#!/usr/bin/env python
#-*- coding:utf-8 -*-
# automato.py
# AFD == Automato Finito Deterministico

# Copyright (c) 2007 Marcelo Lira dos Santos
#
# Author: Marcelo Lira dos Santos <setanta@gmail.com>
#
# 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

# Componentes da 4-upla que descreve um AFD.
# NOTA: convencionalmente usa-se uma 5-upla, sendo o primeiro
#       o conjunto dos estados possiveis. Nesta implementacao
#       extrairemos os estados possiveis dos estados de entrada
#       na funcao de transicao.
(
ALPHABET,
TRANSITION_FUNCTION,
START_STATE,
FINAL_STATES
) = range(4)

def validate_machine(machine):
    if not machine:
        print 'validate_machine: maquina invalida.'
        return False

    possible_states = set(machine[TRANSITION_FUNCTION].keys())

    if not machine[FINAL_STATES].issubset(possible_states):
        print 'validate_machine: o conjunto dos estados finais (%s) '\
              'nao esta contido no conjunto dos estados possiveis. (%s)' %\
              (str(machine[FINAL_STATES]), str(possible_states))
        return False

    if machine[START_STATE] not in possible_states:
        print 'validate_machine: estado inicial (%s) '\
              'nao pertence ao conjunto dos estados possiveis (%s).' %\
              (str(machine[START_STATE]), str(possible_states))
        return False

    for state in possible_states:
        chars = set(machine[TRANSITION_FUNCTION][state].keys())
        resulting_states = set(machine[TRANSITION_FUNCTION][state].values())

        if not chars.issubset(machine[ALPHABET]):
            print 'validate_machine: pelo menos um dos caracteres de entrada '\
                  'da funcao de transicao nao faz parte do alfabeto {%s}.' %\
                  ','.join(machine[ALPHABET])
            return False

        if not resulting_states.issubset(possible_states):
            print 'validate_machine: algum(ns) dos estados resultantes da '\
                  'funcao de transicao nao faz(em) parte dos estados '\
                  'possiveis (%s).' % possible_states
            return False

    return True


def validate_string(alphabet, string):
    for char in string:
        if char not in alphabet:
            print 'validate_string: '\
                  '"%s" eh uma palavra invalida no alfabeto {%s}' %\
                  (string, ','.join(alphabet))
            return False

    return True


def process_string(machine, string):
    '''
    Avalia se 'string' pertence a linguagem descrita pelo
    AFD descrito por 'machine', retornando True ou False.
    Retorna 'None' em caso de parametros invalidos.
    '''

    if not validate_machine(machine) or \
       not validate_string(machine[ALPHABET], string):
        return None

    state = machine[START_STATE]
    for char in string:
        state = machine[TRANSITION_FUNCTION][state][char]

    return (state in machine[FINAL_STATES])


def generate_graph(trans_func, start_state, final_states):
    states = trans_func.keys()
    states.sort()

    dot_graph = 'digraph finite_state_machine {\n'
    dot_graph += '    rankdir=LR;\n'
    dot_graph += '    edge [fontname=arial,fontsize=11]\n'
    dot_graph += '    node [fontname=arial,fontsize=11,shape=doublecircle];'
    dot_graph += ' '.join(final_states)
    dot_graph += ';\n'
    dot_graph += '    node [shape=circle,size=8]\n'
    dot_graph += '    start [shape=point]\n'
    dot_graph += '    start -> %s\n' % start_state

    for state in states:
        values = trans_func[state].keys()

        values.sort()
        for value in values:
            dot_graph += '    %s -> %s [label=%s]\n' % \
                    (state, trans_func[state][value], value)

    dot_graph += '}\n'

    return dot_graph


if __name__ == '__main__':
    # O AFD a seguir descreve uma linguagem sobre o alfabeto {0, 1}
    # que consiste de todas as palavras que comecem com '0',
    # juntamente com a string vazia.
    alphabet = set(['0', '1'])
    trans_func = {'q1' : {'0' : 'q1', '1' : 'q2'},
                  'q2' : {'0' : 'q1', '1' : 'q2'}}
    start_state = 'q1'
    final_states = set(['q1'])
    machine = (alphabet, trans_func, start_state, final_states)

    strings = ['000011111000101010101000', '000011', '1', '10', 'a01', '']

    for string in strings:
        result = process_string(machine, string)
        if result != None:
		    print '%s = %s' % (string, result)

    print '\n------------------------------------------------'
    print 'Automato em formato "dot" do Graphviz.'
    print 'Para gerar uma imagem do automato use o comando:'
    print '  dot -T png -o afd.png afd.dot'
    print

    graph = generate_graph(trans_func, start_state, final_states)
    print graph

    f = open("afd.dot", "w")
    f.write(graph)
    f.close()