(c) δ
γ
( , ) ( , )
q a
p
=
(d) δ
γ
( , , ) ( , )
q a z
p
=
3. Say True or False
A language L is Context free Language, if there is a Pushdown automata
accepting.
4. A CFG is Unambiguous if,
(a) it contains uselss Nonterminals
(b) it produces more than one parse tree for some sentence
(c) it produces more than one derivation for some sentence
(d) Both b & c
5. S
aAa A SA A b
→
→
→
,
,
. The given grammar is in ............ normal
form.
(a) BNF (b) CNF (c) GNF (d) both a & b
GROUP II
6. Define PDA.
7. Show that the CFG with following production is Unambiguous.
S
S S
→
∈
( ) |
8. Let L be the language generated by the CFG with productions
S
S S S S S S S S S a
→ +
−
|
| * | / | ( ) |
How many derivation trees (Parse trees) are there fore the string a | a | a |
a | a | a ?
9. Write Instantaneous descriptions for the PDA generated in the Qn. No.
11 for accepting the sentence aabb.
10. Rewrite the grammar after removing Left recursion.
S
Aa b
A
Ac bd
→
→
|
|
GROUP III
Answer any 2 Ques tions
11. Convert the following grammar to GNF.
S
ASB
A aAS a
B
SbS A bb
→
∈
→
→
|
|
| |
University Question Papers
335