#!/usr/bin/env python

import sys

"""Simulates a Turing machine on some input.
   
   The turing machine is describes as a dictionary of tuples
   the keys are tuples of (state, symbol), and the tuples consists of
   1. symbol to write on tape
   2. direction to move ('L' or 'R')
   3. state to transition to

   Input to the simulator is a configuration of a machine.
   That is a tape (list of symbols), a number for which cell is currently
   being looked at by the machine (indexing begins at 0), and the name of
   the current state.

   As the simulator emulates the turing machine, it will yield the successive
   configurations.

   At any time during the simulation:
     If the simulation encounters a (symbol,state) transition key which
        is not in the dictionary, then we yield 'crash' and halt.
     If the simulated machine accepts, then we yield 'accept' and halt.
     If the simulated machine rejects, then we yield 'reject' and halt.
   There will be no attept to detect infinite loops.

   Blanks on the tape are designated with the TeX symbol 'b'
   It is recommended that all states an symbols have TeX encoding,
   in this way we assure pretty printing.

   Output is a sequence of machine configurations printed to the screen.
"""

# the transition map the TM that recognizes (01)*
UTM = {
    ('$\\boldsymbol{q_1}$', 'b') : ('1', 'R', '$\\boldsymbol{q_3}$'),
    ('$\\boldsymbol{q_1}$', '0') : ('0', 'R', '$\\boldsymbol{q_2}$'),
    ('$\\boldsymbol{q_1}$', '1') : ('1', 'R', 'reject'),

    ('$\\boldsymbol{q_2}$', 'b') : ('b', 'R', 'reject'),
    ('$\\boldsymbol{q_2}$', '0') : ('0', 'R', 'reject'),
    ('$\\boldsymbol{q_2}$', '1') : ('1', 'R', '$\\boldsymbol{q_1}$'),

    ('$\\boldsymbol{q_3}$', 'b') : ('b', 'R', 'accept'),
    ('$\\boldsymbol{q_3}$', '0') : ('0', 'R', 'accept'),
    ('$\\boldsymbol{q_3}$', '1') : ('1', 'R', 'accept'),
    }

STARTCONFIG = ( list('010101'), 0, '$\\boldsymbol{q_1}$' )


def simulate_step( machine, config ):
    tape, position, state = config;

    # look up the transition

    try:
        write_symbol, move, next_state = machine[ (state, tape[position]) ]
    except KeyError:
        print >> sys.stderr, "machine crashed", state, 'on ', tape[position]
        return 'crash'

    if next_state in ['reject', 'accept', 'crash']:
        return next_state

    if move == 'R':
        # fix the tape if we run off the right end
        if position+1 >= len(tape):
            tape += ['b']*(position+2-len(tape))

        return ( tape[:position] + [write_symbol] + tape[position+1:],
                 position+1,
                 next_state )

    elif move == 'L':
        return ( tape[:position] + [write_symbol] + tape[position+1:],
                 max( position-1, 0), # prevent walking off left end of tape
                 next_state )

    else:
        return 'crash'


def config_to_str( config ):
    tape, position, state = config
    return ''.join( tape[:position] + ["{\\bf "] + [state] + ['}'] + tape[position:] )

def machine_to_tbl( machine ):
    states = set([])
    symbols = set([])
    for (state, symbol) in machine.keys():
        if state not in states:
            states.add(state)
        if symbol not in symbols:
            symbols.add(symbol)

    states = sorted(list(states))
    symbols = sorted(list(symbols))
    lst = ['\\begin{tabular}{c|ccc}']
    lst+= ['&' + '&'.join( str(symbol) for symbol in symbols ) + '\\\\']
    lst+= ['\\hline']
    for state in states:
        sublst = []
        for symbol in symbols:
            write_symbol, move, next_state = machine[ (state, symbol) ]
            try:
                sublst+= ['%s,%s,%s'%(write_symbol, move, next_state)]
            except KeyError:
                sublst+= [' ']
        lst+= ['&'.join([str(state)]+sublst) + '\\\\']
    lst+= ['\\end{tabular}']
    return '\n'.join(lst)
    


if __name__=='__main__':
    machine = UTM
    config = STARTCONFIG

    print '\\documentclass[a4paper,10pt]{article}'
    print '\\usepackage{amssymb}'
    print '\\usepackage{amsmath}'
    print '\\title{TM that accepts (01)*}'
    print '\\begin{document}'
    print '\\maketitle'

    print machine_to_tbl( UTM )
    print '\\\\'
    print '\\\\'
    print

    count = 0
    while 1:
        count += 1
        print '%04d'%count, '\\ \\ \\ ', config_to_str( config )
        print
        config = simulate_step( machine, config )
        if config in ['reject', 'accept', 'crash']:
            break

    print '\\ '*6 + config
    print '\\end{document}'