Subject: Formal Languages and Automata Theory (Cse 2201)
Subject: Formal Languages and Automata Theory (Cse 2201)
Subject: Formal Languages and Automata Theory (Cse 2201)
No
Instructions to Candidates:
Answer ALL the questions.
Missing data may be suitable assumed.
1A. A binary tree is a tree in which no parent can have more than two children. Prove by 2
induction that a binary tree of height n has at most 2n leaves.
1B. With an example for each list and explain the types of grammars defined by 4
Chomsky.
1C. Convert the NFA given in Fig 1C. to its equivalent DFA. 4
Fig 1C.
2A. Give Right linear grammar for the regular expression 0*(1(0+1))* using only 3 3
variables(Non terminals).
2B. Draw a DFA to accept the language L1=L(a*baa*) and find language generated from 3
L1/L2 by modifying the DFA for L1 where L2=L(ab*).
2C. Draw the DFA after Minimizing the number of states in the DFA given in Fig 2C. 4
Fig 2C.
CSE-2201 Page 1 of 2
3A. What is Turing Machine halting problem? Let A= {011,00,000} and 3
B={110,000,00}. Check whether a Post Correspondence problem exists or not.
3B. Using pumping lemma prove that L = {w | w = w R, w ∈ {0, 1} ∗} is not regular. 3
3C. Transform the grammar with productions S → abAB, A → bAB|λ, B → BAa|A|λ 4
into Chomsky Normal Form.
n! 2
4A. Show that the L = { a | n>=0} is not context free.
4B. Design a Turing Machine for the language L = {X ϵ {a, b}* | X ends with aba} and 4
show its transition using a transition diagram. Also trace the acceptance of the string
‘abababa’ using instantaneous description.
4C. Identify the language generated by the grammar S aSd | aAd , A bAc | bc and 4
construct PDA for the generated language and show the transitions using the
transition diagram. Also trace a sample string generated from the language using
instantaneous description.
CSE-2201 Page 2 of 2