STUPIDSID
1 (a)
Give chomsky hierachy of grammar with examples.
5 M
1 (b)
State and explain any 5 closure properties of regular language.
5 M
1 (c)
Compare recursive and recursively enumerable language.
5 M
1 (d)
State and prove equivalence of NFA and DFA.
5 M
2 (a)
Design a DFA to accept strings over the alphabet set {a, b} that begin with 'aa' but not end with 'aa'.
10 M
2 (b)
Covert (0+\(\epsilon\)) (1 0)*(\(\epsilon\)+1) into NFA with \(\epsilon\)-moves and hence obtain a DFA.
10 M
3 (a)
Design a MOORE and MEALY machine to decrement a binary number.
10 M
3 (b)
Give statement of pumping lemma for regular sets and hence prove that {w c wR|W? (a+b)*} is not regular where wR is reverse of w.
10 M
4 (a)
Obtain leftmost derivation, rightmost derivation and derivation tree for the string "cccbaccba". The grammar us
S→Ssa|SSb|c
10 M
4 (b)
Design Turing machine as generator to add two binary numbers and hence simulate for "110+10". Hint: Assume two way infinite tape.
10 M
5 (a)
Design a PDA to accept language {an-1 b2n+1 | n≥1}.
10 M
5 (b)
Convert the below given grammar to Chomsky Normal Form (CNF) and Griebach Normal Form (GNF)
E→E+E|E*E|(E)|id
Consider "id" as a single terminal/symbol.
Consider "id" as a single terminal/symbol.
10 M
6 (a)
Design a Turing machine as acceptor for the language
{an bm|n, m≥0 and m≥n}.
{an bm|n, m≥0 and m≥n}.
10 M
6 (b)
Design PDA to check even parentheses over Σ={0,1}.
10 M
More question papers from Theoretical Computer Science