VTU Computer Science (Semester 5)
Formal Languages and Automata Theory
December 2012
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 a DFA and the languages accepted by it
5 M
1 (b) Design a DFA to accept a string of a's and b's not ending with abb
5 M
1 (c) Design a DFA which accept odd number of 0's and odd number os 1's
5 M
1 (d) Convert the following NFA to DFA:

5 M

2 (a) Write a note on application of finite automata
5 M
2 (b) Define an ?-NFA and ?-closure
4 M
2 (c) Prove that for every regular expression ,there exits a finite automation which accept the same language accepted for the regualar expression
4 M
2 (d) Give regular expression for the following languages;
L={W/W is an {a,b}* and |W| mod 3=0}
L={W/W is a string of even number of 0's followed by odd number of 1's }.
8 M

3 (a) Prove that regualar languages are closed under homomorphism
5 M
3 (b) State and prove that pumping lemma of regular languages
5 M
3 (c) Prove that the language L={WWR:W ?{a,b}*} is not regualar language
5 M
3 (d) Write a note on table filling method.When two states are equivalent or distinguishable?
5 M

4 (a) Define the following :
Leftmost derivation
Rightmost derivation
Sentential form
Parsing
5 M
4 (b) Design a context free grammer for the language L={W=WR:W is in {a,b}*}
5 M
4 (c) Design a context free grammer for the language L={a n b m c k where K=m+n,n,m,k ?0}
5 M
4 (d) Show how ambiguity in grammer are verified with an example
5 M

5 (a) Explain the working of PDA with a diagram
5 M
5 (b) Design a PDA for accepting a 2n b n
5 M
5 (c) Define two languages of a PDA .show that they are equivalent
5 M
5 (d) Convert the following CFG to PDA:
E ? E+E|E*E|id
5 M

6 (a) Define CNF .Give an example
5 M
6 (b) Define the following :
generating symbol
Reachable symbol
Unti production
Null production
Nullable production
5 M
6 (c) Convert the following CFG to CNF:
E ?E+E|E*E|(E)|id.
5 M

7 (a) Define a Turning machine .Expain the working of a turning machine
6 M
7 (b) Design a turning machine to accept a n b n c n
5 M
7 (c) Show that a multi tape TM is equivalent to a basic TM
6 M

8 (a) Write a detailed not on halting problem of Turning machine
6 M
8 (b) Prove that complement of a recursively enumerable language is recursive
6 M
8 (c) Write a note on universal Turing machine and show that simulate a computer
8 M



More question papers from Formal Languages and Automata Theory
SPONSORED ADVERTISEMENTS