Coding

Finite State Machine in CoffeeScript

Update: I revised this machine on July 5, 2012.  Visit: Implementing String.Contains for a nicer implementation of this machine, or read on for the full story.

I’m not really a JavaScript guy.  I tend to lean heavily on Google, StackOverflow and trial and error when I need to do some work in the language.  The arrival of CoffeeScript peaked my interest, but since I spend so little time in the JavaScript domain, I had no immediate reason to jump in and give it a try.  Yesterday I had an idea that got me excited giving about CoffeeScript a try.  I decided to take a homework assignment I completed a few weeks ago for the Theory of Computing course I’m taking this semester, and implement it in CoffeeScript.

cs

I spend most of my time in C#, but for this assignment I needed to use C/C++ or Java.  So, initially I implemented the solution in C#, figuring it would be “easy” to translate to C/C++.  I haven’t really done any C/C++ since .NET came out, so it wasn’t as easy as I had hoped it would be.  I spent all of one Sunday flipping back and forth between MonoDevelop and http://www.cplusplus.com/, but it eventually worked out.

Translating to CoffeeScript from the C/C++ implementation went much more smoothly.  The REPL editor and reference material on http://coffeescript.org/ is a great resource.  Here are the results (you can also view/download the whole thing from this gist.

The machine is very simple, it accepts any input that contains the string “operating system”.  Informally, I mentally partitioned the transition function into three sets.  One set of rules advances the machine toward the acceptance state whenever it reads the next expected character.  The next rule set returns the machine to the initial state whenever an unexpected character is encountered.  The final rule traps the machine in the acceptance state after it has read all the characters in the string “operating system”

The first thing I did was to define some functions that would generate these transition rules for me based on an array of expected input characters.

createRule = (index, source) -> {
 initialState: index
 inputChar: source[index]
 resultState: index + 1
 match: (q, c) -> true if (this.initialState == q && this.inputChar == c)
 }

createAltRule = (index, source) -> 
 if index == source.length
  {
    # trap in acceptance state
    initialState: index
    inputChar: null
    resultState: index
    match: (q, c) -> true if (this.initialState == q) 
  }
 else
  {
    # return to start state
    initialState: index
    inputChar: source[index]
    resultState: 0
    match: (q, c) -> true if (this.initialState == q && this.inputChar != c)
  }

Each rule is implemented as an object with some data and a match function. For rules that advance the machine toward acceptance, the match function returns true when the rule’s state and input character match the values passed in by the machine.  For those that move the machine back to the initial state, the match function checks the state and any character other than the expected character.  Finally, the trap rule does not take the input character into account at all, it just checks that the machine has indicated that it has reached the final state.

createMachine = (rules, initialState, finalStates) ->
 {
   currentState: initialState
   transitionRules: rules
   acceptanceStates: finalStates
   read: (c) ->
    for i in [0..this.transitionRules.length - 1]
      if this.transitionRules[i].match this.currentState, c
        return this.currentState = this.transitionRules[i].resultState
   readAll: (s) -> this.read x for x in s.split ''
   acceptedInput: () -> this.currentState in this.acceptanceStates
 }

Next, we have a function that builds the state machine.  This function accepts a set of rules, the start state, and a set of final states.  However, in this example, the machine only has one final state.  When the machine has finished reading the input, clients can use the acceptedInput function to check that the machine’s current state is in the set of final states.  The readAll method takes a string and is provided for convenience, it simply splits the string into a character array and calls the read method an each character in the input.

The read method controls the machine’s state by iterating through each rule until it finds a rule that matches the machine’s current state and input character.  When it finds the match, it assigns the rule’s result state to its own currentState field.  I believe that calling return will short-circuit the loop after when a match is made, but I’m not familiar enough with JavaScript to say for sure.  In any case, it shouldn’t matter because the machine is deterministic and only one rule can match for any given combination of state and input character.

The list comprehension feature of CoffeeScript will also build a collection from the read method return values and this collection should contain each state the machine chose for each computation.  That might be interesting to look at but, it isn’t really necessary for using the machine.

 getMachineResult = (b) -> 
  if b == true 
   return " Accepted. "
  else
   return " Not Accepted. "

source = "operating system".split '' 
rules = (createRule x, source for x in [0..source.length])
altRules = (createAltRule x, source for x in [0..source.length])
rules.concat altRules
finalStates = [ source.length ]

test1 = "Windows is an operating system installed on many machines."
machine = createMachine(rules, 0, finalStates)
machine.readAll test1
alert getMachineResult(machine.acceptedInput()) + test1

test2 = "Welcome to the operating room, the Doctor is just finishing his martini."
machine2 = createMachine(rules, 0, finalStates)
machine2.readAll test2
alert getMachineResult(machine2.acceptedInput()) + test2

In this part, we create one more little function to translate Boolean results into text, and then we use have we have to create and run a couple machines.  As expected “test1” is accepted by the machine, and “test2” is not.

From scratch, translating this machine to CoffeeScript took about 3 hours and resulted in 60 lines of code.  Before this I had zero experience with CoffeeScript.  All in all, I’d say it was fun and easy.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s