4. State and distinguish halting problem and Unsolvability.
GROUP II
5. State the Kleene’s theorem (not the corollary) and give the proof with
neat sketch wherever necessary.
6. State the rules for a Context Free Grammar to be in Chomsky Normal
form. Find a CFG G’ in CNF generating L(G)—{ε}, where G has a
productions of
S
AaA CA BaB
A aaBa CDA aa DC
B
bB bAB bb As C Ca bC
→
→
→
→
/
/
/
/
/
/
/ /
/
/ D
D bD
→
/ ε
7. Consider the CFG with productions
S
S
S
S T T T
T F F
F
S
a
→
→
+
→
→
1
1
1
1
$
/
* /
( ) /
(a) Write the CFG obtained from this one by eliminating left recursion.
(2)
(b) State the rules for DPDA and give a transition table for a DPDA
that acts as a top down parser for this language.
8. Define Universal TM.
Show that a language L ⊆ Σ
* is recursively enumerable (i.e., can be
accepted by some TM) if and only if L can be enumerated by some TM.
9. State and prove Rice’s Theorem.
THEORY OF COMPUTING
Time : 90 Mts.
Max Marks: 30
TEST II
GROUP I
1. The CFG defined by ab* is
(a) S
Sb a
→ |
(b)
S
XY
X
ax
Y
by
→
→
→
(c) C
SS baa abb
S
→
→ ∈
|
|
(d) S
aS bS
→ |
2. The transition function of PDA is defined as
(a) δ
γ
( , , ) ( , )
q a z
p
=
(b) δ
γ
( , ) ( , )
q z
p
=
334
Theory of Automata, Formal Languages and Computation