Subject: Formal Languages and Automata Theory (Cse 2201)

Download as pdf or txt
Download as pdf or txt
You are on page 1of 2

Reg.

No

IV SEMESTER B.TECH. (COMPUTER SCIENCE AND ENGINEERING)

END SEMESTER EXAMINATIONS, APRIL/MAY 2019

SUBJECT: FORMAL LANGUAGES AND AUTOMATA THEORY [CSE 2201]


REVISED CREDIT SYSTEM
(24/4/2019)
Time: 3 Hours MAX. MARKS: 50

Instructions to Candidates:
 Answer ALL the questions.
 Missing data may be suitable assumed.

1A. A binary tree is a tree in which no parent can have more than two children. Prove by 2
induction that a binary tree of height n has at most 2n leaves.
1B. With an example for each list and explain the types of grammars defined by 4
Chomsky.
1C. Convert the NFA given in Fig 1C. to its equivalent DFA. 4

Fig 1C.
2A. Give Right linear grammar for the regular expression 0*(1(0+1))* using only 3 3
variables(Non terminals).
2B. Draw a DFA to accept the language L1=L(a*baa*) and find language generated from 3
L1/L2 by modifying the DFA for L1 where L2=L(ab*).
2C. Draw the DFA after Minimizing the number of states in the DFA given in Fig 2C. 4

Fig 2C.

CSE-2201 Page 1 of 2
3A. What is Turing Machine halting problem? Let A= {011,00,000} and 3
B={110,000,00}. Check whether a Post Correspondence problem exists or not.
3B. Using pumping lemma prove that L = {w | w = w R, w ∈ {0, 1} ∗} is not regular. 3
3C. Transform the grammar with productions S → abAB, A → bAB|λ, B → BAa|A|λ 4
into Chomsky Normal Form.

n! 2
4A. Show that the L = { a | n>=0} is not context free.
4B. Design a Turing Machine for the language L = {X ϵ {a, b}* | X ends with aba} and 4
show its transition using a transition diagram. Also trace the acceptance of the string
‘abababa’ using instantaneous description.
4C. Identify the language generated by the grammar S  aSd | aAd , A  bAc | bc and 4
construct PDA for the generated language and show the transitions using the
transition diagram. Also trace a sample string generated from the language using
instantaneous description.

5A. Explain Turing’s thesis as a definition of a mechanical computation. 3


5B. What is ambiguous grammar? Show that the grammar with the productions: 3
S → aSbS|bSaS|λ is ambiguous for the string “abab” using the derivation trees.
5C. Obtain a Turing Machine to accept a string w of 0’s and 1’s such that the number of 4
0’s (w) is equal to number of 1’s (w). Show that the truing machine accepts some
valid input.

CSE-2201 Page 2 of 2

You might also like