Exercise 23.10 [chomsky-form-exercise]

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.

View Answer