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

Con.3719-10                                   (REVISED COURSE)                         AN-4228

                                                                  (3 Hours)                              [Total Marks:-100]

N.B: (1) Question No.1 is compulsory.
        (2) Attempt any four questions from the remaining questions.

1. (a) Define DFA and state applications of Finite Automata in brief. [5 Marks]
    (b) Obtain a grammer to generate the language
          

    (c) State and prove Pumping Lemma Theorem for regular languages. [5 Marks]

    (d) Differentiate deterministic Push Down Automata and Non-deterministic Push Down
         Automata. [5 Marks]  

2. (a) (i) Obtain DFA to accept string's of a a's and b's with even no of a's and even no of a's and
              even no. of b's. [10 Marks] 
         (ii) Obtain a regular expression such that L(R) = {W |W with atleast three consecutive's zeros.
    (b) Give Mealy and Moore machine for input ends in 110, output should be y, otherwise output
         should be z. [10 Marks]

3. (a) Design PDA for the following languages. [10 Marks]
         L(M) = {WCwR} Wε{a,b} where wR is reverse of W and C is constant. [10 Marks]
    (b) For the grammar
          S -> aABC
          A -> aB/a
          B -> bA/b
          C -> a
          Obtain the corresponding PDA.

4. (a) Using Pumping Lemma theorem, show that following grammars are not regular:- [10 Marks]
             (i)     
             (ii)

         
    (b) Construct reduced DFA for language represented by [10 Marks]
            (ab/ba)*aa(ab/ba)

5. (a) Convert the following grammar in Chomsky Normal form [10 Marks]
           S -> ASB/ε
           B -> Sbs/A/bb
           A -> aAS/a
     (b) Show that the following grammar is ambiguous [10 Marks]
           S -> aSbs
           B -> bSaS
           A ->

6. (a) Design TM that replaces all occurrences of "111" by "101" from sequence of 0's
         and 1's. [10 Marks]
    (b) Define post correspondence problem and prove that PCP with two lists x = {b,bab3,ba} and
          y = {b3, ba,a} have a solution. [10 Marks]

7. (a) Minimize the following DFA, where q3 and q5 are final states [10 Marks]

    (b) Write short notes on:- [20 Marks]
          (i) Universal Turing Machine
         (ii) P & NP problems.