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

Questions asked in this paper

1. Q1 (a) Find the CFG for the regular expression (10)*(1 10+01)*. 5 marks
   • (b) Write short note on Universal Turing Machine. 5
   • (c) Difference between FA and PDA 5
   • (d) Design moore machine to convert each occurrence of 111 to 101 Q Construct NFA with epsilon which accept a language consisting the string of any (10) number of a’s followed by any number of b’s followed by any number of c’s Also convert it into NFA without epsilon 5
   • (b) Moore and Mealy machine for a binary input sequence such that if it has a substring 011 the machine outputs A if input has substring 001 it outputs B otherwise it outputs C 10
2. Q3 (a) Minimize the following DFA where A is a start state and B,C and E are 10 marks
   • Q.P. Code: 25528
   • (b) Use pumping lemma prove that whether following language is regular or not 10
3. Q4 (a) Define context free grammer. Obtain the CFG for the following refular expression: 10 marks
   • (b) Convert given CFG to GNF where V={S,A}, T={0,1} and P is 10
4. Q5 (a) Design a PDA to accept a string of balanced parentheses. The parentheses to be considered (, ), {, } 10 marks
   • (b) Construct TM for L= n>=1} 10
5. Q6 Write short notes on (Any two) 20 marks
   • (a) Pumping Lemma for Regular Languages
   • (b) Recursive and Recursively enumerable languages
   • (c) Unsolvable Problems

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