B.TECH - Semester 4 formal languages and automata theory Question Paper 2020 (sep)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Explain the different variants of Turing Machine in detail. ..... 20 OR
- Design a DFA that accepts strings of binary numbers divisible by 3
- Differentiate Mealy and Moore machine.
- What is NPDA? Give an example.
- Design a Turing machine to find 2's complement of a binary number.
- Draw a NFA for $(a+b)^{*} a b$. PART - B Answer any one full question from each Module. Each full question carries 20 marks.
- (a) State and prove the equivalence of NFA with and without E-transitions.
- (b) Design a Moore machine to determine residue mod 6 for each binary string which when interpreted as a non negative integer. Convert this Moore machine to Mealy machine.
- (a) Convert the following NFA to DFA.
- (b) Construct a DFA to recognize decimal strings divisible by 3 .
- (a) Prove that $L=\left\{w w^{R} / w \in\{0,1\}^{*}\right.$ and $w^{R}$ is the reverse of $\left.w\right\}$ is not regular.
- (b) Convert to regular expression the FA given below.
- (a) Minimize the automata given below. | States | 0 | 1 | | :--- | :--- | :--- | | $\rightarrow q 0$ | q1 | q2 | | q1 | q2 | $\mathrm{q}_{3}$ | | $\mathrm{q}_{2}$ | $\mathrm{q}_{2}$ | q4 | | ${ }^{*} \mathrm{q}_{3}$ | $\mathrm{q}_{3}$ | q3 | | *q4 |...
- (a) Convert the grammar given below to CNF. ..... 10 $$ S \rightarrow \sim S / S \supset S / p / q $$
- (b) Describe Chomsky hierarchy. ..... 10 OR
- (a) Design a PDA accepting $L=\left\{a^{n} b^{n} / n>=0\right\}$ ..... 10
- (b) Remove useless symbols of the CFG given by ..... 5 $$ S \rightarrow A B / C A, B \rightarrow B C / A B, A \rightarrow a, C \rightarrow a B / b . $$
- (c) Write the context free grammar to generate equal number of a's and b's. ..... 5 Module - IV
- (a) Design a Turing machine that accepts strings with equal number of O's and1's.10
- (b) State and prove halting problem of Turing machines. ..... 10 [^0]: (b) Describe decision algorithms for regular sets. 5
- (c) List closure properties of regular sets.