Interpretador de arquivos do JFLAP para Máquina de Turing.

questao01.jff

<?xml version="1.0" encoding="UTF-8" standalone="no"?><!--Created with JFLAP 6.4.--><structure>
	<type>turing</type>
	<automaton>
		<!--The list of states.-->
		<block id="0" name="q0">
			<tag>Machine0</tag>
			<x>243.0</x>
			<y>176.0</y>
			<initial/>
		</block>
		<block id="1" name="q1">
			<tag>Machine0</tag>
			<x>370.0</x>
			<y>175.0</y>
		</block>
		<block id="2" name="q2">
			<tag>Machine0</tag>
			<x>502.0</x>
			<y>179.0</y>
		</block>
		<block id="3" name="q3">
			<tag>Machine0</tag>
			<x>611.0</x>
			<y>181.0</y>
		</block>
		<block id="4" name="q4">
			<tag>Machine0</tag>
			<x>736.0</x>
			<y>180.0</y>
		</block>
		<block id="5" name="q5">
			<tag>Machine0</tag>
			<x>870.0</x>
			<y>330.0</y>
		</block>
		<block id="6" name="q6">
			<tag>Machine0</tag>
			<x>639.0</x>
			<y>333.0</y>
		</block>
		<block id="7" name="q7">
			<tag>Machine0</tag>
			<x>821.0</x>
			<y>61.0</y>
		</block>
		<block id="8" name="q8">
			<tag>Machine0</tag>
			<x>985.0</x>
			<y>61.0</y>
			<final/>
		</block>
		<!--The list of transitions.-->
		<transition>
			<from>0</from>
			<to>1</to>
			<read>B</read>
			<write>B</write>
			<move>R</move>
		</transition>
		<transition>
			<from>1</from>
			<to>2</to>
			<read>a</read>
			<write>X</write>
			<move>R</move>
		</transition>
		<transition>
			<from>7</from>
			<to>8</to>
			<read>B</read>
			<write>B</write>
			<move>R</move>
		</transition>
		<transition>
			<from>3</from>
			<to>4</to>
			<read>b</read>
			<write>Y</write>
			<move>R</move>
		</transition>
		<transition>
			<from>4</from>
			<to>7</to>
			<read>B</read>
			<write>B</write>
			<move>L</move>
		</transition>
		<transition>
			<from>5</from>
			<to>6</to>
			<read>B</read>
			<write>B</write>
			<move>R</move>
		</transition>
		<transition>
			<from>4</from>
			<to>5</to>
			<read>b</read>
			<write>b</write>
			<move>L</move>
		</transition>
		<transition>
			<from>6</from>
			<to>2</to>
			<read>a</read>
			<write>X</write>
			<move>R</move>
		</transition>
		<transition>
			<from>5</from>
			<to>5</to>
			<read>a</read>
			<write>a</write>
			<move>L</move>
		</transition>
		<transition>
			<from>5</from>
			<to>5</to>
			<read>Y</read>
			<write>Y</write>
			<move>L</move>
		</transition>
		<transition>
			<from>5</from>
			<to>5</to>
			<read>X</read>
			<write>X</write>
			<move>L</move>
		</transition>
		<transition>
			<from>7</from>
			<to>7</to>
			<read>X</read>
			<write>a</write>
			<move>L</move>
		</transition>
		<transition>
			<from>2</from>
			<to>2</to>
			<read>a</read>
			<write>a</write>
			<move>R</move>
		</transition>
		<transition>
			<from>6</from>
			<to>6</to>
			<read>X</read>
			<write>X</write>
			<move>R</move>
		</transition>
		<transition>
			<from>2</from>
			<to>2</to>
			<read>Y</read>
			<write>Y</write>
			<move>R</move>
		</transition>
		<transition>
			<from>7</from>
			<to>7</to>
			<read>Y</read>
			<write>b</write>
			<move>L</move>
		</transition>
		<transition>
			<from>2</from>
			<to>3</to>
			<read>b</read>
			<write>Y</write>
			<move>R</move>
		</transition>
		<!--The list of automata-->
		<Machine0/>
	</automaton>
</structure>

turing.py

#!/usr/bin/env python
#-*- coding: utf-8 -*-
import sys
from xml.etree import ElementTree


class State(object):
    def __init__(self, ID, name, kind=None):
        self.ID = ID
        self.name = name
        self.kind = kind
        self.transitions = []

    @property
    def trans_out(self):
        outs = [t for t in self.transitions if t.from_state == self]
        return outs

    def get_transition(self, content):
        for t in self.trans_out:
            if content == t.read:
                return t

    def __eq__(self, other):
        return self.ID == other.ID

    def __str__(self):
        if self.kind is None:
            return self.name
        else:
            return "%s(%s)" % (self.name, self.kind)

    def __repr__(self):
        return "<State: %s>" % self


class Transition(object):
    def __init__(self, from_state=None, to_state=None, read='', write='', move=''):
        self.from_state = from_state
        self.to_state = to_state
        self.read = read
        self.write = write
        self.move = move

    def __str__(self):
        return "%s -> [%s:%s:%s] -> %s" % (self.from_state, self.read, self.write, self.move, self.to_state)

    def __repr__(self):
        return "<Transition: %s>" % self


class Turing(object):
    def __init__(self, filename):
        with open(filename, 'r') as f:
            xml = f.read()
            self.xmlp = ElementTree.fromstring(xml)
        self._load_states()
        self._load_transition()

    def match(self, seq, debug=True):
        pos = len(seq) * 50
        tape = ['B' for i in range(pos * 2)]
        tape[pos:pos + len(seq)] = list(seq)
        head = pos - 1
        state = self.find_state_initial()
        while state.kind != 'final':
            c = tape[head]
            t = state.get_transition(c)
            if t is None:
                if debug:
                    print "Error:", state, c
                return False
            tape[head] = t.write
            if t.move == 'R':
                head += 1
            else:
                head -= 1
            state = t.to_state
            if debug:
                print ''.join(tape).strip('B'), c, t
        return True

    def find_state_initial(self):
        for state in self.states:
            if state.kind == 'initial':
                return state

    def find_state_by_id(self, ID):
        for state in self.states:
            if state.ID == ID:
                return state

    def _load_states(self):
        self.states = []
        for state in self.xmlp.findall('automaton/block'):
            ID = state.attrib['id']
            name = state.attrib['name']
            if not state.find('initial') is None:
                kind = 'initial'
            elif not state.find('final') is None:
                kind = 'final'
            else:
                kind = None
            self.states.append(State(ID, name, kind))

    def _load_transition(self):
        self.transitions = []
        for transition in self.xmlp.findall('automaton/transition'):
            t = Transition()
            for p in transition.getchildren():
                if p.tag == 'from':
                    state = self.find_state_by_id(p.text)
                    t.from_state = state
                    state.transitions.append(t)
                elif p.tag == 'to':
                    state = self.find_state_by_id(p.text)
                    t.to_state = state
                    state.transitions.append(t)
                else:
                    setattr(t, p.tag, p.text)
            self.transitions.append(t)


def main(argv):
    if len(argv) < 3:
        print "Use: %s arquivo.jff entrada" % argv[0]
        sys.exit(1)
    t = Turing(argv[1])
    print t.match(argv[2])

if __name__ == '__main__':
    main(sys.argv)