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

Questions asked in this paper

1. Q1 Question No. | is compulsory
2. Q2 Out of remaining questions, attempt any three questions
3. Q3 Assume suitable data wherever required but justify the same
4. Q4 All questions carry equal marks
5. Q5 Answer to each new question to be started on a fresh page
6. Q6 Figure to the right in brackets indicate full marks
7. Q1 Solve any four from the followings
   • (a) Construct Moore machine equivalent to following Mealy machine. 5
   • (b) Construct a PDA for the following Context Free Grammar (CFG). 5
   • (c) Construct right grammar and left linear grammar for the regular
   • (d) Explain the concepts, acceptance by final state and acceptance by empty stack of a Pushdown automata with suitable example. [05]
   • (e) Construct regular expression for the following FA using state elimination method. 5
8. Q2 (a) Write down the regular expressions for the following language. 4 marks
9. Q1 Lis the language of all strings over {0, 1} having odd number of 0’s and any il. Lis the language of all strings over {0, 1} having number of 1’s multiple of three
   • (b) Construct DFA for the following NFA with 10
   • (c) Construct NFA with s-moves for the regular expression ab*(a + b)* + ba* 6
10. Q3 (a) Covert the following context free grammar into Chomsky normal form. 10 marks
    • (b) Construct a Context Free Grammar (CFG) for the following PDA. M = ({go, qi}, ), {G L Zo}, 5, qo, Zo, B) and 6 is given by: 10
11. Q4 (a) Construct a PDA for L = 1 10 marks
    • (b) Design a DFA over {0, 1} which accepts all strings that contain substring ‘11’ and do not contain the substring *00’. [06]
    • (c) Give context free grammar for the following languages. 4
    • ii. 1}
12. Q5 (a) Construct Turing Machine to accept language L = |n > 1}. 10 marks
    • (b) Find the equivalent NFA with e-moves accepting the regular language defined by the
    • (c) Let G be the grammar having following set of production. For the string find a leftmost derivation and rightmost derivation 6 is given in the following table. [06] 5
    • (b) Construct Turing Machine wherein given an input 1" leaves on the tape. Covert the TM design into equivalent function. [10]
    • (c) What do you understand by closure property? State the various set theoretic operations under which regular languages are closed. Give suitable example. [04]

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