# Mumbai University Previous year question papers

## V Sem CSE Examination Dec 2009

## Theory of Computer Science

Note. (1) Question No 1 is Compulsory.

(2) Attempt any questions from remaining six questions.

(3) Figures to the right indicate full marks given to the question.

(4) Assume suitable data, if necessary.

I. (a)Distinguish between NFA and DFA

(b) Design’Finite Automata from 1(0/1)*0 Regular Expression

(c) Explain CNF and GNF with example.

(d) Explain Classesof Complexity with example.

2. (a) Design a Moore and Mealy Machine to convert substring aba into abb.

(b) Construct DFA accepting the following language

(i) Strings ending with 110 or III

(ii) String containing 010 as a substring.

3. (a)Let G be the grammar

S~aBlbA

A ~alaSlbAA

B~blbSlaBB

Find leftmost deriyation, rightmost derivation and parse tree for the string “bbaaabbaba”

(b) Designa PDAfor the following

CFG S~ ( S )ISS

4. (a) Stateandexplain pumping Lemma for regular languages. (10)

Using Pumping lemma, show that following grammars are not regular.

(i) L= {In In is prime number}

(ii) L= {OnIOn I n>O}

(b) Design a TM to subtract two numbers (e.g. m and n are two integers and m-n is to be evaluated)assumem>n–( I0)

5. (a) Construct NFA from (0+1)*(00+11) and convert into minimized DFA (10)

(b) Write CFG for language having number of a’s greater than number ofb’s and Design a PDA for the same. (10)

6. (a) Design a TM to accept language {On1nln>O} (10)

(b) Explain decision properties for regular languages (10)

7. Write short notes on (Any Four) (20)

(a) Variants ofTM

(b) Deterministic Pushdown Automata

(c) Recursive and Recursively Enumerated”Languages

(d) Complements of languages in NP

(e) ChomskyHierarchy