whenever the grammar has unit-production C
D
→ , then A B
⇒
*
holds
whenever there is a walk between A and B.
The new grammar $
G, equivalent to G is obtained by letting into $
P all
non-unit productions of P.
Then for all A and B satisfying A B
⇒
*
, we add to $
P
A
y y
y n
→ 1 2
|
|
|
KK
where B
y y
y n
→ 1 2
| |
|
KK
is the set of all rules in $
P with B on the left.
(c) Left Recursion Removal
A variable A is left-recursive if it occurs in a production of the form
A
Ax
→
for any x V T
∈ ∪
(
) .
*
A grammar is left-recursive if it contains at least one left-recursive
variable.
Every content-free language can be represented by a grammar that is not
left-recursive.
Ì Exam ple 2.4.1: Given a grammar G
A B a b c A P
= ({ , }, { , , }, , ) with
productions
A a aaA abBc
B
abbA b
→
→
|
|
| .
obtain an equivalent grammar $
G such that both G and $
G would accept the string
“aaabbc”.
Solu tion
Given G as
A a aaA abBc
→ |
|
(1)
B
abbA b
→
| .
(2)
Making use of (2) in (1), we have the grammar $
G with productions
A a aaA ababbAc abbc
B abbA b
→
→
|
|
|
| .
$
G is equivalent to G.
Thus the string “aaabbc” is derived as
A aaA aaabBc aaabbc
G
⇒
⇒
⇒
(
)
with
Con text-free Grammars
135