question.md

In this exercise you will transform $\large \varepsilon_0$ into Chomsky Normal Form (CNF). There are five steps: (a) Add a new start symbol, (b) Eliminate $\epsilon$ rules, (c) Eliminate multiple words on right-hand sides, (d) Eliminate rules of the form (${\it X} \rightarrow{{;}}$${\it Y}$), (e) Convert long right-hand sides into binary rules.

1. The start symbol, $S$, can occur only on the left-hand side in CNF. Replace ${\it S}$ everywhere by a new symbol ${\it S'}$ and add a rule of the form ${\it S}$ ${{;}}\rightarrow{{;}}$${\it S'}$.
   

2. The empty string, $\epsilon$ cannot appear on the right-hand side in CNF. $\large \varepsilon_0$ does not have any rules with $\epsilon$, so this is not an issue.
   

3. A word can appear on the right-hand side in a rule only of the form (${\it X}$ ${{;}}\rightarrow{{;}}$word). Replace each rule of the form (${\it X}$ ${{;}}\rightarrow{{;}}$…word …) with (${\it X}$ ${{;}}\rightarrow{{;}}$…${\it W'}$ …) and (${\it W'}$ ${{;}}\rightarrow{{;}}$word), using a new symbol ${\it W'}$.
   

4. A rule (${\it X}$ ${{;}}\rightarrow{{;}}$${\it Y}$) is not allowed in CNF; it must be (${\it X}$ ${{;}}\rightarrow{{;}}$${\it Y}$ ${\it Z}$) or (${\it X}$ ${{;}}\rightarrow{{;}}$word). Replace each rule of the form (${\it X}$ ${{;}}\rightarrow{{;}}$${\it Y}$) with a set of rules of the form (${\it X}$ ${{;}}\rightarrow{{;}}$…), one for each rule (${\it Y}$ ${{;}}\rightarrow{{;}}$…), where (…) indicates one or more symbols.
   

5. Replace each rule of the form (${\it X}$ ${{;}}\rightarrow{{;}}$${\it Y}$ ${\it Z}$ …) with two rules, (${\it X}$ ${{;}}\rightarrow{{;}}$${\it Y}$ ${\it Z'}$) and (${\it Z'}$ ${{;}}\rightarrow{{;}}$${\it Z}$ …), where ${\it Z'}$ is a new symbol.
   

Show each step of the process and the final set of rules.