A turing machine in coffeescript

turing.coffee

alert = (s) -> console.log s

createResult = (state, symbol, direction) ->
 nextState: state
 writeSymbol: symbol
 moveTo: direction
 toString: () -> [this.nextState, this.writeSymbol, this.moveTo].join ", "

createRule = (state, symbol, result) ->
 inState: state
 readSymbol: symbol
 transitionResult: result
 match: (s, y) -> true if (this.inState == s && this.readSymbol == y)
 toString: () -> [this.inState, this.readSymbol, this.transitionResult].join ", "

createTape = (s, blank) ->
 t = [ blank ].concat s.split ''
 t.push blank
 pos = 0
 pos++ while t[pos] == blank
 pos-- while t[pos] == undefined
 return {
  currentPosition: pos
  buffer: t
  currentSym: () -> this.buffer[this.currentPosition]
  write: (s) -> this.buffer[this.currentPosition] = s
  moveRight: () ->
   p = this.currentPosition
   p++
   this.buffer.push blank if p == this.buffer.length
   this.currentPosition = p
   return null
  moveLeft: () ->
   p = this.currentPosition
   p--
   if p < 0
    this.buffer.unshift blank
    p = 0
   this.currentPosition = p
   return null
  move: (d) ->
   this.moveRight() if d == 'R'
   this.moveLeft() if d == 'L'
   return null
  toString: () -> (this.buffer.join ", ") + " pos: " + this.currentPosition
  }

createMachine = (rules, initialState, blank, finalStates) ->
 transitionRules: rules
 currentState: initialState
 blankSymbol: blank
 acceptanceStates: finalStates
 tape: createTape '', blank
 isHalted: false
 toString: () -> 
  r = this.transitionRules.join "|| "
  f = this.acceptanceStates.join ", "
  [ r, this.currentState, this.blankSymbol, f, this.tape].join ":: "
 acceptedInput: () -> this.currentState in this.acceptanceStates
 loadTape: (s) -> this.tape = createTape s, this.blankSymbol
 readTape: () -> this.tape
 update: (r) ->
  this.currentState = r.nextState
  this.tape.write r.writeSymbol
  this.tape.move r.moveTo
  return null
 read: () ->
  q = this.currentState
  s = this.tape.currentSym()
  for rule in this.transitionRules
   if rule.match q, s
    return this.update rule.transitionResult
  return this.isHalted = true
 run: (s) ->
  this.loadTape s
  this.read() until this.isHalted
  return null

runMachine = (f, i) ->
 m = f()
 m.run i
 alert "input: " + i + " accepted: " + m.acceptedInput() + " tape: " + m.readTape()

# Example from lecture
exampleMachine = () -> 
 exampleRuleSet = [ 
  createRule 0, 'a', createResult 0, 'b', 'R'
  createRule 0, 'b', createResult 0, 'b', 'R'
  createRule 0, 'B', createResult 1, 'B', 'L'
 ]
 createMachine exampleRuleSet, 0, 'B', [ 1 ]

#runMachine exampleMachine, "aaa"
#runMachine exampleMachine, "aba"
#runMachine exampleMachine, "bbb"
#runMachine exampleMachine, "caa"

# HW Problem 1 Construct a Turing machine that will accept the following language on {a, b}
# L = { w : |w| is even }
m1 = () ->
 ruleSet = [
   createRule 0, 'B', createResult 5, 'B', 'L' # accept the empty string
   createRule 0, 'a', createResult 1, 'X', 'R' # replace the first a or b with an X
   createRule 0, 'b', createResult 1, 'X', 'R'
   createRule 0, 'Y', createResult 4, 'Y', 'R' # possibly located the tail
   createRule 1, 'a', createResult 1, 'a', 'R' # scan right until {B, Y}
   createRule 1, 'b', createResult 1, 'b', 'R'
   createRule 1, 'B', createResult 2, 'B', 'L'
   createRule 1, 'Y', createResult 2, 'Y', 'L' 
   createRule 2, 'a', createResult 3, 'Y', 'L' # replace first a or b with Y
   createRule 2, 'b', createResult 3, 'Y', 'L'   
   createRule 3, 'a', createResult 3, 'a', 'L' # scan left until X
   createRule 3, 'b', createResult 3, 'b', 'L'
   createRule 3, 'X', createResult 0, 'X', 'R'   
   createRule 4, 'Y', createResult 4, 'Y', 'R' # tail should be all Y
   createRule 4, 'B', createResult 5, 'B', 'L' # accept
 ]
 createMachine ruleSet, 0, 'B', [ 5 ]

runMachine m1, ""
runMachine m1, "a"
runMachine m1, "b"
runMachine m1, "aa"
runMachine m1, "ab"
runMachine m1, "ba"
runMachine m1, "bb"
runMachine m1, "aaa"
runMachine m1, "bbbb"
runMachine m1, "aaaa"
runMachine m1, "abab"
runMachine m1, "cc"

# HW Problem 2 Design Turing machines to compute the following function for x and y positive
# integers represented in unary f(x) = 3x
m2 = () ->
 ruleSet = [
  createRule 0, 'B', createResult 1, 'B', 'L' # accept empty string
  createRule 0, '1', createResult 2, 'X', 'R' # replace all 1 with X
  createRule 2, '1', createResult 2, 'X', 'R'
  createRule 2, 'B', createResult 3, 'B', 'L' # Found the right side B, now return to leftside B
  createRule 3, 'X', createResult 3, 'X', 'L'
  createRule 3, '1', createResult 3, '1', 'L'
  createRule 3, 'B', createResult 4, 'B', 'R' # Found the left side B, now look for an X
  createRule 4, '1', createResult 9, '1', 'R' # Found 1 before finding X, check all '1's
  createRule 4, 'X', createResult 5, 'B', 'R' # Erase an X and look for the rightside B
  createRule 5, 'X', createResult 5, 'X', 'R' 
  createRule 5, '1', createResult 5, '1', 'R'
  createRule 5, 'B', createResult 6, '1', 'R' # Write 3 ones
  createRule 6, 'B', createResult 7, '1', 'R'
  createRule 7, 'B', createResult 8, '1', 'R'
  createRule 8, 'B', createResult 3, 'B', 'L' # Repeat search for additonal X
  createRule 9, '1', createResult 9, '1', 'R' # Checking string for all 1's
  createRule 9, 'B', createResult 1, 'B', 'L' # accept 
 ]
 createMachine ruleSet, 0, 'B', [ 1 ]

#runMachine m2, ""    # 0 x 3 = 0
#runMachine m2, "1"   # 1 x 3 = 3
#runMachine m2, "11"  # 2 x 3 = 6
#runMachine m2, "111" # 3 x 3 = 9
#runMachine m2, "112" # invalid

# HW Problem 3 Design a Turing Machine that accepts the language L = {a^n, b^n, c^n | N >=0}
m3 = () ->
 ruleSet = [
  createRule 0, 'B', createResult 1, 'B', 'L' # accept empty string
  createRule 0, 'a', createResult 2, 'X', 'R' # replace all a with X
  createRule 2, 'a', createResult 2, 'X', 'R'
  createRule 2, 'b', createResult 3, 'b', 'L' # until we find a 'b's 
  createRule 3, 'X', createResult 3, 'X', 'L' # scan left until Blank
  createRule 3, 'Y', createResult 3, 'Y', 'L'
  createRule 3, 'b', createResult 3, 'b', 'L'
  createRule 3, 'c', createResult 3, 'c', 'L'
  createRule 3, 'B', createResult 4, 'B', 'R'
  createRule 4, 'X', createResult 5, 'B', 'R' # Find and erase an X
  createRule 4, 'Y', createResult 7, 'B', 'R' # Find and erase a Y... done with X
  createRule 4, 'Z', createResult 9, 'Z', 'R' # Found Z, check that string is all Z
  createRule 5, 'X', createResult 5, 'X', 'R' # scan right until { c, Y }
  createRule 5, 'b', createResult 5, 'b', 'R'
  createRule 5, 'c', createResult 6, 'c', 'L'
  createRule 5, 'Y', createResult 6, 'Y', 'L'
  createRule 6, 'b', createResult 3, 'Y', 'L' # scan left to b, write Y, repeat X search
  createRule 7, 'Y', createResult 7, 'Y', 'R' # Scan right past {Y, c} until { B, Z }
  createRule 7, 'c', createResult 7, 'c', 'R'
  createRule 7, 'Z', createResult 8, 'Z', 'L'
  createRule 7, 'B', createResult 8, 'B', 'L'
  createRule 8, 'c', createResult 3, 'Z', 'L' # Scan left to c, Write Z, repeat Y search
  createRule 9, 'Z', createResult 9, 'Z', 'R' # scan right past Z until B
  createRule 9, 'B', createResult 1, 'B', 'L' # accept
 ]
 createMachine ruleSet, 0, 'B', [ 1 ]

runMachine m3, ""          # valid n = 0
runMachine m3, "a"         # invalid
runMachine m3, "ab"        # invalid
runMachine m3, "abc"       # valid n = 1
runMachine m3, "aabc"      # invalid
runMachine m3, "aabbc"     # invalid
runMachine m3, "aabbcc"    # valid n = 2
runMachine m3, "aaabbcc"   # invalid
runMachine m3, "aaabbbcc"  # invalid
runMachine m3, "aaabbbccc" # valid n = 3
runMachine m3, "abcd"      # invalid