Computer Engineering Sem 4 Theoretical Computer Science Question Paper PDF 2026 - Mumbai University | munotes

Questions asked in this paper

1. Q1 (a) Write short note on Myhill Nerode theorem 5 marks
   • (b) Differentiate between NFA and DFA. 5
   • (c) State and explain Closure properties of Context Free Language 5
   • (d) Explain Post Correspondence problem. 5
2. Q2 (a) Construct the i for the language in which strings starts and ends different letter over the set = {.a, b }
   • ii) for the R.E (01+2*) 10
   • (b) Give and Explain formal definition of Pumping Lemma for Regular Language and 10 prove that following language is not regular
3. Q3 (a) Convert the given grammar into Griebach Normal Form 10 marks
   • (b) Construct PDA for a language L={wew* | w {a,b} and is reverse of w} 10
4. Q4 (a) Construct TM to check palindrome over 10 marks
   • (b) Design a DFA which accepts all strings not having more than 2 a’s over b} 10
5. Q5 (a) Convert (0+1) into NFA with e-moves and obtain DFA. 10 marks
   • (b) Design Mealy Machine that accepts an input from (0+1)* if the input ends in 101, 10 output A; if the input ends in 110, output B, otherwise C. then convert into
6. Q6 (a) Draw a parse tree for the string “abaaba” for the CFG given by G where Also Determine whether the given CFG is ambiguous or not 10 marks
   • (b) Write short note on following 10
7. Q1 Halting problem

Read from the scan above, so a character or two may differ. The scan is the original.