Automatos Finitos em Python

Seu computador computa, sua calculadora computa, uma flor computa, você computa, enfim, o universo inteiro computa. Uma verdadeira computaria.

Se encararmos qualquer estado (apagado, aceso, em movimento, triste, com fome) como informação, todo processo que altera esse estado, altera também a informação. Ou melhor, processa a informação, atividade comumente atribuída aos computadores, mas que é feita pelo universo desde que… desde de sempre! (Se é só isso que o universo faz, aí é outra história.)

Pra saber se alguma máquina de computação estava computando direito ou ainda qual seria seu poder computacional, um modelo matemático formal que dissesse “isso aqui é uma computação” era necessário. O modelo que usamos hoje é a máquina de turing, e seu criador, Alan Turing, foi recompensado por essa contribuição sendo levado (dizem alguns) à morte. Mas estou dispersando, isso também é outra história.

Não vou falar aqui da máquina de turing (ainda não cheguei nela em Informática Teórica), e sim de Autômatos Finitos Determinísticos (AFDs pra encurtar). Trata-se de uma máquina mais simples com propósito restrito: determinar se uma string de entrada é parte de uma dada linguagem ou não.

Uma explicação mais elaborada sobre linguagens (no contexto computacional) pode ser encontrada na entrada “Linguagem Formal“, na Wikipedia, no entanto darei alguns exemplos. Usando o alfabeto (os símbolos possíveis da linguagem) {0, 1}, podemos ter a linguagem composta das strings que começam com “110” e terminam com qualquer coisa; a linguagem das strings que terminam em “0”; ou a linguagem das strings que possuem a substring “10101”.

Se fossem nomes de arquivos no unix, poderíamos listar os membros das linguagens dos exemplos anteriores com os comandos: ls 110* ; ls *0 ; ls *10101*

Autômatos Finitos Determinísticos

As linguagens reconhecidas por AFDs são chamadas regulares, e se você pensou no que eu penso que pensou, então está certo! As strings que fazem parte dessas linguagens regulares são aquelas reconhecidas pelas expressões regulares. Na verdade toda expressão regular tem um AFD equivalente e vice-versa.

Vamos a coisas mais estruturais. Um AFD é composto de

  • estados: sua memória;
  • alfabeto: caracteres usados para formar as entradas a serem testadas pelo autômato;
  • transições: o coração do autômato, diz para qual estado deve ir baseado no símbolo (ou caractere) lido na entrada, e no estado atual (é aqui que entra a função de memória dos estados);
  • estado inicial: onde deve começar a brincadeira;
  • estados finais: se o processamento terminar num estado de final, a string de entrada é considerada válida.

Em símbolos costuma ser assim (na mesma ordem da lista anterior):

M = (Q, Σ, δ, s, F)

Implementação em Python

Tudo muito legal, mas bom mesmo é quando tem código pra nos poupar do trabalho macacal de ficar rodando o AFD na mão, e melhor ainda se o código for em Python.😀

Essa implementação recebe uma 4-upla representando o autômato, mais a string a ser avaliada, retornando True ou False para indicar se a string faz parte da linguagem descrita pelo AFD, ou retorna None, para indicar parâmetros inválidos.

(
ALPHABET,
TRANSITION_FUNCTION,
START_STATE,
FINAL_STATES
) = range(4)

Como você deve ter reparado, o implementação em python recebe uma 4-upla, em lugar da 5-upla descrita anteriormente. O motivo é porque a lista de estados já está embutida na hash table que descreve a função de transição.

def process_string(machine, string):
    if not validate_machine(machine) or
       not validate_string(machine[ALPHABET], string):
        return None    # Processamento do automato.
    state = machine[START_STATE]
    for char in string:
        state = machine[TRANSITION_FUNCTION][state][char]

return (state in machine[FINAL_STATES])

As funções validate_* apenas testam a validade dos parâmetro, a implementação pode ser vista no código fonte (lá embaixo).

Exemplo

O AFD usado como exemplo reconhece a linguagem, sobre o alfabeto {0, 1}, composta de todas as strings que começam com 0, mais a string vazia. Sua representação em forma de grafo é a seguinte (hmm, parece um sapo de óculos):

AFD

Na formalidade, esse autômato M é descrito assim:

M = (Q, Σ, δ, s, F)

  • Q = {q1, q2}
  • Σ = {0, 1}
  • δ(q1, 0) = q1
    δ(q1, 1) = q2
    δ(q2, 0) = q1
    δ(q2, 1) = q2
  • s = q1
  • F = {q1}

Versão pythonizada do autômato:

  • Q: não é usado pelos motivos descritos acima
  • Σ: alphabet = set(['0', '1'])
  • δ: trans_func = {'q1' : {'0' : 'q1', '1' : 'q2'}, 'q2' : {'0' : 'q1', '1' : 'q2'}}
  • s: start_state = 'q1'
  • F: final_states = set(['q1'])

Chamo atenção para a forma de implementação da função de transição, usando dicionários. Dessa forma o equivalente pythonico à forma δ(q1, 0) é trans_func['q1']['0'].

Agora o código para testar algumas strings nesse AFD:

if __name__ == '__main__':
    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)

Código-fonte: automato.py

Agora você pode programar seus autômatos e testá-los mais rapidamente, além de gastar menos papel no processo, porque esse mundo está se acabando!

15 pensamentos sobre “Automatos Finitos em Python

  1. Cara, tri massa teu post!
    A gente está acostumado a ter essa parte com bastante teoria e, muitas vezes, falta tempo para pensar em uma implementação pura dos AFDs, ainda mais com as facilidades que os geradores de analisadores léxicos e as expressões regulares nos trazem…
    e em python fica mais legal ainda.🙂

  2. Pingback: Gerando Grafos de Automatos Finitos « Head Like a Hole

  3. Pingback: Máquina de Turing « Head Like a Hole

  4. buenas!
    pués, gostei do bichinho, cara!
    com a geração do grafo ficou mais legal ainda.🙂

    una cosita: ali na definição formal do autômato, na função de transição, acho que tem um errinho to tipo copy/paste🙂
    tó um patch que acho que corrige:

    2,3c2,3
    < δ(q2, 1) = q2
    δ(q1, 1) = q2
    > δ(q2, 0) = q1

    valeu, hombre!

  5. acho que consegui faze-lo rodar.. mas nao como eu esperava.. apareceu isso quando nao deu erro
    000001110010101010=TRue
    0000011=False
    —————
    Automato em formato “dot” do Graphviz..

    era isso que era pa aparecer??!

    o erro de identacao eu arrumei assim.. Edit-> select all fps Format->Untabify … e colokei 8

    me ajude

  6. Eu estava verificando justamente agora, que bom que funcionou. Quanto ao resultado era isso mesmo que devia acontecer de acordo com o trecho de código que vem depois de
    if __name__ == ‘__main__’:

    A idéia é mexer nessa parte pra colocar um autômato criado por você. Além disso ele cria esse arquivo “afd.dot” pra você gerar um grafo usando o GraphViz.

  7. Pingback: Máquinas de Turing São Dispositivos de Manipulação Simbólica « Head Like a Hole

  8. Gostei. Mais fugindo um pouquinho dessa linguagem gostaria de uma ajuda para calcular transições vazias de um AFN. Tô fazendo e c mais tá dando u, pouco de dor de cabeça. Se puder ajudar agradeço.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s