A → a,
where A, B, C are in V, and a is in T.
Example 6.7
The grammar
is in Chomsky normal form. The grammar
is not; both productions S → AAS and A → aa violate the conditions of
Definition 6.4.
Theorem 6.6
Any context-free grammar G = (V, T, S, P) with λ ∉ L (G) has an equivalent
grammar
in Chomsky normal form.
Proof: Because of Theorem 6.5, we can assume without loss of generality that G
has no λ-productions and no unit-productions. The construction of will be
done in two steps.
Step 1: Construct a grammar G 1 = (V 1 ,T, S, P 1 ) from G by considering all
productions in P in the form
where each x i is a symbol either in V or in T. If n = 1, then x 1 must be a terminal
since we have no unit-productions. In this case, put the production into P 1 . If n ≥
where A, B, C are in V, and a is in T.
Example 6.7
The grammar
is in Chomsky normal form. The grammar
is not; both productions S → AAS and A → aa violate the conditions of
Definition 6.4.
Theorem 6.6
Any context-free grammar G = (V, T, S, P) with λ ∉ L (G) has an equivalent
grammar
in Chomsky normal form.
Proof: Because of Theorem 6.5, we can assume without loss of generality that G
has no λ-productions and no unit-productions. The construction of will be
done in two steps.
Step 1: Construct a grammar G 1 = (V 1 ,T, S, P 1 ) from G by considering all
productions in P in the form
where each x i is a symbol either in V or in T. If n = 1, then x 1 must be a terminal
since we have no unit-productions. In this case, put the production into P 1 . If n ≥