Bom, eu ainda não compreendo a lógica de se utilizar ε-transições na NFA, qual o real significado? Pular de estado sem efetuar uma leitura?
Por exemplo, dada a regex:
a*
NFA:
DFA:
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeBom, eu ainda não compreendo a lógica de se utilizar ε-transições na NFA, qual o real significado? Pular de estado sem efetuar uma leitura?
Por exemplo, dada a regex:
a*
NFA:
DFA:
A resposta do Anthony está perfeita, mas eu já estava escrevendo então vou postar porque pode ser de ajuda complementar.
Os dois autômatos (1) e (2) são equivalentes. A diferença bem explicada pelo Anthony é que as transições Epsilon (ou Lambda) permitem a mudança de estados sem consumir caracteres, funcionando quase como se o autômato mudasse de estado "sozinho" (o "não determinístico" no nome vem justamente do fato de que as mudanças podem ocorrer arbitráriamente, e não apenas para um único estado bem definido para cada símbolo, como nos AFD).
Assim:
a expressão regular a*
deve aceitar apenas uma entrada vazia (nenhum símbolo) ou uma entrada com um ou mais símbolos a
(por exemplo, a
, aa
, aaa
, ...).
no caso do AFD (2), ambos os estados são de aceitação. Então, se o autômato receber uma entrada vazia, ele encerra aceitando-a porque estará no estado 0 (que é o inicial); senão, ao ler o primeiro símbolo a
, muda para o estado 1, de onde não sai mais enquanto ler símbolos a
da entrada, eventualmente terminando e aceitando-a ao acaber de ler tudo.
no caso do AFN-ε (1), apenas o estado 3 é de aceitação - sendo que o estado 0 é o inicial. Se a entrada for vazia, pode-se entender que eventualmente (em um momento arbitrário) o estado do autômato será alterado de 0 para 3 porque há uma transição-epsilon ligando esses dois estados. E nesse caso, ele aceitará a entrada vazia. Porém, o autômato pode também mudar para o estado 1 de forma arbitrária, de onde precisará ler ao menos um símbolo a
para seguir para o estado 2 (nessa transição particular, de forma determinística), de onde pode voltar ao estado 1 ou seguir para o estado 3 também de forma não determinística. Assim, ele só aceitará a entrada quando ela for vazia, sendo que ele passou diretamente do estado 0 para o estado 3; ou quando a entrada não for vazia, sendo que ele passou do estado 0 para o estado 1, do estado 1 para o estado 2 ao menos uma vez (podendo circular entre os estados 2, 1 e 2 novamente para cada novo símbolo lido), e finalmente do estado 2 ao estado 3.
Note que esses autômatos são apenas modelos conceituais de máquinas computacionais processadoras de uma entrada simbólica, e a ideia de usar um AFN-ε é porque certos problemas são mais facilmente descritos (usando menos estados também) dessa forma. Mas como sempre é possível converter um AFN-ε em um AFD (há provas matemáticas desse fato), qualquer propriedade testada em um é válida para o outro.
Note também que os seus exemplos assumem que o alfabeto Σ contém apenas o símbolo a
. Se a entrada pudesse também ter o símbolo b
(por exemplo, aaaabbab
), o próprio AFD não estaria correto por não ter transição(ões) para o símbolo b
.
Exatamente. Transições Epsilon permitem a mudança de estado sem consumir caracteres da cadeia de entrada. Essa característica aliada a possibilidade de mudar para mais do que um estado ao mesmo tempo caracterizam autômatos finitos não determinísticos (na verdade uma variação dos AFNDs conforme artigo da Wikipedia).