Bjørn Arild Mæland

Better late than never, I finally published the code I produced for my small automaton library at http://github.com/Chrononaut/rton/tree/master. It was created as part of a introductionary course in computational linguistics. I'm quite pleased with how the DSL turned out. Consider the following example, a pushdown automaton for the aⁿ bⁿ language:

@anbn = Automaton.setup(:pda) do
  initial_state :q0 do
    transition ['a', EMPTY], [:q0, 'A']
    transition ['b', 'A'],   [:q1, EMPTY]
  end

  state :q1 do
    transition ['b', 'A'],   [:q1, EMPTY]
  end

  final_states :q0, :q1
end

From the initial state, if an 'a' is read, 'A' is pushed onto the stack. This is called the automatons 'pushing state'. Once a 'b' is read, it transists to state q1, where it starts popping off the 'A' characters from the stack. Basically, if the end of the input string is reached and the stack is empty at that point, the string is accepted. Therefore this automaton accepts input strings like a b, a a b b, etc.

Unfortunately, I doubt that I will actually turn this into something generally usable, mainly because I now spend more time on languages like Python and Clojure for NLP tasks. However, I can recommend JFLAP for a more visual automaton experience.