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.
Examples:
(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.
(defn check-CNF "Checks if a string is already in CNF format" [string] (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.
(deftest test-check (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.
Continue tomorrow