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

Questions asked in this paper

1. Q1 Attempt any four sub-questions
   • a) State and explain advantages and limitation of regular and context free grammar. 05
   • b) Design a Mealy machine for a binary adder. 05
   • c) Give formal definition of PDA. 05
   • d) Construct the DFA that accept set of all strings over the alphabet = {a, b} 05
   • e) Find the CNF equivalent to
2. Q2 a) What is NFA? Design a NFA for a binary number where the first and last digit is same. 10 marks
   • b) Write a necessary function for the given automata. 10
3. Q3 a) i) Find a regular expression RE corresponding to the following FA 10 marks
   • ii) Give a regular expression for a language over the alphabet = {a, b} containing at most two.a’s
   • b) Construct a Mealy machine that accepts strings ending in ‘00’ and ‘11’. Convert the 10 same to Moore machine
   • Q.P. Code: 40017
4. 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 paranthesis and Trace the sequence of moves made corresponding to input string 10 marks
5. Q5 a) Let G be the grammar. Find the leftmost derivation, rightmost derivation and parse tree for the string 001222 10 marks
   • b) Design a NFA for accepting input strings that contain either the keyword 000 10 or the keyword 010 and convert it into an equivalent DFA
6. Q6 Write short notes on (any four) 20 marks
   • a) Variants of Turing Machines
   • b) Algorithm for CFG to CNF Conversion
   • c) Chomsky Hierarchy
   • d) Limitation of Finite Automata
   • e) Halting Problem

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