Created
April 23, 2012 22:42
-
-
Save jamesrcounts/2474332 to your computer and use it in GitHub Desktop.
A turing machine in coffeescript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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