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

Questions asked in this paper

1. Q1 Question No.1 is compulsory
2. Q2 Attempt any three question form reaming question
   • a) Construct NFA for accepting the set of all strings over the input {0,1}, whose second last symbol is | (05)
   • b) State and explain limitations and power of Finite Automata. 5
   • c) Design a Moore machine for binary number divisible by 3 5
   • d) Give formal definition of a Push Down automata (PDA) 5
3. Q2 a) Convert the following grammar to CNF 10 marks
   • b) Design DFA to accept
   • i. Binary Strings in which every. 0 is followed by 11 li. String over the binary alphabet that do not contain the substring 010 (05) 5
   • a) Minimize the following DFA. 10
   • b) Convert the following NFA to DFA( final state is marked with *) 10
   • a) Design PDA for recognizing L= {a" a" } 10
   • b) Design a Turing Machine to recognize the language L = {a" | n 10
   • a) Using the pumping Lemma prove that the following language is not regular
   • b) Design Melay machine to accept all the strings ending with 00 or 11 10
4. Q6 Write a Short Note on (any four) 20 marks
   • a) Chomsky Hierarchy
   • b) Applications of Automata theory
   • e) Halting Problem

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