in Books, Doing Books, Theory of Computation

Theory of Computation #10

Exercise 2.6.3P: Write a program to convert context-free grammars that do not generate the empty string into grammars in Chomsky normal form.

Again, a challenging problem. The choice of the data structure will be very important I think. Let’s start with an example.

So we how would this look in CNF?

We basically do two operations. The first step is to guarantee that the right-hand side is either only a terminal or consists of two terminals.

Let’s write a function for that. This function will return true if it’s already in CNF otherwise false.


Ok, we take a string and check two things. First, the length has to be less or equal 2. And then if the length is 2 if all characters are uppercase. And if the length is one, if the character is lowercase.

We also write a few tests which all work fine. Great.

Although it doesn’t look like much it saved us time.

Continue tomorrow

Write a Comment