I'm trying to learn how to convert a Context Free Grammar to Chomsky Normal form, but I'm getting stuck on removing the null transitions.

The Grammar is:

S -> TTS | a
T -> bTb |aa| ε

I've tried this:

1.) Add a new start variable

S' -> S
S -> TTS | a
T -> bTb |aa| ε

2.) Remove T -> ε

I see that T appears on the right side in the third step, and the second step. I'm confused about what to do here, I've tried this:

S' -> S
S -> TS | a | T
T -> bb |aa| b  

Where a b is added on the third line, because if the T is removed, then we're left with a b

And where a T is added on the second line because if a T s removed, then we're left with another T

I'm not sure I'm doing this right, and I'm getting pretty confused in regards to how to do it.

How would I continue from here?

Any help would be much appreciated!


First, your conversion is not correct. $b$ is not in the language at first, but after your conversion it is. ($S'\rightarrow S\rightarrow T \rightarrow b$)

Second, there are several ways to do this conversion. I can show you one, but this may not necessarily be the one you learned.

Your first step is correct.

For your second step: We remove $T\rightarrow \varepsilon$. To ensure the language stays the same, we must search for all $T$ on the right side and add a new rule without the $T$. The general idea is as follows: With that CFG we could have $T\rightarrow bTb \rightarrow bb$. What we want to do is get rid of that epsilon transition by turning those two steps into one. Another example: $S\rightarrow TTS \rightarrow TS \rightarrow S \rightarrow a$. We again replace the epsilon rule by turning the first two/first three steps into one.

That gives the rule $T\rightarrow bTb | aa|bb$. Note the we must keep all transitions except the epsilon transitions.

For the other transition it's not the best example to explain. So first, again we keep all old transitions. $S\rightarrow TTS|a$. However, we have $T$ on the right side, so we must consider what happens if some $T$ were $\varepsilon$. If the first $T$ were epsilon, we get $S\rightarrow TS$, so we add that to get $S\rightarrow TTS|a|TS$. What happens if the second $T$ is $\varepsilon$? Well, just remove it and we again get $S\rightarrow TS$, which we already have (note that it's very important to consider what happens upon reamoving each $T$. Just in this case it does not matter, because the $T$ appear right next to each other). Lastly, we must also consider what would happen if both $T$ were $\varepsilon$. Then we get $S\rightarrow S$ which we could also add, but it's a useless transition that does not do anything, so we might just not add it as well. This leaves us with:

$S'\rightarrow S$

$S\rightarrow TTS|TS|a$

$T\rightarrow bTb|aa|bb$

Lastly for CNF, we must make sure all transitions have either one symbol or two variables on the right.

First, let's pull $S\rightarrow TTS$ apart. For that, introduce a new variable $T'$ with $T'\rightarrow TT$. By adding we can remove $S\rightarrow TTS$ if we add $S\rightarrow T'S$.

Another "bad" transition is $T\rightarrow aa$. The "trick" for removing concatenations of symbols on the right side is to introcude another variable that leads to that symbol. So we add $A\rightarrow a$ to replace $T\rightarrow aa$ by $T\rightarrow AA$. In the same way we add $B\rightarrow b$ and turn $T\rightarrow bb$ into $T\rightarrow BB$ and turn $T\rightarrow bTb$ into $T\rightarrow BTB$.

Lastly, we must pull apart $T\rightarrow BTB$ again. To do that, just add $C\rightarrow BT$ and replace $T\rightarrow BTB$ with $T\rightarrow CB$.

The CNF we're left with finally is:

$S'\rightarrow S$

$S\rightarrow T'S|TS|a$

$T\rightarrow CB|AA|BB$

$T'\rightarrow TT$

$A\rightarrow a$

$B\rightarrow b$

$C\rightarrow BT$

This grammer now prduces the exact same language as the grammar initially given, but is in CNF. This may seems kind of clunky, but this very simple and restricted form makes it so you can run some useful algorithms on this later :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.