Lemma 4.4.3: For each right-linear grammar G = (V, _, P, S), there is an equivalent right-linear grammar G' = (V', _, P', S) so each non-terminating production A _____P' has len(_) Š 2, and each terminating production A _ x _ P' has len(x) Š 1.
Example 4.4.3. According to Lemma 4.4.3, a right-linear grammar such as
G = A _ abA | abB, B _ aaaB | b
is transformed into the equivalent grammar
G' = A _ aX1 | aY1, X1 _ bA, Y1 _ bB, B _ aZ1 | b, Z1 _ aZ2, Z2 _ aB.
Grammars in this form can then be directly used to define the transitions in an acceptor that mimics their behavior.
| Previous slide | Next slide | Back to first slide | View graphic version |