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

Questions asked in this paper

1. Q1 Attempt any three out of the remaining five questions Assumptions made should be clearly stated
2. Q1 Attempt any four sub-questions
   • a) Construct the Finite Automata for binary umber divisible by 2 5
   • b) Design FA for decimal number divisible by 5 5
   • c) Give formal definition of Turing Machine 5
   • d) State and explain closure properties of regular languages 5
   • e) Construct DFA accepting all the strings corresponding to the Regular expression
3. Q2 a) Construct the following grammar to CNF 10 marks
   • b) Design Moore machine for binary adder. 10
4. Q3 a) Design a DFA corresponding to. the regular expression aba 10 marks
   • b) Define CFG, obtain CGF for the following grammar 10
5. Q4 a) Design a PDA for CFL that checks the well formedness of parenthesis i.e. the language L of all balanced string of two types of parenthesis and “[ the sequence of moves made corresponding to input string (10)
   • b) Construct a TM for complement of a binary number. Simulate it for 1 0 10 10
6. Q5 a) Let G be the grammar. Find the leftmost derivation, rightmost derivation and parse tree for the string 001222 10 marks
   • b) Consider the CFG | bSal SS , consider the string babbabaaaababb that given grammar is ambiguous by generating more than one parse tree for a given string (10)
7. Q6 Write short notes on 20 marks
   • a) Applications of Automata Theory
   • b) Chomsky Hierarchy
   • c) Power and limitations of PDA
   • d) Halting Problem

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