import sys, re

FILENAME='/Users/kozen/Desktop/machine.txt'
DEBUG=False

def compile_machine(filename):
    rexp = re.compile('^\((\w*),(\w*|[\{\?])\)->\((\w*),(\w*|{),([LR]?)\)$')
    lines = [line.strip() for line in open(filename, 'r')]
    for line in lines:
        if line == '': continue
        m = re.match(rexp,line)
        if m == None:
            print 'Illegal transition: ' + line
            continue
        else:
            elements = m.groups()
            kv_pairs[(elements[0], elements[1])] = (elements[2], elements[3], elements[4])

def run_machine(tape, location, state):
    if DEBUG:
        print tape
        print state + ' ' + str(location)
        print ' '
    if location < len(tape):
        if (state,tape[location]) in kv_pairs:
            (new_state, print_letter, direction) = kv_pairs[(state,tape[location])]
        elif (state,'?') in kv_pairs:
            (new_state, print_letter, direction) = kv_pairs[(state,'?')]
        else:
            print 'No transition for (' + state + ',' + tape[location] + ')'
            sys.exit()
    else:
        if (state,'') in kv_pairs:
            (new_state, print_letter, direction) = kv_pairs[(state,'')]
            tape.append('')
        else:
            print 'No transition for (' + state + ',)'
            sys.exit()
    
    tape[location] = print_letter
    if new_state == 't':
        print 'ACCEPT'
        sys.exit()
    elif new_state == 'r':
        print 'REJECT'
        sys.exit()
    else:
        if direction=='R':
            location += 1
        elif direction=='L':
            location -= 1
        run_machine(tape, location, new_state)
    

kv_pairs={}
compile_machine(FILENAME)
tape = ['{']
tape += list(raw_input('Enter a string to run on: '))

run_machine(tape,0,'s')