Instantly share code, notes, and snippets.

Embed
What would you like to do?
A turing machine in coffeescript
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment