# 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)
decomposed-input (map decompose-rule input)
mixed-terminals (set (mapcat transform-terminals
(set (reduce into
[(filter-good decomposed-input)
(filter-good 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.