and S
abAB ba
A aaa
B
aA bb
→
→
→
| ,
,
|
are equivalent.
22. Eliminate all the λ-productions from
S
AaB aaB
A
B
bbA
→
→
→
|
,
| .
λ
λ
23. Say whether the following grammars are in CNF:
(a) S
AS a
A SA b
→
→
|
|
;
(b) S
AS AAS
A SA aa
→
→
|
,
| .
24. Convert the grammar S
aSb ab
→
| into Chomsky Normal Form.
25. Convert the grammar with productions
S
abAB
A bAB
B
BAa A
→
→
→
,
| ,
| |
λ
λ
into Chomsky Normal Form.
26. Give a grammar with no ∈- or unit productions generating the set
L G
( ) { },
− ∈ where G is the grammar
S
aSbb T
T
bTaa S
→
→
∈
| ,
| | .
27. Give grammars in Chomsky Normal Form for the following CFGs.
(a) {a, b}
* -(palindromes)
(b) {
| , ,
,
}
a b c k m n
k n
k m n
≥
≥
1 2
(c) {
| ,
}
a b a k n
n k n
≥1
(d) {
| ,
}
a b c k n
n
n k
2
1
≥ .
SHORT-QUESTIONS AND ANSWERS
1. Define a Context-Free Grammar (CFG).
A context-free grammar is a 4-tuple (V, T, S, P) where
(i) V is a finite set called the variables
(ii) T is a finite set, disjoint from V, called the terminals.
(iii) P is a finite set of rules, with each rule being a variable and a
string of variables and terminals, and
(iv) S V
∈ is the start variable.
Con text-free Grammars
153