#!/usr/bin/env python #-*- coding:utf-8 -*- # turingmachine.py # Maquina de Turing # Copyright (c) 2007 Marcelo Lira dos Santos # # Author: Marcelo Lira dos Santos # # This program is free software; you can redistribute it and/or # modify it under the terms of the GNU General Public License as # published by the Free Software Foundation; either version 2 of the # License, or (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 # USA class TuringMachine: ( LEFT, RIGHT ) = range(2) ( ACCEPT, REJECT, NONE ) = range(3) def __init__(self, states=None, input_alphabet=None, tape_alphabet=None, transition_function=None, start_state=None, accept_state=None, reject_state=None): self.states = states self.input_alphabet = input_alphabet self.tape_alphabet = tape_alphabet self.transition_function = transition_function self.start_state = start_state self.accept_state = accept_state self.reject_state = reject_state self.string = None self.current_state = start_state self.tape = None self.head = 0 self.steps = 0 self.debug = False def set_states(self, states): states.sort() self.states = states def set_input_alphabet(self, input_alphabet): self.input_alphabet = input_alphabet def set_tape_alphabet(self, tape_alphabet): self.tape_alphabet = tape_alphabet def set_start_state(self, start_state): self.start_state = start_state def set_accept_state(self, accept_state): self.accept_state = accept_state def set_reject_state(self, reject_state): self.reject_state = reject_state def set_transition_function(self, transition_function): self.transition_function = transition_function def set_string(self, string): if not self.validate_string(string): #FIXME: jogue uma excecao adequada print 'string invalida' return self.string = string def set_head(self, head=0): self.head = head def get_states(self): return self.states def get_current_state(self): return self.current_state def get_input_alphabet(self): return self.input_alphabet def get_tape_alphabet(self): return self.tape_alphabet def get_start_state(self): return self.start_state def get_accept_state(self): return self.accept_state def get_reject_state(self): return self.reject_state def get_transition_function(self): return self.transition_function def get_string(self): return self.string def get_head(self): return self.head def get_tape(self): return self.tape def validate_machine(self): '''Retorna True se os atributos da maquina estiverem corretos.''' if not self.states: return False if self.start_state not in self.states or\ self.accept_state not in self.states or\ self.reject_state not in self.states: return False if not set(self.transition_function).issubset(self.states): return False #FIXME: verificar os valores dentro de self.trans_func... return True def validate_string(self, string): return set(string).issubset(self.input_alphabet) def reset(self): self.current_state = self.start_state # FIXME: a fita eh infinita a direita. self.tape = list(self.string) self.head = 0 self.steps = 0 def step_back(self): if self.steps < 1: return steps = self.steps - 1 self.reset() self.compute(steps) def compute(self, steps=-1): while steps != 0: steps -= 1 accept = self.compute_step() if accept == TuringMachine.ACCEPT: return True elif accept == TuringMachine.REJECT: return False def compute_step(self): self.steps += 1 if self.current_state == self.accept_state: return TuringMachine.ACCEPT read_symbol = self.tape[self.head] current_state_trans = self.transition_function[self.current_state] if not current_state_trans.has_key(read_symbol): return TuringMachine.REJECT else: next_state, write_symbol, move = \ current_state_trans[read_symbol] if self.debug: print '(state:%s,head:%d,read:%s): ->%s w:%s, m:%d -- %s' % \ (self.current_state, self.head, read_symbol, next_state, \ write_symbol, move, ''.join(self.tape)) if write_symbol != None: self.tape[self.head] = write_symbol self.current_state = next_state if self.current_state == self.reject_state: return TuringMachine.REJECT elif self.current_state == self.accept_state: return TuringMachine.ACCEPT if move == TuringMachine.LEFT: self.head -= 1 if self.head < 0: self.head = 0 else: self.head += 1 if self.head == len(self.tape): self.tape.append(' ') return TuringMachine.NONE def generate_graph(self): dot_graph = 'digraph turing_machine {\n' dot_graph += ' edge [fontname=helvetica,fontsize=9]\n' dot_graph += ' node [fontname=helvetica,fontsize=9,shape=doublecircle];' dot_graph += self.accept_state + '\n' dot_graph += ' node [shape=circle,size=8]\n' dot_graph += ' start [shape=point]\n' dot_graph += ' start -> %s\n' % self.start_state for state in self.states: if not self.transition_function.has_key(state): continue values = self.transition_function[state].keys() values.sort() tmp_values = {} for value in values: next_state, write, movement = \ self.transition_function[state][value] right_side = '' if write: right_side += write + ',' if movement == TuringMachine.RIGHT: right_side += 'R' else: right_side += 'L' if value == ' ': read_value = '_' else: read_value = value if tmp_values.has_key((next_state, right_side)): tmp_values[(next_state, right_side)].append(read_value) else: tmp_values[(next_state, right_side)] = [read_value] for value in tmp_values.keys(): left_side = ','.join(tmp_values[value]) next_state, right_side = value dot_graph += ' %s -> %s [label=\"%s->%s\"]\n' % \ (state, next_state, left_side, right_side) dot_graph += '}\n' return dot_graph def test(): tm = TuringMachine() tm.debug = True # A maquina de turing deste teste. states = ['q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'q7', 'q8', 'qa', 'qr'] tm.set_states(states) tm.set_start_state('q1') tm.set_accept_state('qa') tm.set_reject_state('qr') tm.set_input_alphabet(['0', '1', '#']) tm.set_tape_alphabet(['x', ' ']) # Funcao de transicao trans_func = { 'q1': {'0': ('q2', 'x', TuringMachine.RIGHT), '1': ('q3', 'x', TuringMachine.RIGHT), '#': ('q8', None, TuringMachine.RIGHT)}, 'q2': {'0': ('q2', None, TuringMachine.RIGHT), '1': ('q2', None, TuringMachine.RIGHT), '#': ('q4', None, TuringMachine.RIGHT)}, 'q3': {'0': ('q3', None, TuringMachine.RIGHT), '1': ('q3', None, TuringMachine.RIGHT), '#': ('q5', None, TuringMachine.RIGHT)}, 'q4': {'0': ('q6', 'x', TuringMachine.LEFT), 'x': ('q4', None, TuringMachine.RIGHT)}, 'q5': {'1': ('q6', 'x', TuringMachine.LEFT), 'x': ('q5', None, TuringMachine.RIGHT)}, 'q6': {'0': ('q6', None, TuringMachine.LEFT), '1': ('q6', None, TuringMachine.LEFT), 'x': ('q6', None, TuringMachine.LEFT), '#': ('q7', None, TuringMachine.LEFT)}, 'q7': {'0': ('q7', None, TuringMachine.LEFT), '1': ('q7', None, TuringMachine.LEFT), 'x': ('q1', None, TuringMachine.RIGHT)}, 'q8': {' ': ('qa', None, TuringMachine.RIGHT), 'x': ('q8', None, TuringMachine.RIGHT)} } tm.set_transition_function(trans_func) if not tm.validate_machine(): #FIXME: jogue uma excecao adequada print 'maquina invalida' return #string = '101111100011#101111100011' string = '101111100011#000000000000' tm.set_string(string) print '\nprocessando: ' + string tm.reset() accept = tm.compute() print accept ''' string = '1011#1011' tm.set_string(string) print '\nprocessando: ' + string accept = TuringMachine.NONE i = 0 while accept != TuringMachine.ACCEPT: i += 1 print '\nproc ' + str(i) tm.reset() for j in range(i): accept = tm.compute_step() print ' aceita: ', accept print '\n-----------------------------------------\n' ''' grafo = tm.generate_graph() print grafo f = open('turingmachine.dot', 'w') f.write(grafo) f.close() if __name__ == '__main__': test()