STUPIDSID
Attempt any four sub-questions.
1 (a)
Design a DFA to accept only those strings containing a substring 'aa'.
5 M
1 (b)
Design a Moore machine for binary adder.
5 M
1 (c)
Give formal definition of a Push Down Automata.
5 M
1 (d)
Construct a Context Free Grammar for the language with equal number of a's and b's.
5 M
1 (e)
Give a regular expression for a language over the alphabet ?={a,b} containing at most two a's.
5 M
2 (a)
Design a DFA that accepts the strings over a binary alphabet that do not contain the substring 010.
10 M
2 (b)
Convert the following NFA to a reduced DFA.
10 M
3 (a)
What is a Mealy machine. Design a mealy machine to determine the residue mod 5 of a binary number.
10 M
3 (b)
Using pumping lemma prove that the following language is not regular
L={anbncn| n>=0}
L={anbncn| n>=0}
10 M
4 (a)
Find a regular expression RE corresponding to the following FA.
10 M
4 (b)
Design a Turing machine to recognize the language
L={1n2n3n | n>=1}
L={1n2n3n | n>=1}
10 M
5 (a)
What is Greibach Normal Form (GNF). Convert the following CFG to GNF.
S→Sab|Sba|ε
S→Sab|Sba|ε
10 M
5 (b)
Design a PDA for the language
L={WWR|W? {a,b}*}
L={WWR|W? {a,b}*}
10 M
Write short notes on:
6 (a)
Variants of Turning Machines.
10 M
6 (b)
Recursive and Recursively enumerable languages.
10 M
6 (c)
Chomsky Hierarchy.
10 M
6 (d)
Halting Problem.
10 M
More question papers from Automata Theory