Seonglae ChoProductions are one of the following two forms / A→ BC or A → σ
so A → α, α has at most two symbols; namely, |α| ≤ 2 (α is sentential form)
Claim
for every CFL L, there exists a CFG in CNF for L
Proof
First, eliminate λ-productions and then unit productions from G. Then, the new production rules are
Step 1. We introduce new variables Ba,Bb,Bc,··· Bt for terminals in (c) and (d)
Change terminal t as Bt and add production Bt → t
Step 2. We introduce additional variables for A → α ∈ V* , where |α|≥ 3
ex. S → ABC to S → AF, F → BC