#!/usr/bin/env ruby

INITIAL_STATE = 's1'
FINAL_STATES = ['s6']
STRING = 'aaabbb'
TRANSITIONS = {
['s1', 'a'] => ['s2', 'A', :R],
['s2', 'a'] => ['s2', 'a', :R],
['s2', 'B'] => ['s2', 'B', :R],
['s2', 'b'] => ['s3', 'B', :L],
['s3', 'B'] => ['s3', 'B', :L],
['s3', 'A'] => ['s5', 'A', :R],
['s3', 'a'] => ['s4', 'a', :L],
['s4', 'a'] => ['s4', 'a', :L],
['s4', 'A'] => ['s1', 'A', :R],
['s5', 'B'] => ['s5', 'B', :R],
['s5', '^'] => ['s6', '^', :R]
}

state = INITIAL_STATE
tape = STRING
head = 0

puts '<tt>'

while true do
	puts '[' + state + '] ' + (head == 0 ? '' : tape[0..head - 1]) + '<u>' + tape[head..head] + '</u>' + tape[head + 1..-1] + '<br/>';
	
	if FINAL_STATES.include?(state)
		puts 'Halt.'
		break
	end
	
	state, write, move = TRANSITIONS[[state, tape[head..head]]]
	
	if state == nil
		puts 'Crash.'
		break
	end
	
	tape[head] = write
	
	if move == :R
		if head == tape.length - 1
			tape += '^'
		end
		head += 1
	elsif move == :L
		if head == 0
			tape = '^' + tape
		else
			head -= 1
		end
	end
end

puts '</tt>'