STUPIDSID
1(a)
Define the following terms:(i) Undecidability(ii) Unrestricted Grammer(iii) Pumping Lemma
5 M
1(b)
Define TM and give its variants.
5 M
1(c )
Explain Chomsky hierarchy for formal languages.
5 M
1(d)
Give the closure properties of regular languages.
5 M
2(a)
(i) What is ambiguous CFG? Give one example.
5 M
2(a)
(ii) What is Myhill-Nerode theorem? Explain necessity of it.
5 M
2(b)
Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101S ? 0B/1AA ? 0/0S/1AAB ? 1/1S/0BB
10 M
3 (c)
Using pumping lemma prove L = {anbn | n>=1} is not regular or not.
5 M
3(a)
Explain CNF and GNF with example.
10 M
3(b)
Give the formal definition of RE and Design DFA consisting of (a+b)*aba( a + b )*
5 M
4(a)
Write NFA for accepting (a+bb)*(ba*+ ?)
10 M
4(b)
Explain DPDA and NPDA with languages of them.
10 M
5(a)
Find the languages defined by the following grammar:(i) S?OA/ICA?OS/IB/? B?1A/OCC?OB/1S(ii) S?OA/ICA?OS/IB B?OC/IB/?C?OB/IS
10 M
5(b)
Construct PDA of accepting the following language L = { anbman | m,n >=1}
10 M
6(a)
Differentiate between Moore and Mealy machine with proper example and usage. Carry out comparison of Moore MIC to Mealy MIC.
10 M
6(b)
Design a Turing Machine to accept the language L = {an bn | n>=1 }
10 M
7 (c)
Simplification of CFGs
5 M
Write short notes on any FOUR:-
7(a)
Recursive and recursively enumerable languages.
5 M
7(b)
Intractable Problems
5 M
7(d)
Decision properties of regular languages.
5 M
7(e)
Rice Theorem
5 M
More question papers from Theory of Computer Science