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)

Como conjunto:

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

Um automato finito não determinista é um quíntuplo , em que:

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: