Convert grammar into Chomsky Normal Form

Question

I am trying to convert grammar into Chomsky Normal Form (CNF) but something is going wrong. I need some help. Can someone explain it, please? Here is grammar:

S $\rightarrow$ aSc|X

X $\rightarrow$ aXb|$\lambda$

Thanks in advance!

Answer 1

Following exactly the steps on Wikipedia, we have the following:

$\textbf{START}$

Since the start symbol $S$ appears on the right hand side of a rule, we must introduce a new start symbol $S_0$, so we have the rules

$S_0\to S$

$S\to aSc\mid X$

$X\to aXb\mid\lambda$

$\textbf{TERM}$

Next, we replace each of the terminal symbols $a$, $b$, $c$, and $d$ with nonterminal symbols $A$, $B$, $C$, and $D$ and add the rules $A\to a$, $B\to b$. $C\to c$, and $D\to d$. Then we now have

$S_0\to S$

$S\to ASC\mid X$

$X\to AXB\mid\lambda$

$A\to a$

$B\to b$

$C\to c$

$D\to d$

$\textbf{BIN}$

Next, we want to split up the rules $S\to ASC$ and $X\to AXB$ into rules with only two nonterminals on the right hand side. To do this, we introduce new nonterminal symbols, $S_1$ and $X_1$ and replace $S\to ASC$ and $X\to AXB$ with the new rules $S\to AS_1$, $S_1\to SC$, $X\to AX_1$, and $X_1\to XB$. Then we now have

$S_0\to S$

$S\to AS_1\mid X$

$S_1\to SC$

$X\to AX_1\mid\lambda$

$X_1\to XB$

$A\to a$

$B\to b$

$C\to c$

$D\to d$

$\textbf{DEL}$

Next, we want to remove any $\lambda$-rules, namely $X\to\lambda$. In order to do this while making sure the grammar generates the same language, we need to determine the set of nullable nonterminals (see Wikipedia). It follows immediately from the definition that the nullable nonterminals are $X$, $S$, and $S_0$ (although $S_0$ does not appear on the right hand side of any rule, so it does not matter that $S_0$ is nullable). So, we introduce a new rule for every rule which has a nullable nonterminal on the right hand side by deleting the nullable nonterminal. This yields

$S_0\to S\mid\lambda$

$S\to AS_1\mid X\mid\lambda$

$S_1\to SC\mid C$

$X\to AX_1\mid\lambda$

$X_1\to XB\mid B$

$A\to a$

$B\to b$

$C\to c$

$D\to d$

After that, we can simply remove every rule of the form $Y\to\lambda$ for any nonterminal $Y$ with $Y\neq S_0$. So, we have

$S_0\to S\mid\lambda$

$S\to AS_1\mid X$

$S_1\to SC\mid C$

$X\to AX_1$

$X_1\to XB\mid B$

$A\to a$

$B\to b$

$C\to c$

$D\to d$

$\textbf{UNIT}$

Finally, we want to remove all the unit rules (i.e. rules of the form $Y\to Y'$ where $Y$ and $Y'$ are nonterminals). To do this, we first need to repeatedly add a new rule for every unit rule $Y\to Y'$ and every rule starting with $Y'$. In our case, the unit rules are $S_0\to S$, $S\to X$, $S_1\to C$, and $X_1\to B$. Since we have $S_0\to S$ and $S\to AS_1$ as rules, we need to add the rule $S_0\to AS_1$. By the same reasoning, we need to add the rules $S_0\to X$, $S\to AX_1$, $S_1\to c$, and $X_1\to b$. But now there is a new unit rule! Since the new unit rule $S_0\to X$, has been added, we repeat the process to get the new rule $S_0\to AX_1$. This time, there were no new unit rules, so we finish by deleting every unit rule, and get

$S_0\to AS_1\mid AX_1\mid\lambda$

$S\to AS_1\mid AX_1$

$S_1\to SC\mid c$

$X\to AX_1$

$X_1\to XB\mid b$

$A\to a$

$B\to b$

$C\to c$

$D\to d$

And hence, this is a new context-free grammar in Chomsky normal form which generates the same language as the original. I tried to make this as detailed as possible, but let me know if you need further explanation on any of the steps.