# Mumbai University Previous year question papers

## V Sem CSE Examination June 2007

## Theory of Computer Science

N.S.: (1) Question No. ~ is compulsory.

(2) Answer any four out of the remaining six questions.

1. (a) Distinguish between NFA and DFA. Give two examples of each.

(b) Design a FSM for testing divisibility by three.

(c) Design a Moore M/c to change all vowels to ‘$’.

(d) Design a PDA to accept (ab)n (cd)n.

2. (a) What is p~rsing ? What are the two different parsing.methods ? Explain thier difference with examples.

(b) Design a TMto generate 2n. 10

3. (a) Design a suitable PDA to accept an even palindrome over {a, b}.

(b) Design a NFAto accept (a/b)* aba. Convert it to a reduced DFA.

4. (a) Design a TMto accept (1

n 1 bn). Can a DFA be designed for the same? Justify.

(b) Convert the followingto CNF :

S ~ a S b / b S a / ab / ba / E.

5. (a) Design a TM to multiply 2 unary numbers.

(b) Use pumping lemma to show that the following is regular.

L={x/ x =on 12m n > a }m>O

6. (a) Define different types of grammers and give one example of each.

(b) State different types of machines and state atleast one application of each.

7. Write short notes on any five out of the following:

(a) GNF

(b) Universal TM

(c) Recursive descent parser

(d) Post correspondence problem

(e) Myhill-Nerode theorem

(f) Ambiguity resolution.