B.TECH - Semester 6 formal languages and automata theory Question Paper 2021 (dec)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- List and explain the properties of transition functions.
- State pumping lemma for regular set.
- Explain the use of decision algorithm for regular sets.
- Let r be a regular expression. Prove that there exists an NFA with $\varepsilon$-transitions that accepts $L(r)$.
- Compare and contrast between Chomsky normal form and Greibach normal forms.
- Construct context free grammar for the following CFLs (a) $L=\left\{a^{n} b^{m} \mid n, m>=1\right\}$
- Construct context free grammar for the following CFLs (b) $L=\left\{a^{n} b^{m} c^{m} d^{n} \mid n, m>=1\right\}$.
- Mention the differences between ambiguous grammar and unambiguous grammar.
- Prove that if a language $L$ and its complement $L^{\prime}$ are recursively enumerable languages then $L$ is recursive language.
- Explain the use of universal Turing machine.
- Write about single and multitape Turing machines. Answer any one full question from each module.
- (a) Construct NFA, DFA and Minimal DFA for the regular expression $(r)=a^{*} b b$.
- (b) (i) Construct the Moore and Mealy machines for computing residue mod 3. (ii) List and explain the closure properties of regular sets.
- (a) (i) Find a grammar in Chomsky normal form equivalent to $S \rightarrow A B \mid a B$, $A \rightarrow a a b, B \rightarrow b b A$. (ii) Construct the Push down automata for the language $L=\left\{w c w^{R} \mid w\right.$ is in $\left.(0+1)^{*}\rig...
- (b) (i) Prove that the language $L=\left\{a^{n} b^{n} c^{n}: n \geq 1\right\}$ is not context free. $\quad 10$ (ii) Is the grammar $S \rightarrow S b S \mid a$ ambiguous. Find the parse trees, leftmost and rightmost derivations for the string abababa...
- (a) (i) Construct a Turing Machine to recognize the language $L=\left\{0^{n} 1^{n} 0^{n} \mid n>=1\right\}$. (ii) Explain the universal Turing machine with an example.
- (b) (i) What is halting problem? Explain with an example. ## \section*{Module - Ill <br> <br> Module - Ill}
- (i) Construct a Turing Machine to recognize the languag $L=\left\{0^{n} 1^{n} 0^{n} \mid n>=1\right\}$. xplain the universal Turing machine with an example. (ii) Prove that the union of two-recursive language is recursive and union of two recursively...