THEORY OF COMPUTER SCIENCE (TCS) MAY 2011 COMPUTER SCIENCE SEMESTER 5

       THEORY OF COMPUTER SCIENCE (TCS) MAY 2011 COMPUTER SCIENCE SEMESTER 5 

                                                  (3 Hours)                                      [Total Marks:- 100]

1. (a) Differentiate between:-
         (i) NFA and DFA
         (ii) Moore and Mealy machines. [5 Marks]
    (b) Design a Mealy Machines. [5 Marks]

2. (a) Design a DFA to accept the following languages over the alphabet {0,1} [10 Marks]
         (i) {W | W starts with zero and has odd length or starts with one has even length}
        (ii) {W|every odd position of w is 1}
    (b) Find a minimum state finite automata equivalent to the following automata :- [10 Marks]

3. (a) Give and explain the formal statement of Pumping Lemma for regular languages and use it to
          prove that the following language is not regular : - [10 Marks] 
           
    (b) Convert the following NFA with epsilon moves to a minimum state DFA accepting the
          same language:- [10 Marks]

4. (a) Design a PDA for the language [10 Marks]
      
    (b) Design a PDA for the following grammar and test whether is in the language defined by that
         PDA. [10 Marks] 
          S -> 0BB
          B -> 0S | 1S | 0

5. (a) Reduce the following grammars to GNF [10 Marks]
          (i) S -> AB
              A -> BSB | BB| b
         (ii) B aAB | a  [5 Marks]
              S -> AA | 1
              A -> SS | 1
     (b) Convert the following grammars to CNF [10 Marks]
            A -> aBb | bBa
            B -> aB | bB | ε

6. (a) Design a Turing Machine to accept the language [10 Marks]  

         

    (b) Design a Turing Machine that computes a function f(m,n) = m+n for the addition of 2 

          integers. [10 Marks] 

7. Write short notes on (any three) :- [20 Marks]

     (a) Halting problem 

     (b) Post Correspondence Problem

     (c) Chomsky Hierarchy

     (d) Intractable Problems

     (e) Greibach Theorem.