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.

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