B.TECH - Semester 6 formal languages and automata theory Question Paper 2020 (sep)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Differentiate between Mealy and Moore machine.
- Design a DFA to accept strings over $\{a, b\}$ containing even number of a's and odd number of b's.
- List any four closure properties of regular sets.
- What is NPDA? Give an example.
- Eliminate $\in$-productions from the grammar given below. $$ S->a A B / b B \quad A->a B / \in \quad B->b A / A l a . $$
- What is Universal Turing machine?
- Design a Turing machine to add 2 numbers.
- What is undecidability? Give two examples of undecidable problems.
- Draw a NFA for $(a+b)^{\star}+(a b b)^{*}$.
- What is meant by ambiguity in languages? ( $\mathbf{1 0} \boldsymbol{\times} \mathbf{4} \boldsymbol{=} \mathbf{4 0}$ Marks) P.T.O.
- (a) State and prove the equivalence of NFA and DFA. 10
- (b) Design a DFA to test whether a binary number is divisible by 5 . 10 OR
- (a) Prove that $L=\left\{a^{p} / p\right.$ is prime $\}$ is regular or not. $\quad 10$
- (b) Minimize the states of the DFA. Transition table is given below. 10 | | States | $a$ | $b$ | | :--- | :---: | :---: | :---: | | $->0$ | 1 | 3 | | | 1 | 2 | 4 | | | 2 | 1 | 4 | | | 3 | 2 | 4 | | | (Final State) | ${ }^{\star} 4$ | 4 | 4 |
- (a) What is CNF? Convert the grammar given below to CNF. $\mathrm{S}->\mathrm{ASB} / \in \mathrm{B}->\mathrm{SbS} / \mathrm{A} / \mathrm{bb}$ A->aAS/a.
- (b) Describe Chomsky classification of languages.
- (a) Design a PDA accepting $L=\left\{a^{n} b^{m} a^{n} / m, n>=1\right\}$.
- (b) Remove useless symbols of the CFG given by $\mathrm{S}->\mathrm{AB} / \mathrm{CA}, \mathrm{B}->\mathrm{BC} / \mathrm{AB}, \mathrm{A}->\mathrm{a}, \mathrm{C}->\mathrm{aB} / \mathrm{b}$.
- (c) Write the context free grammar that generates $$ L=\left\{a^{i} b^{j} c^{k} \mid i, j, k \geq 0, \text { and } i=j \text { or } i=k\right\} . $$
- Explain the different variants of Turing Machine in detail.
- Design a Turing machine to multiply 2 numbers. ( $\mathbf{3} \boldsymbol{\times} \mathbf{2 0} \boldsymbol{=} \mathbf{6 0}$ Marks)