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

Questions asked in this paper

1. Q1 (a) Explain Chomsky Hierarchy. 5 marks
   • (b) Differentiate between NFA and DFA. 5
   • (c) Define Regular Expression and give regular expression for 5 Set of all strings over { a, b,c } that starts and ends with different symbol
   • (d) Explain Post Correspondence problem. 5
2. Q2 (a) Design F.A. for following R.E. 10 marks
   • (b)Give and Explain formal definition of Pumping Lemma for Regular Language and 10 prove that following language is not regular
3. Q3 (a) Test whether 001100, 001010 are in the language generated by grammar and draw parse tree 10 marks
   • (b) Construct PDA for a language | we {a,b} and is reverse of w} 10
4. Q4 (a) Construct TM to check palindrome over 10 marks
   • (b) Explain CNF and GNF in detail and convert given grammar in GNF. 10
5. Q5 (a) Convert (0+1) into NFA with 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 Write short note on following (any 4) 20 marks
   • (a) Closure properties of Context Free Language
   • (c) Rice’s Theorem
   • (d) Moore and Mealy Machine
   • (e). Variant of TM

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