Autómato finito não determinista
Last updated
Last updated
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).
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.
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):
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)
Considere o seguinte AFND sobre o alfabeto A = {0;1}:
Há 6 caminhos possíveis:
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
Represente analiticamente o AFND:
Como expressão regular: (0|1)*1(0|ε)1
Ou alternativamente: (0|1)*1(0)?1
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:
Como conjunto:
Um automato finito não determinista é um quíntuplo , em que:
