Autómato finito não determinista
Um autómato finito não determinista é um autómato finito onde:
as transições estão associadas a símbolos individuais do alfabeto ou à palavra vazia (ε);
de cada estado saem zero ou mais transições por cada símbolo do alfabeto ou ε;
há um estado inicial;
há zero ou mais estados de aceitação, que determinam as palavras aceites;
uma dada palavra sobre o alfabeto faz o sistema avançar do estado inicial a zero ou mais estados finais, determinando estes a aceitação ou rejeição da palavra.
Os arcos múltiplos permitem alternativas de reconhecimento.
Os arcos ausentes representam quedas num estado de morte (estado não representado, logo implicando palavra não reconhecida).
AFND: exemplo
Um possível diagrama de transição para um AFND que reconhece a expressão regular (a|b)*abb é o seguinte:
É bem evidente o efeito do fecho de Kleene no diagrama, assim como a alternativa (a | b) e as sequências.
AFND: caminhos alternativos
Será que a palavra aabb pertence esta linguagem?
Existem 3 caminhos alternativos no diagrama:
Apenas o último termina no estado final.
Podemos representar estes caminhos com uma estrutura tipo árvore (deitada):
AFND: exemplo
Considerando o alfabeto A = {a;b;c}, que palavras são reconhecidas pelo autómato seguinte:
Como expressão regular: (a|b|c)*a(b|c)
AFND: exemplo com transições ε
Considere o seguinte AFND sobre o alfabeto A = {0;1}:
Há 6 caminhos possíveis:
AFND: exemplo com transições ε
Que palavras são reconhecidas por este autómato?
Todas as palavras terminadas em 11 ou 101.
Como expressão regular: (0|1)*10?1
AFND: definição formal
AFND: outro exemplo
Represente analiticamente o AFND:
Como expressão regular: (0|1)*1(0|ε)1
Ou alternativamente: (0|1)*1(0)?1
AFND: linguagem reconhecida
Tabelas de transição
Podemos representar um AFND por uma tabela de transição, em que as linhas correspondem aos estados, e as colunas aos símbolos de entrada incluindo a palavra vazia (Aε).
A tabela de transição para o AFND:
é a seguinte:
Last updated
