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 w

^{R}|W? (a+b)*} is not regular where w^{R}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 {a

^{n-1}b^{2n+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

{a

{a

^{n}b^{m}|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