I am still having some doubts when it comes to Context-Free Grammar to Chomsky Normal Form conversion. Here is what I did for the following CFG:
$S \rightarrow bXb \ |\ bS \ |\ \epsilon\ |\ aSdSc$
$X \rightarrow aX \ |\ Xtt$
$Y \rightarrow tt \ |\ SbS\ | \ \epsilon$
Before I started, I already see that Y is not reachable from the start state and the symbol X won’t be producing a string. I will remove them after finishing with the unit productions removal step.
Step1: Add new start state:
$S_{0} \rightarrow S$
$S \rightarrow bXb \ |\ bS \ |\ \epsilon\ |\ aSdSc$
$X \rightarrow aX \ |\ Xtt$
$Y \rightarrow tt \ |\ SbS\ | \ \epsilon$
Step 2: Remove $\epsilon$ rules ($Y\rightarrow \epsilon$, $S\rightarrow \epsilon$):
$S_{0} \rightarrow S \ |\ \epsilon$
$S \rightarrow bXb \ |\ bS \ |\ aSdSc \ |\ b \ |\ adSc \ |\ aSdc \ |\ adc$
$X \rightarrow aX \ |\ Xtt$
$Y \rightarrow tt \ |\ SbS\ |\ bS \ |\ Sb \ |\ b$
Step 3a: Remove unit productions $S_{0}\rightarrow S$:
$S_{0} \rightarrow bXb \ |\ bS \ |\ aSdSc \ |\ b \ |\ adSc \ |\ aSdc \ |\ adc \ |\ \epsilon$
$S \rightarrow bXb \ |\ bS \ |\ aSdSc \ |\ b \ |\ adSc \ |\ aSdc \ |\ adc$
$X \rightarrow aX \ |\ Xtt$
$Y \rightarrow tt \ |\ SbS\ |\ bS \ |\ Sb \ |\ b$
Step 3b: Remove useless symbols and productions, etc.:
$S_{0} \rightarrow bS \ |\ aSdSc \ |\ b \ |\ adSc \ |\ aSdc \ |\ adc \ |\ \epsilon$
$S \rightarrow bS \ |\ aSdSc \ |\ b \ |\ adSc \ |\ aSdc \ |\ adc$
Step 4: Eliminate more than two non-terminals on RHS:
$H \rightarrow b$, $A \rightarrow a$, $D \rightarrow d$, $C \rightarrow c$.
bS becomes HS.
aSdSc becomes ASDSC then EFC which then becomes GC, where $E \rightarrow AS$, $F \rightarrow DS$ and $G \rightarrow EF$.
adSC becomes ADSC then it becomes IJ, where $I \rightarrow AD$, and $J \rightarrow SC$.
aSdc becomes ASDC then it becomes EK, where $K \rightarrow DC$.
Lastly, adc becomes ADC and then IC.
Therefore, the final resul is:
$S_{0} \rightarrow HS \ |\ GC \ |\ b \ |\ IJ \ |\ EK \ |\ IC \ |\ \epsilon$
$S \rightarrow HS \ |\ GC \ |\ b \ |\ IJ \ |\ EK \ |\ IC$
$E \rightarrow AS$
$F \rightarrow DS$
$G \rightarrow EF$
$I \rightarrow AD$
$J \rightarrow SC$
$K \rightarrow DC$
$H \rightarrow b$
$A \rightarrow a$
$D \rightarrow d$
$C \rightarrow c$
Did I do this correctly?
