STUPIDSID
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 }.
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
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
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
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.
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