Information Technology Engineering Sem 4 Automata Theory Question Paper PDF 2026 - Mumbai University | munotes

Questions asked in this paper

1. Q2 Solve any three out of remaining question
2. Q1 Answer any four. 20 marks
   • a) Differentiate between Moore machine and Mealy machine
   • b) What do you mean by ambiguous grammar? Prove that the following grammar is ambiguous
   • c) Distinguish between NFA and DFA
   • d) What is Halting problem? Explain with example
   • e) What is a regular expression? Design DFA corresponding to the regular expression
3. Q2 a) Define the structure of Push Down Automata (PDA). Explain the power and limitations of PDA. (10)
   • b) Design PDA to accept language L = {a"b*"| n> 1}. 10
4. Q3 a) Define CFG. Design a CFG for the language L = { }. 10 marks
   • b) Find the leftmost derivation, rightmost derivation and parse trees for the string
   • a) Describe Chomsky Normal Form (CNF). Convert the following CFG to CNF 10
   • b) Explain Greibach Normal Form (GNF) Convert the following CFG to GNF 10
5. Q5 a) What is a Turing Machine (TM)? Explain the working of TM with a neat sketch Also describe the variants of TM (10)
   • b) Design a TM to accept (a"b"c"). Can a DFA be designed for the same? Justify. 10
6. Q6 Write short notes on (any four) 20 marks
   • b) Chomsky Hierarchy
   • c) Right Linear and Left Linear Grammars
   • d) Phases of Compiler

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