I'm trying to prove that the following CFG can be converted to a CNF:
S -> aAB A -> aAa A -> bb B -> a
Here below is how I've managed so far:
Step 1: add a new start state
S0 -> S S -> aAB A -> aAa A -> bb B -> a
Step 2: remove epsilon rules
There are no such rules in this CFG.
Step 3: remove non-terminal to non-terminal rules
Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:
S0 -> aAB S -> aAB A -> aAa A -> bb B -> a
S0 -> BC S -> BC A -> BF | EE (A -> aAa and A -> bb in one line) B -> a C -> AB E -> b F -> AB
So this is where I got confused. I have now both
F that go to
AB. If I've done this correctly that would mean that either
F can simply be removed. Or, of course, I've done something wrong in this procedure.