Formal Languages and Automata Theory - May 2016

VTU Computer Science (Semester 5)

Total marks: --
Total time: -- INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary 1(a) Define the following with examples: i) Alphabet, ii) String. 4 marks

1(b) Define DFA. Write the DFA's for the following languages on ∑={a,b}.
i) The set all strings containing the substring 'ab'.
ii) L = {ω |ω| mod 3=0} 4 marks

1(c) Convert the following NFA to its equivalent DFA.
4 marks

2(a) Define a regular expression. Also write the regular expressions for the following languages.
i) The set of all strings ending in the substring '00' on ∑={0,1}
ii) L = {aⁿb^m | n≥4, m≤3}. 4 marks

2(b) Prove that every language defined by a regular expression is also defined by a finite automation. 4 marks

2(c) Write the ∈-NFA for the regular expression ab(a+b)*. 4 marks

3(a) State and prove pumping lemma for regular languages. 4 marks

3(b) Show that the language L = {aⁿbⁿ | n≥0} is not regular. 4 marks

3(c) Minimize the following DFA using table filling algorithm.

4(a) Define CFG. Design CFG's for the following languages:
i) L = {aⁿb²ⁿ | n≥0}
ii) L = {ω;ω^R / ω∈ {a,b}*} 4 marks

4(b) Write the LMD, RMD and parse tree for the string '+*-xyxy' using the grammar
E → EE | *EE | -EE | x | y 4 marks

4(c) What is an ambiguous grammar? Show that the following grammar is ambiguous:
E → E + E | E * E | (E) | id 4 marks

5(a) Define a PDA and explain the working of it with a neat diagram. 4 marks

5(b) Design a PDA for the language L = {ωω^R | ω ∈ {a, b}'. Draw the transition diagram and also write the sequence od ID's for the string 'abba'. 4 marks

5(c) Convert the following CFG to an equivalent PDA:
S → aA
A → aABC|bB|a
B → b
C → c 4 marks

6(a) Eliminate the useless symbols and productions from the following grammer.
S → AB|AC
A → aA|bAa|a
B → bbA|aB|AB
C → aCa|aD
D → aD|bC 4 marks

6(b) Define CNF and convert the following grammer into CNF.
S → Aba
A → aab
B → Ac 4 marks

6(c) Prove that the family of context-free languages is closed under union, concentration and star-closure. 4 marks

7(a) Define a turing machine and explain the working of a basic turing machine with a neat diagram. 4 marks

7(b) Design a turing machine for the language L = {aⁿbⁿ | n≥1}. Write the transition diagram for the same and also, indicate the moves by the machine for the input 'aabb'. 4 marks

Write short notes on

8(b) post's correspondence problem 4 marks

8(c) Applications of context-free languages. 4 marks

8(d) Chomsky hierarchy 4 marks