Gerando Grafos de Automatos Finitos

Acrescentei uma função para gerar grafos no formato DOT dos autômatos finitos determinísticos usados naquele programa do meu último post sobre autômatos. Com isso tenho uma implementação que funciona mais uma visualização decente.

A função de geração é mostrada a seguir. Perdoe usar pontos como identação, é que o wordpress (sem plugins) foi amaldiçoado por um programador corcunda de COBOL com a incapacidade de indentar. O código decente pode ser visto em automato.py

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

(Queria ter colocado “Bitstream Vera Sans” no lugar de “Arial” como fonte, mas por motivos além da minha vontade estou num windão.)

O autômato no formato DOT é visto abaixo. Para fazer a seta que indica o estado inicial e que não parte de nenhum dos nós usei shape=point no nó start, cujo nome nem aparece por causa da forma escolhida.

digraph finite_state_machine {
....rankdir=LR;
....edge [fontname=arial,fontsize=11]
....node [fontname=arial,fontsize=11,shape=doublecircle];q1;
....node [shape=circle,size=8]
....start [shape=point]
....start -> q1
....q1 -> q1 [label=0]
....q1 -> q2 [label=1]
....q2 -> q1 [label=0]
....q2 -> q2 [label=1]
}

Tentei gerar um png mas saiu muito feio, cheio de rebarbas, a imagem abaixo foi gerada a partir do SVG gerado pelo dot (com o comando: dot -T svg -o afd.svg afd.dot).

AFD

Nota: para usar o dot é preciso instalar o pacote graphviz num sistema Debian/Ubuntu; se por algum motivo estranho você estiver no Windows pegue o GraphViz aqui.

4 pensamentos sobre “Gerando Grafos de Automatos Finitos

  1. Amigo,
    Boa tarde, estou fazendo um trabalho de compiladores e gerei um arquivo .dot, a partir um arquivo .flex. Gostaria de saber como fazer para converter meu arquivo .dot em um arquivo representando um automato finito deterministico?

    Obrigado

  2. Oi Daniel,
    se você gerou o arquivo .dot corretamente, basta rodar o comando

    dot -T png -o teuarquivo.png teuarquivo.dot

    e você terá seu grafo desenhado pelo GraphViz (neste exemplo, no formato PNG).

    Lembrando que pra um arquivo .dot descrever um grafo corretamente basta colocar linhas do tipo

    No1 -> No2
    No1 -> No3

    que indicam os nós com que cada nó se conecta.

  3. boenas!
    cara, usando teu automato.py pa testar um autômato pra reconhecer números em ponto flutuante.
    o grafo gerado pela generate_graph deu um pequeno probleminha na hora de converter, porque os labels não estavam escapados (labels simples como 0 e 1 funcionam, mas +, -, ., etc, dão problema. é só escapar)…
    quando puder, bota lá na linha 123 as guampa pro label funfiar bonitinho [label=\\”%s\\”]
    valeu!

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

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