B.TECH - Semester 4 formal languages and automata theory Question Paper 2022 (dec)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Construct a finile automaton that accepts strings not ending in 1 from the sel of slrings in (0+1)
- Prove that the language $L=\left\{a^{n} b^{n} \mid n>0\right\}$ is not regular.
- Write noles on Chornsky hierarchy of languages,
- Give a CFG that generales the language $L=\left\{0^{\circ} 1^{2 n} \mid n>0\right\}$.
- Deline Turing Machine. What are its uses? $$ \text { ( } 5 \times 4=20 \text { Marks) } $$ Answer one full question from each module. Each question carries 20 marks.
- (a) Convert the following NFA to DFA.
- (b) Deline Moore machine. Design a Moore machine lo oulpul residue mod 4 (remainder of the inpul number when divided by 4) for tinary inpul string trealed as binary integer.
- (a) Show Ihal is $L$ is accepled by NFA with $\varepsilon$ transilions, $L$ can be accepled by an NFA yrithoul e transilions.
- (b) Let 1 be a sel accepled by an NFA. Prove that there exists a DFA that accepts $L$. Is the converse true? Juslify your answer.
- (a) Minimize the fallowing DFA.
- (b) Stale and prove pumping lemma for regular languages.
- (a) Stale and prove closure properties of regular sels.
- (b) Oblain a regular expression for the FA given below. 10 (a) With a neal example, explain how CFG can be converted to Chomsky Normal Form.
- (b) Use pumping lemma to show thal $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{n}} \mathrm{c}^{\mathrm{n}} \mid \mathrm{n}>0\right\}$ is nol context free. OR
- (a) Construcl a PDA for $L=\left\{w w^{R} \mid w^{R}\right.$ is the reverse of $\left.w\right\}$.
- (b) Prove the equivalence between PDA and CFG . 12 (a) Prove that if a language and its complement are both recursively enumarable, the language is recursive.
- (b) Design a TM that recognizes $L=\left\{a^{n} b^{n} c^{n} \mid n>0\right\}$. OR
- (a) Explain the varianls of Turing machines.
- (b) Slate halling problem of Turing machines Prove that it is undecidable,