Mumbai University Previous year question papers Theory of Computer Science Dec 2008

Mumbai University Previous year question papers

V Sem CSE Examination Dec 2008

Theory of Computer Science


 (1) Question No.1 is compulsory.

(2) Attempt any four questions from the remaining questions.

1. (a) Design the DFA for the language, contains strings in which leftmost symbol differ from rightmost symbol. given { 0, 1 }.

(b) What is Turing machine? Explain different techniques for Turing machine construction.


2. (a) Compare and contrast Moore and Mealey machine. Design a Mealey machine to convert each occurrence of substring abb by aba. L = { a, b }

(b) What is parsing? What are the two different parsing methods?

Explain their differences with examples.


3.(a) Prove that it is undecidable whether a context free grammar is ambiguous.

(b) Prove the variations and equivalence of the push down automata.


4.(a) State and prove pumping Lemma for context free languages.

(b) Design a grammer for accepting an Even Palindrome over L = { a, b}. 


5.(a) Design a Turing machine to Compute n!.

(b) Explain GNF with suitable example.


6.(a) Write a program to translate a regular expression to finite automata


(b) Construct a NFA for the regular expression 01 * + 1 and convert it to DFA.


7.Write a detail note on (any four) ;-

 (a) Post correspondence problem

(b) Halting problem

(c) Uz:tiversal TM

(d) Myhill-Nerode’s theorem

(e) Ambiguity resolution.

Leave a Comment