Example 4.3.1.The grammar with productions S ___ | SaSbS becomes
S _ SaSbS | aSbS | SabS | SaSb | abS | aSb | Sab | ab.
Definition 4.3.2: A production A _ B is a unit rule if both A and B are variables.
Theorem 4.3.2: every context-free grammar is equivalent to one with no unit productions.
Example 4.3.2.The productions A _ aA | B, B _ bB | C, C _ cC | _ are first transformed by eliminating A _ B into A _ aA | bB| cC | _, B _ bB | C, C _ cC | _and then by eliminating B _ C into A _ aA | bB | cC | _, B _ bB | cC | _, C _ cC | _.
Previous slide | Next slide | Back to first slide | View graphic version |