CNF (Chomsky normal form)


Productions 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
<details><summary>

**Proof**</summary>

First, eliminate λ-productions and then unit productions from G. Then, the new production rules are
![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F81cb7f11-1c5e-466d-9c6f-150941f76f8f%2FUntitled.png?table=block&id=97672954-9d17-4068-9b70-01d6d8fd2f87&cache=v2)
**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 |α|≥ 3ex. S → ABC to S → AF, F → BC
</details>











