STUPIDSID
1 (a)
Differentiate between NFA and DFA.
5 M
1 (b)
State and Explain closure properties of Context Free Language.
5 M
1 (c)
Explain with an example the Chomsky hierarchy.
5 M
1 (d)
Compare recursive and recursively enumerable language.
5 M
2 (a)
Construct PDA accepting the language L={anbn |n>0}.
10 M
2 (b)
Design minimized DFA for accepting strings ending with 100 over alphabet (0,1).
10 M
3 (a)
Convert (0+ε)(10)*(ε+1) into NFA with e-moves and obtains DFA.
10 M
3 (b)
Construct Turing machine that accepts the string over ?=(0,1) and convert every occurrence of 111 to 101.
10 M
4 (a)
Convert following Grammar to CNF and GNF
S→ASB/a/bb
A→aSA/a
B→Sbs/bb
S→ASB/a/bb
A→aSA/a
B→Sbs/bb
10 M
5 (a)
Design Moore Machine to generate output A if string is ending with abb, B if string ending with aba and C otherwise over alphabet (a,b) and convert it to Mealy machine.
10 M
5 (b)
Construct TM to check wellformed ness of parenthesis.
10 M
Write short notes on:
6 (a)
Rice theorem
5 M
6 (b)
Variants of Turing Machine.
5 M
6 (c)
Applications of Regular Expression
5 M
6 (d)
Difference between PDA and NPDA
5 M
More question papers from Theoretical Computer Science