Theorem 4.4.4: For each right-linear grammar G, L(G) is regular.
Example 4.4.4. For the grammar of Example 4.4.3, G' = A _ aX1 | aY1, X1 _ bA, Y1 _ bB, B _ aZ1 | b, Z1 _ aZ2, Z2 _ aB
the construction in the proof of Theorem 4.4.4 yields the acceptor
A _ aY1 _ abB _ abb corresponds to the NFA run
_(A, abb) _ _(Y1, bb) _ _(B, b) _ {_}.
| Previous slide | Next slide | Back to first slide | View graphic version |