THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2009 COMPUTER SCIENCE SEMESTER 5

THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2009 COMPUTER SCIENCE SEMESTER 5 

Con.5503-09.                                  (REVISED COURSE)                         SP-8562
  
                                                              (3 Hours)                                [Total Marks:100]

Note:- (1) Question No.1 is compulsory
           (2) Attempt any four questions from remaining six questions.
           (3) Figures to the right indicate full marks given to the questions.
           (4) Assume suitable data, if necessary.

1. (a) Distinguish between NFA and DFA. [4 Marks]
    (b) Design Finite Automata from 1(0/1)*0 Regular Expression. [5 Marks]
    (c) Explain CNF and GNF with example. [5 Marks]
    (d) Explain classes of Complexity with example. [6 Marks]

2. (a) Design a Moore and Mealy Machine to convert substring aba into abb. [10 Marks]  
    (b) Construct DFA accepting the following language. [10 Marks]
           (i) Strings ending with 110 or 111.
          (ii) String containing 010 as a substring.

3. (a) (b) Let G be the grammar [10 Marks]
                                   S -> aB|bA
                                   A -> a|aS|bAA
                                   B -> b|bS|aBB
            Find leftmost derivation, rightmost derivation and parse tree for the string "bbaaabbaba".
  
   (b) Design of PDA for the following CFG:  [10 Marks]
                                                          S -> (S) | SS|

4. (a) State and explain pumping Lemma for regular languages. [10 Marks]
          Using Pumping Lemma, show that the following grammars are not regular.
           (i) L= {1n| n is prime number}
          (ii) L= {0n 10n|n>0}
    (b) Design a TM to subtract two numbers (e.g m and n are two integers and m-n is to be
          evaluated ) assume m>n. [10 Marks]   

5. (a) Construct NFA from (0+1)*(00+11) and convert into minimized DFA. [10 Marks]
    (b) Write CFG for language having numbers of a's greater than number of b's and Design a PDA for
          the same. [10 Marks]

6. (a) Design a TM to accept language {0n1n|n>0} [10 Marks]
    (b) Explain decision properties for regular languages. [10 Marks]

7. Write short notes on (any four):- [20 Marks]
     (a) Variants of TM
     (b) Deterministic Pushdown Automata
     (c) Recursive and Recursively Enumerated Languages.
     (d) Complements of languages in NP.
     (e) Chomsky Hierarchy