Question

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

$\begin{array}{l}A\to BAB|B|\epsilon \\ B\to 00|\epsilon \\ \end{array}$

Short answer

$$\begin{gathered} S\to BD\left|BB\right|AB\left|CC\right|BA|\epsilon \\ A\to BD|BB|AB|CC|BA \\ B|CC \\ C|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:

A$\to$BC

A$\to$a

Add a new start symbol S

S$\to$A

A$\to$BAB | B | $\epsilon$

B$\to$00 | $\epsilon$

Step 3: Remove ε-productions.

A $\to$$\epsilon$

$$\begin{gathered} B\to \epsilon \\ Remove,A\to \epsilon \\ S\to A|\epsilon \\ A\to BAB|BB|BB\mathfrak{R}00|\epsilon \\ RemoveB\to \epsilon \\ S\to A|\epsilon \end{gathered}$$