Tutorial -1
Unit 3:Context Free Grammar
1. Let G be the grammar
S -> aB | bA
A -> a | aS | bAA
B -> b | bS | aBB
For string aaabbabbba, find Left most derivation and
Right most derivation.
2. Consider the grammar:
S -> aAS | a
A -> SbA | SS | ba
Derive left most and right most derivation of string
aabbaa using given grammar
3. Check whether the following grammars are ambiguous
or not. Justify your answer with proper reason.
i.
S → ABA
A → aA | Ʌ
B → bB | Ʌ
ii.
S→A|B
A → aAb | aabb
B → abB | Ʌ
4. Generate CFG to CNF
(i)
S -> AaA | CA | BaB
A ->aaBa | CDA | aa | DC
B -> bB | bAB | bb | aS
C -> Ca | bC | D
D -> bD | ɛ
Here ɛ represents null.
(ii)
S → TU | V T → aTb | Ʌ
U → cU | Ʌ
V → aVc | W
W → bW | Ʌ
5. Write unambiguous grammar for following grammar:
E→E+E|E-E|E^E|id
Here ^ represents Raise to power of operator
6. Give CFG for following languages:
1). L = a*b*
2). L = {an+2 b n | n >= 0}
7. Construct finite automata for following left linear
grammar:
S -> X0 | Y1
X -> Y1
Y -> Y0 | 1
8. Write CFG for the following languages :
i. {a ib j c k | i = j + k}
ii. ii. {a ib j c k | j = i or j = k}
9. Describe the language generated by the following
grammars:
i.
S → aA | bC | 𝑏
A → 𝑎𝑆 | bB
B → 𝑎𝐶 | bA | 𝑎
C → aB | bS
ii.
S → aT | bT | Ʌ
T → aS | bS