Finite Automata

I did some pictures of automata to go with this post, but Google have managed to bugger up 'Insert Image' in Blogger, which used to be easy.

I wonder if their monkeys are even interested in whether their filthy javascript crap actually works before they inflict it on people.

God I hate them. They've gone from 'Don't be evil / Awesome' to 'We own you now / But we can't program any more' in a couple of years.

I'd really like to move this blog somewhere less incompetent. Anyone got any suggestions?

You'll just have to imagine what the pictures look like. Think bubbles and arrows.

;; Finite Automata

;; I just did Jeff Ullmann's Stanford Course 'Automata' through Coursera. It was fascinating.

;; A finite automaton is a mathematical model representing a simple
;; computer. But it's very close to being a computer.  In fact you can
;; code them up in Verilog and make them out of silicon. In chip
;; design they're known as finite state machines.

;; They're strictly less powerful than real computers and programs,
;; but they can still do lots of stuff.  On the other hand, we can
;; determine what it is that they do much more easily than we can with
;; computers and programs.

;; Here's an example of an automaton

;; Start at A
;; A -0-> A
;; A -1-> B
;; B -1-> B
;; B -0-> A
;; B is an accepting state

;; INSERT IMAGE automaton1.png

(def automatonI {:start :A
                 :accept #{:B}
                 :transition { 1 {:A :B :B :B}
                               0 {:A :A :B :A}}})

;; How should we work out whether this automaton accepts the string 101101011 ? 

;; It starts in state :A
(automatonI :start) ;-> :A

;; The first character of the string is a 1, and so it transitions to B
(((automatonI :transition) 1) 
 (automatonI :start)) ;-> :B

;; The second character is 0, so it transitions back to :A
(((automatonI :transition) 0) 
 (((automatonI :transition) 1) 
  (automatonI :start))) ;-> :A

;; And so on
(reduce 
 (fn[state input] (((automatonI :transition) input) state)) 
 (automatonI :start) 
 (list 1 0 1 1 0 1 0 1 1)) ;-> :B

;; The final state after all the input is consumed is :B, which is an accepting state

(defn final-state [automaton string]
  (reduce (fn[state input] 
            (((automaton :transition) input) state)) 
          (automaton :start) 
          string))


(final-state automatonI (list 1 0 1 1 0 1 0 1 1)) ;-> :B
(final-state automatonI (list 1 0 1 1 0 1 0 1 0)) ;-> :A

;; And so the string 101101011 is accepted by the automaton.

(defn accepts [automaton string]
  (not (nil? ((automaton :accept) 
              (final-state automaton string)))))

(accepts automatonI (list 1 0 1 1 0 1 0 1 1)) ;-> true
(accepts automatonI (list 1 0 1 1 0 1 0 1 0)) ;-> false

;; We might ask what other strings are accepted

;; First let's generate all possible strings of zeros and ones
(defn extend [ss] (for [a ss b '(0 1)] (cons b a)))

(extend '(())) ;-> ((0) (1))
(extend (extend '(()))) ;-> ((0 0) (1 0) (0 1) (1 1))

;; All these strings together are rather charmingly known as the free monoid on #{0,1} 
;; But enough of that! We know what strings are!

(def strings01 (apply concat (iterate extend '(()))))


strings01 ;-> (() (0) (1) (0 0) (1 0) (0 1) (1 1) (0 0 0) (1 0 0) (0 1 0) (1 1 0) (0 0 1) (1 0 1) (0 1 1) (1 1 1) (0 0 0 0) (1 0 0 0) (0 1 0 0) (1 1 0 0) (0 0 1 0) (1 0 1 0) (0 1 1 0) (1 1 1 0) (0 0 0 1) (1 0 0 1) (0 1 0 1) (1 1 0 1) ...)

;; As you may have guessed, this automaton accepts strings that end in 1

(filter (partial accepts automatonI) strings01) ;-> ((1) (0 1) (1 1) (0 0 1) (1 0 1) (0 1 1) (1 1 1) (0 0 0 1) (1 0 0 1) (0 1 0 1) (1 1 0 1) (0 0 1 1) (1 0 1 1) (0 1 1 1) (1 1 1 1) (0 0 0 0 1) (1 0 0 0 1) (0 1 0 0 1) (1 1 0 0 1) (0 0 1 0 1) (1 0 1 0 1) (0 1 1 0 1) (1 1 1 0 1) (0 0 0 1 1) (1 0 0 1 1) (0 1 0 1 1) (1 1 0 1 1) ...)

;; Proof by trying a finite number of cases:

(map last (filter (partial accepts automatonI) strings01)) ;-> (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)
(map last (filter (comp not (partial accepts automatonI)) strings01)) ;-> (nil 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...)

;; Here's a (slightly) more interesting variant:

;; INSERT AUTOMATONII.PNG

(def automatonII {:start :A
                  :accept #{:B}
                  :transition { 1 {:A :B :B :A}
                                0 {:A :A :B :B}}})


;; Can you see what it is doing?
(filter (partial accepts automatonII) strings01) ;-> ((1) (1 0) (0 1) (1 0 0) (0 1 0) (0 0 1) (1 1 1) (1 0 0 0) (0 1 0 0) (0 0 1 0) (1 1 1 0) (0 0 0 1) (1 1 0 1) (1 0 1 1) (0 1 1 1) (1 0 0 0 0) (0 1 0 0 0) (0 0 1 0 0) (1 1 1 0 0) (0 0 0 1 0) (1 1 0 1 0) (1 0 1 1 0) (0 1 1 1 0) (0 0 0 0 1) (1 1 0 0 1) (1 0 1 0 1) (0 1 1 0 1) ...)

;; And finally:
(def automatonIII {:start :A
                   :accept #{:A}
                   :transition { 1 {:A :B :B :A :C :C}
                                 0 {:A :A :B :C :C :B}}})

;; INSERT AUTOMATONIII.PNG

(filter (partial accepts automatonIII) strings01) ;-> (() (0) (0 0) (1 1) (0 0 0) (1 1 0) (0 1 1) (0 0 0 0) (1 1 0 0) (0 1 1 0) (1 0 0 1) (0 0 1 1) (1 1 1 1) (0 0 0 0 0) (1 1 0 0 0) (0 1 1 0 0) (1 0 0 1 0) (0 0 1 1 0) (1 1 1 1 0) (0 1 0 0 1) (1 0 1 0 1) (0 0 0 1 1) (1 1 0 1 1) (0 1 1 1 1) (0 0 0 0 0 0) (1 1 0 0 0 0) (0 1 1 0 0 0) ...)

;; Can you see what this one is doing? 

;; Here's a clue

(defn to-integer [lst]
  (cond (empty? lst) 0
        (= (first lst) 1) (+ 1 (* 2 (to-integer (rest lst))))
        :else (* 2 (to-integer (rest lst)))))

(map to-integer strings01)

(map to-integer (filter (partial accepts automatonIII) strings01)) ;-> (0 0 0 3 0 3 6 0 3 6 9 12 13 15 0 3 6 9 12 13 15 18 24 26 27 30 0 ...)

(for [[k v] (group-by (partial accepts automatonIII) (take 100 strings01))]
  [k (sort (distinct (map to-integer v)))])
;;-> ([true (0 3 6 9 12 15 18 21 24 27 30 33 36)] 
;;    [false (1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35)])

;; Can you get it to work the right way round? 

;; Can you generalize it?

Starting Clojure from the Command Line

For some reason, starting Clojure is comically slow on my machine. Most people talk about a few seconds, but for me it's more like a minute from 'lein repl' to a usable state.

This is annoying. I need a good reason to restart my repls, and I usually make a cup of tea while it's happening.

Sometimes I come back and find that the thing has failed to start because the start up time has exceeded leiningen's built in time-out and been killed. The reasons this can happen are many and varied, I have found.

This is not the JVM's fault. A trivial java hello world program runs quickly enough that you can't tell that there is a startup time.

One way to speed it up is to get leiningen out of the loop and start clojure as a JVM program, but leiningen is a great classpath manager.

But you can have the best of both worlds:


$ lein classpath > LEIN_CLASSPATH

Gets the classpath and puts it in a file. You only need to do this when you change your project.clj file to add a new dependency.

$ LEIN_CLASSPATH=`cat LEIN_CLASSPATH`




Reads that file into an environment variable.

$ rlwrap java -classpath $LEIN_CLASSPATH clojure.main

Starts clojure with the right classpath. As a bonus, you can use rlwrap to be your command line editor, which works like the bash shell, and is much better than the default.

Usually I use clojure from EMACS though, and so instead I type:

rlwrap java -server -Xmx800M -classpath $LEIN_CLASSPATH clojure.main -e "( do (require 'clojure.tools.nrepl.server) (clojure.tools.nrepl.server/start-server :bind \"127.0.0.1\" :port 4001))" -r

Which starts up an nrepl on port 4001, ready to be bound to from emacs, makes sure the jvm's in server mode, and gives it 800M maximum memory. It will only expand to that size if it needs it, so why not?

In either case clojure will execute a file called user.clj on the classpath, so you've got somewhere to put custom startup code if you like.

If I was feeling really clever, I might turn these commands into a script which remade the file if it was older than project.clj, etc. But these lines are always in my command line history, and that's actually good enough that I don't feel the need (yet).