B.TECH - Semester 4 formal languages and automata theory Question Paper 2019 (jun)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Design a DFA to accept strings over $\{a, b\}$ containing even number of $a$ 's and odd number of $b$ 's.
- State My-Hill Nerode theorem.
- What is ambiguous grammar? Give an example.
- Write the regular expression for set of all strings of zeroes and ones not containing 10 .
- Define recursive and recursively enumerable languages. $$ (5 \times 4=20 \text { Marks }) $$ P.T.O. Answer any one full question from each Module. Each full question carries 20 marks.
- (a) State and prove the equivalence of NFA and DFA.
- (b) Design a DFA to accept string of 0's and 1's when interpreted as binary numbers would be multiple of 4 . OR
- (a) Design Moore Machine for the input from $(0+1+2)^{*}$ which print the residue modulo 5 of the input treated as ternary number.
- (b) Compare Moore and Mealy Machine.
- (c) Describe two way Finite automata.
- (a) State and prove the equivalence of regular expression and finite automata.
- (b) Find a regular expression corresponding to finite automata given below. | States | 0 | 1 | | :---: | :---: | :---: | | $\rightarrow q_{1}$ | $q_{1}$ | $q_{2}$ | | $q_{2}$ | $q_{3}$ | $q_{2}$ | | $q_{3}$ | $q_{1}$ | $q_{4}$ | | $q_{4}$ | $q_{1}$ ...
- (a) Draw an $\varepsilon$-NFA for the regular expression $(a+b)^{*} a b b$ and convert it to DFA. 15
- (b) Prove that $L=\left\{a^{p} / p\right.$ is prime $\}$ is regular or not.
- (a) Define Greibach Normal form (GNF). Convert the following grammar to GNF. $S \rightarrow A B a \rightarrow B S / b B \rightarrow S A / a$
- (b) Check the ambiguity in $S \rightarrow a B / b A \quad A \rightarrow a / a S / b A A \quad B \rightarrow b / b S / a B B . \quad 10$
- (a) Design a PDA to recognize all palindromes over $\{0,1\}$.
- (b) Remove useless symbols of the CFG given below and convert to Chomsky Normal form. $s \rightarrow 0 A 0 / 1 B 1 / B B \quad A \rightarrow C \quad B \rightarrow S / A \quad C \rightarrow S / \varepsilon$ Module - IV
- (a) Explain Universal Turing machine.
- (b) Design a Turing machine that computes a function $f(m, n)=m \div n$, i.e. proper subtraction of 2 integers defined as $m \div n$ if $m>n$ and 0 otherwise.
- Design a Turing machine to multiply two numbers.