STUPIDSID
1 (a)
Define the following terms:
(i) Undecidability
(ii) Unrestricted Grammer
(iii) Pumping Lemma
(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.(ii) What is Myhill-Nerode theorem? Explain necessity of it.
10 M
2 (b)
Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101
S → 0B/1A
A → 0/0S/1AA
B → 1/1S/0BB
S → 0B/1A
A → 0/0S/1AA
B → 1/1S/0BB
10 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
3 (c)
Using pumping lemma prove L = {anbn | n≥1} is not regular or not.
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/IC
A→OS/IB/∈
B→1A/OC
C→OB/1S
(ii) S→OA/IC
A→OS/IB
B→OC/IB/∈
C→OB/IS
(i) S→OA/IC
A→OS/IB/∈
B→1A/OC
C→OB/1S
(ii) S→OA/IC
A→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 = {anbn | n≥1}
10 M
Write short notes on (any four)
7 (a)
Recursive and recursively enumerable languages.
5 M
7 (b)
Intractable Problems
5 M
7 (c)
Simplification of CFGs
5 M
7 (d)
Decision properties of regular languages.
5 M
7 (e)
Rice Theorem.
5 M
More question papers from Automata Theory