# Copyright (c) 2010 Davi Alves Magalhaes
#
# Autor: Davi Alves Magalhaes <davialvesmagalhaes(at)hotmail.com>
#
# Automato Reconhecedor Deterministico
#
# Programa desenvolvido para estudo na Universidade do Estado
# do Rio Grande do Norte - UERN. Este software eh LIVRE. Use,
# edite e redistribua conforme desejar, sem esquecer dos creditos
# ao autor ;). Nao meresponsabilizo por danos causados por este
# programa a computadores de terceiros. Use por sua conta e risco.
#

alfabeto = []
transicoes = []

def cadeia_valida(auxiliar):
    global estadoInicial
    estado = estadoInicial
    for i in auxiliar:
        contador = 0
        for j in transicoes:
            if i == j[1] and j[0] == estado:
                estado = j[2]
                break
            else:
                contador = contador + 1
            if contador == len(transicoes):
                return False

    if estado == estadoFinal:
        return True
    else:
        return False

print "Digite um alfabeto: (cada caractere deve ser digitado numa unica linha)"
print "Digite 'fim' para terminar este processo"
while (True):
    aux = raw_input()
    if aux != "fim":
        alfabeto.append(aux)
    else:
        break

if len(alfabeto) == 0:
    print "Nenhum alfabeto digitado. O programa sera finalizado"
    exit(0)

print "Ok! Agora digite as operacoes de transicao da seguite forma:"
print "<estado_atual> <caractere_encontrado> = <novo_estado>"
print "Se estou no <estado_atual> e tenho <caractere_encontrado>, vou para <novo estado>."
print "Ex: \n\t1 a = 3\n\t4 y = 0\n\t2 z = 1\n\nDigite 'fim' indicar o fim das transicoes"

while (True):
    aux = raw_input()
    if aux != "fim":
        transicoes.append((aux[0], aux[2], aux[-1]))
    else:
        break

if len(transicoes) == 0:
    print "Nenhuma transicao digitada. O programa sera finalizado."
    exit(0)

estadoInicial = raw_input("Qual o estado inicial?")
estadoFinal = raw_input ("Qual o estado final?")

print "Digite cadeias para o teste do automato ('sair' para finalizar)"
while (True):
    aux = raw_input()
    if aux != "sair":
        if cadeia_valida(aux) == True:
            print "A cadeia", aux, "eh valida."
        else:
            print "A cadeia", aux, "nao eh valida."
    else:
        print "Programa encerrado"
        break