Question Paper: Formal Languages and Automata Theory Question Paper - May 2016 - Computer Science (Semester 5) - Visveswaraya Technological University (VTU)

Formal Languages and Automata Theory - May 2016

VTU Computer Science (Semester 5)

Total marks: --
Total time: --
(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 = {anbm | 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 = {anbn | n≥0} is not regular. 4 marks

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

δ 0 1
→q1 q2 q3
q2 q3 q5
*q3 q4 q3
q4 q3 q5
*q5 q2 q5
4 marks

4(a) Define CFG. Design CFG's for the following languages:
i) L = {anb2n | 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.
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 = {anbn | 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(a) Multitape turing machine 4 marks

8(b) post's correspondence problem 4 marks

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

8(d) Chomsky hierarchy 4 marks

written 5 months ago by gravatar for vatsalmehta922 vatsalmehta9220
Please log in to add an answer.