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.
S -> xSyy
S -> zNz
N -> x
So we how would this look in CNF?
S -> XA
A -> SB
B -> YY
S -> ZC
C -> NZ
N -> x
X -> x
Y -> y
Z -> z
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.
(check-CNF "XA") -> true
(check-CNF "xA") -> false
(check-CNF "x") -> true
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.
"Checks if a string is already in CNF format"
(let [length (count string)]
(cond (> length 2) false
(= length 2) (every? #(Character/isUpperCase %) string)
(= length 1) (Character/isLowerCase (first string))
:else false )))
We also write a few tests which all work fine. Great.
(is (= (check-CNF "XA") true))
(is (= (check-CNF "XAA") false))
(is (= (check-CNF "xA") false))
(is (= (check-CNF "x") true)))
Although it doesn’t look like much it saved us time.