9. Define ‘derivation tree’.
10. When is an ordered tree said to be a derivation tree?
11. What do you mean by sentential form?
12. What is a partial derivation tree?
13. Explain (a) Rightmost (b) Leftmost and (c) Mixed derivation.
14. What do you mean by the terms
(a) Parsing
(b) Ambiguity.
15. What do you mean by exhaustive search parsing?
16. Distinguish between top-down and bottom-up parsing.
17. Define the terms:
(a) Ambiguous Grammar (b) Ambiguous Language.
18. What do you mean by inherantly ambiguous language?
19. Explain the method of simplifying a CFG.
20. State the substitution rule.
21. How will you abolish useless production in CFG?
22. What do you mean by empty production removal? Explain with an
example.
23. State the procedure to find CFG without λ-productions.
24. What do you mean by unit production removal?
25. What do you mean by left recursion removal?
26. What are the kinds of Normal Forms?
27. What do you mean by Chomsky Normal Form (CNF)?
28. State the procedure to find equivalent grammar in CNF.
29. What do you mean by Greibach Normal Form (GNF).
30. When is a CFG said to be in GNF?
EXERCISES
1. Generate the Context-Free Grammars that give the following languages.
(a) {w | w contains at least three 1s}
(b) {w | w starts and ends with the same symbol}
(c) {w | the length of w is odd}
(d) {w | w = w
R , that is, w is a palindrome}
2. Determine the CFG that generates the following languages.
(a) The set of strings over the alphabet {a, b} with twice as many a’s as
b’s.
(b) The complement of the language {a
n b
n | n ≥ 0}
3. Determine a derivation tree of a b a b
*
*
+
given that a b a b
*
*
+
is in
L G
( ) where G is given by the productions S
S S S S a b
→ + | * | | .
150
Theory of Automata, Formal Languages and Computation