Theory of Computation #12

Let’s take the rules from the beginning.

A -> eAee
A -> fBf
B -> g

The result should be:

A -> FI
I -> BF

A -> EJ
J -> AK
K -> EE

B -> g

E -> e
F -> f

Here’s the final code which stitches together all our functions:

(defn shorten-loop
  "Applies shorten-rule on a collection of rules"
  [coll]
  (loop [rest-fix coll
         index (int \I)
         result nil]
    (if (seq rest-fix)
      (recur
       (rest rest-fix)
       (+ index (dec (count (shorten-rule (first rest-fix) (char index)))))
       (into result (shorten-rule (first rest-fix) (char index))))
      result)))




(defn to-CNF
  "Takes a vector of rules in context free regular form and returns them
   as a hashmap in Chomsky normal form (CNF)."
  [input-strings]
  (let [filter-fn #(check-CNF (first (vals %)))
        filter-good (partial filter filter-fn)
        filter-bad (partial remove filter-fn)
        decomposed-input (map decompose-rule input)
        mixed-terminals (set (mapcat transform-terminals
                                     (filter-bad decomposed-input)))]
    (set (reduce into 
                 [(filter-good decomposed-input)
                 (filter-good mixed-terminals)
                 (shorten-loop (filter-bad  mixed-terminals))]))))
         


(with-test
  (def input ["A -> eAee"
              "A -> fBf"
              "B -> g"])
  (is (= (to-CNF input)
         #{{:J "AK"} {:I "BF"} {:E "e"} {:K "EE"} {:A "EJ"} {:F "f"} {:A "FI"} {:B "g"}}#{{:J "AK"} {:I "BF"} {:E "e"} {:K "EE"} {:A "EJ"} {:F "f"} {:A "FI"} {:B "g"}})))

And the result is:

{:A "FI"}
{:I "BF"}

{:A "EJ"}
{:J "AK"}
{:K "EE"}

{:B "g"}

{:E "e"}
{:F "f"}

Yay. This took a while.