sexta-feira, 24 de setembro de 2010

Exemplo de Autômato Usando Vaucanson

Vou mostrar em detalhes como desenhar um autômato usando o pacote Vaucanson.
Quero deixar claro que há outras maneiras mais simples de desenhar. Mas como eu passei trabalho neste autômato, achei melhor explicá-lo.

Vamos desenhar o seguinte autômato:
A seguir o código em latex:

\begin{center}
\MediumPicture\VCDraw{
\begin{VCPicture}{(0,-5)(8,3)}
% states
\FinalState[1]{(0,0)}{1} \State[2]{(3,0)}{2}
\LargeState \FinalStateVar[\{1,2\}]{(8,0)}{3}
\LargeState \FinalStateVar[\{2,3\}]{(3,-3)}{4}
% initial--final
\Initial{1}
% transitions
\EdgeL{1}{2}{a}\EdgeL{1}{4}{b}
\LoopN{2}{a} \EdgeL{2}{4}{b}
\EdgeL{3}{2}{a}\ArcL{3}{4}{b}
\LoopS{4}{b} \ArcL{4}{3}{a}
\end{VCPicture}
}
\end{center}


O comando \MediumPicture desenha a figura no tamanho médio.
Inicia-se a figura com \VCDraw{
\begin{VCPicture}{(0,-5)(8,3)} Estas duas coordenadas são as dimensões da figura.

O comando \FinalState[1]{(0,0)}{1} define um estado final. O [1] equivale ao rótulo do estado que aparecerá na figura, {(0,0)} é a coordenada que o estado irá ficar, e {1} é o nome dado para trabalhar com este estado, pode ser o mesmo que [1]. Muitas vezes não é possível, quando o rótulo é bem incrementado como este:
\FinalStateVar[\{1,2\}]{(8,0)}{3}. Perceba que o nome que irá na figura é {1,2}, mas no código eu chamo este estado de {3}.

Quando você quiser colocar fórmulas nos rótulos você deve usar o comando \FinalStateVar[]{}{}.

O comando \initial{1} define um estado inicial. (Pode ser mais que um, assim como os finais.)

Rá! A hora da fazer as transições! Você deve ter ideia de como é a figura, para saber quais como vão ficar as setas. Para isso, temos 3 opções aqui:

\EdgeL{1}{2}{a} Desenha uma aresta reta, que vai do estado 1 ao 2, e tem o símbolo a na transição.
\ArcL{3}{4}{b} Desenha uma aresta curva, que vai do estado 3 ao 4, e tem o símbolo b na transição.
\LoopN{2}{a} Faz o loop no estado 2, com o símbolo a.
Bem, acho que deu para dar uma ideia. Agora é só praticar!!
;)

Como Desenhar Autômatos e Grafos em LateX

Olá!!!

Hoje vou apresentar a vocês um pacote chamado Vaucanson para desenhar autômatos ou grafos em LaTeX. Nestes sites vocês encontram o pacote para download, o manual e toda documentação:


Segue um exemplo de autômato:
Bem, só há um problema... Você tem que digitar todo o seu autômato em Latex mesmo, por linha de comando.... Não há uma ferramenta gráfica pra isso. Mas... é só praticar que você consegue! (O manual é ótimo!)

Importante: Um bug que dá na compilação usando o Kile é que ele não gera automaticamente o .pdf. Você tem que gerar o .ps primeiro. E depois converter para .pdf, se quiser.

Estou usando e é o melhor que achei até agora!
Se alguém souber de outro me avise!

Aulas de Autômatos no Youtube

Olá!

Este vídeo sobre conversão de NFA para DFA é bem prático e simples de entender!


Para aprender a fazer o Fecho Epsilon:


Para minimização de DFA's, eu encontrei somente estes vídeos, são vários:


Adorei o exemplo, pois pares com mesmos estados sobram como equivalentes. Por exemplo, sobraram como equivalentes os pares: (s0,s1), (s0,s3), (s1,s3).

O que fazer? Uni-los e transformá-los em um só estado: (s0,s1,s3).
Depois é só verficar!

Bem era isso! ;)