Question

Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9.

$$\begin{gathered} \mathit{A}\mathbf{\to }\mathit{B}\mathit{A}\mathit{B}\mathbf{\left|}\mathit{B}\mathbf{\right|}\mathit{\epsilon } \\ \mathit{B}\mathbf{\to }\mathbf{00}\mathbf{|}\mathit{\epsilon } \end{gathered}$$

Short answer

Answer

$$\begin{gathered} S\to BD\left|BB\right|AB\left|CC\right|BA|\epsilon \\ A\to BD|BB\left|AB\right|CC|BA \\ B\to CC \\ C\to 0 \\ D\to AB \end{gathered}$$

Step-by-step solution

Define Chomsky Normal Form (CNF)

In theory of computation, context free grammar (CFG) generates the possible strings in a language. CFG is in Chomsky normal form (CNF) if the production rules in it are of the following forms:

$$\begin{gathered} A\to BC \\ A\to a \end{gathered}$$

Add a new start symbol S

$$\begin{gathered} S\to A \\ A\to BAB\left|B\right|\epsilon \\ B\to 00|\epsilon \end{gathered}$$

Remove ε-productions.

The two ε-productions are:

$$\begin{gathered} A\to \epsilon \\ B\to \epsilon \\ Remove,A\to \epsilon \\ S\to A|\epsilon \\ A\to BAB|BB\odot 00|\epsilon \\ RemoveB\to \epsilon \\ S\to A|\epsilon \\ A\to BAB\left|AB\right|BA\left|BB\right|B|\epsilon \\ B\to 00 \\ A\to \epsilon iscreatedagain. \\ RemoveA\to \epsilon \\ A\to BAB|BB\left|AB\right|B\left|BA\right|\epsilon \\ B\to 00 \\ RemoveA\to \epsilon again. \\ S\to A|\epsilon \\ A\to BAB|BB\left|AB\right|B|BA \\ B\to 00 \end{gathered}$$

Remove the unit productions.

The two-unit productions are:

$$\begin{gathered} S\to A \\ RemoveS\to A. \\ S\to BAB\left|BB\right|AB\left|B\right|BA|\epsilon \\ A\to BAB|BB\left|AB\right|B|BA \\ B\to 00 \\ RemoveS\to B. \\ S\to BAB|BB\to \left|AB\right|00\left|BA\right|\epsilon \\ A\to BAB\left|BB\right|AB\left|B\right|BA3 \\ B\to 00 \\ RemoveA\to B \\ S\to BAB\left|BB\right|AB\left|00\right|BA|\epsilon \\ A\to BAB|BB\left|AB\right|00|BA \\ B\to 00 \end{gathered}$$

Add new variables

$$\begin{gathered} S\to BD\left|BB\right|AB\left|CC\right|BA|\epsilon \\ A\to BD|BB\left|AB\right|CC|BA \\ B\to CC \\ C\to 0 \\ D\to AB \end{gathered}$$