B.TECH - Semester 6 formal languages and automata theoery Question Paper 2019 (jun)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- 603 : FORMAL LANGUAGES AND AUTOMATA THEORY (R) Time : 3 Hours Max. Marks 100 PART - A Answer all questions :
- What are Mealy machines?
- Reduce the regular expression $(00+0+1)^{*}$.
- What is a decision algorithm?
- List down the applications of finite automata.
- Give Chomsky's hierarchy for formal languages.
- What is yield of a parse tree?
- Design a PDA to accept strings of balanced parenthesis.
- Compare single tape with multiple tape Turing machines.
- Differentiate recursive and recursively enumerable languages.
- What are offline Turing machines? ( $\mathbf{1 0} \boldsymbol{\times} \mathbf{4} \boldsymbol{=} \mathbf{4 0}$ Marks) P.T.O. Answer any one full questions from each Module. Each question carries 20 marks.
- (a) Construct a $\in N F A$ using Kleene's Theorem to accept the language $(01+0)^{\star} 11$. Convert the constructed NFA to a DFA using subset construction method. 20
- (b) (i) Show that regular language are closed under difference operation. 10 (ii) Find the regular expression of the DFA in Fig. 1. 10 Fig. 1
- (a) (i) Give CFG for the language $\left\{a^{i} b^{j} c^{k} \mid j=i+k\right\}$. (ii) Construct a bottom up PDA for the CFG accepting the regular language $a^{*} b$.
- (b) (i) Prove that the language $L=\left\{x \in\{a, b, c\}^{\star} \mid n_{a}(x)>n_{b}(x)>\right.$ and $\left.n_{a}(x)>n_{c}(x)\right\}$ is not a CFL. (ii) Give the steps to convert a CFG into CNF. Consider the following set of productions, convert t...
- (a) (i) Design a Turing machine to perform proper subtraction of two numbers $m$ and $n$. (ii) Encode the Turning machine given in Fig. 2 for writing in an Universal Turning machine. Fig. 2
- (b) Prove that post correspondence problem is undecidable. ( $\mathbf{3} \boldsymbol{\times} \mathbf{2 0} \boldsymbol{=} \mathbf{6 0}$ Marks)