1.
Give a formal definition of Context Free Grammar
2. Consider the CFG: G={ (S,A), (a,b), P, S } where P consists of S -> aAS|a , A -> SbA| SS | ba
Derive string “aabbaa” using leftmost and rightmost derivation.
3. Grammar G is defined as
S -> aB | bA
A -> a| aS| bAA
B -> b| bS | aBB
S is a start symbol. Write leftmost and rightmost derivation for the string “bbaaba”.
4. For the following grammar give leftmost and rightmost derivation for string “aaabbb”
S -> aSb | ab
5. Grammar: S → S + S
S→S*S
S → (S)
S→a
Draw a derivation tree for the following string : “a + a * a + a”using leftmost and right most
derivation
6. Grammar: S → (S)
S→a
Give a derivation tree for the following string: ((a))
7. Grammar: E→E+E
E → (E)
E → id
String: (id + id) + id
Draw left and right derivation tree / parse tree for the above string.
8. Define Ambiguous Grammar and give its example.
9. What is CFL? Explain with an example.
10. Find the CFL generated by following grammar:
S → aSb
S → aSbb
S → ab
11. Find the CFL generated by following grammar:
S → aSa
S → bSb
S → ab
S → ba
12. Find the CFL generated by following grammar:
S → aS
S → aSb
S→ε
13. Find the CFL generated by following grammar:
S → aSbS
S → bSaS
S→ε
14. Write the grammar generating all strings consisting of a’s and b’s with at least two a’s.
15. Write a grammar for the language over ∑ = {a,b} containing at least one occurrence of “aa” .
16. Write a CFG that generates language L denoted by (a+b)* bbb (a+b)*
17. Consider the grammar having productions:
S → aS | ε
S → aSbS
The grammar is ambiguous. Show in particular that the string aab has two parse trees.
18. Let G be the grammar:
S → aB | bA
A → a | aS | bAA
B → b | bS | aBB
For string aaabbabbba find:
(i) Left most derivation
(ii) Right most derivation
(iii) Parse Tree
(iv) Is the grammar unambiguous? Check by drawing 2 different parse trees for the string
aababb
19. Simplify the grammar by removing epsilon production:
S → AB | C
A → aA | ε
B → bB | ε
C→c
20. Simplify the grammar by removing epsilon production:
S → aSbS | bSaS | ε
21. Simplify the grammar by removing epsilon production:
S→ABC|D
A → aA | ε
B → bB | ε
C → cC | ε
D → AB | d
22. Simplify the grammar by eliminating unit production:
S→A|b
A→B|a
B→b
23. Simplify the grammar by eliminating unit production:
S→A|B|a
A→B|C
B→C|b
C→D|c
D→a
24. Simplify the grammar by eliminating useless symbols:
S → AB | BC | a
A → aA | a
B → bB | C
C→D
D→d
E → eE | e
F→G
G→F
25. Simplify the grammar by eliminating useless symbols:
S → AB | a
A → aA | B
B→C
C→B
D→d
26. Express the following grammar using CNF:
S->ABA
A->aA|ε
B->bB|ε
Note: Simplify the grammar first if needed and then convert to CNF
27. Express the following grammar using CNF:
S → aBC | b
B → bB | b
C→c
Note: Simplify the grammar first if needed and then convert to CNF
28. Convert the following CFG to GNF
S → AB | b
A → aA | a
B → bB | b
29. Convert the following CFG to GNF
S → aS | AB
A→a
B → bB | b
30. Explain the closure properties of CFL.
31. Applications of CFG: