Autômato finito não determinístico

O autômato finito apresentado nos capítulos anteriores (abreviamos AF ou AFD) era sempre determinístico, o que se manifestava no fato de que, a cada momento, estava claro o que o autômato faria. Agora vamos olhar para o conceito mais geral dos autômatos finitos não determinísticos (abreviamos AFN), no qual podem existir transições que partem do mesmo estado e são para o mesmo símbolo.

Exemplo

Veja o diagrama de autômato a seguir:

O que há de estranho nele? Do nó q₀ saem duas arestas para o símbolo 0. Se tentarmos aceitar a palavra 001, pareceria que o autômato não saberia se deve permanecer no estado q₀ ou seguir a transição para q₁. Um autômato assim seria não determinístico.

Determinismo, nesse sentido, significa que em cada situação está claro o que o autômato fará, não há espaço para ambiguidade. O autômato determinístico tem, para cada estado e cada símbolo, apenas uma transição. O não determinismo indica ambiguidade — de um estado podem sair, por exemplo, três transições para o mesmo símbolo.

E como o autômato decide, então? O autômato não determinístico sempre escolhe (às vezes dizemos também que “adivinha”) a transição que leva a aceitar a palavra, se isso for possível.

Se dermos ao autômato a palavra 001, ele tem estas possibilidades de tratar a palavra:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

mais as possibilidades em que ele não lê a palavra inteira. Na primeira, ele permanecia sempre no estado q₀, o que com certeza pode, pois as regras de transição permitem. No segundo ramo, ele se arriscou a ir para os outros estados e por fim chegou ao estado q₂, que é final. Nesse ramo o autômato aceitaria a palavra. O autômato não determinístico escolhe sempre, automaticamente, o ramo em que aceita a palavra, se tal ramo existir.

Como ele faz para escolher automaticamente o ramo “favorável”? Podemos imaginar que o autômato não determinístico percorre todos os ramos possíveis e, se encontrar um ramo em que aceita a palavra, então aceita a palavra. Como ele poderia percorrer todos os ramos? Simplesmente, no momento em que está em um estado do qual saem n arestas para o símbolo atual, o autômato se copia n vezes, e cada cópia segue um caminho diferente. Assim, percorremos aos poucos todas as possibilidades.

Representação da computação do autômato em árvore

Vamos modificar levemente o autômato anterior:

O não determinismo permanece no primeiro estado. O autômato anterior aceitava todas as palavras que terminam em 01. Este autômato modificado aceita todas as palavras que contêm a subpalavra 01. Portanto, ele aceita, por exemplo, a palavra 101 ou 0101. Todos os ramos da computação podem ser visualizados com facilidade por meio de uma árvore; por exemplo, para a palavra 01010, a árvore poderia ser assim:

No começo estamos no estado inicial q₀. Na entrada temos a palavra 01010, e o primeiro caractere não lido é 0. Do estado q₀ saem duas transições para o símbolo 0, para os estados q₀ e q₁. A árvore terá, portanto, neste nó dois descendentes: q₀ e q₁. Em seguida lemos o símbolo 1. Aí não há ambiguidade nenhuma, passamos para os estados q₀ e q₂. Depois lemos o caractere 0; no ramo da esquerda surge de novo ambiguidade, e dividimos a computação em mais dois ramos. Em um deles permanecemos de novo em q₀, e no outro vamos para q₁. E assim por diante.

Observe que, ao todo, dois ramos terminam no estado q₂, um estado final. Existem dois ramos da computação pelos quais o autômato pode aceitar a palavra dada. Esse autômato aceitaria, portanto, a palavra 01010. Podemos tentar criar uma árvore semelhante para a palavra 1000.

A computação ou permanece no estado q₀ ou passa para o estado q₁, mas dali não tem para onde ir, porque na entrada só restam zeros e o estado q₁ tem transição apenas para o símbolo 1. Nenhum ramo da computação termina em um estado final, então o autômato não aceita a palavra 1000.

Transições ε

Nos autômatos não determinísticos podemos ainda usar transições ε. São transições que podemos fazer qualquer que seja o símbolo na entrada, e isso sem ler nenhum símbolo da palavra. Como poderíamos escrever um autômato não determinístico que aceitasse a palavra vazia, todas as palavras compostas apenas de uns e as palavras da forma (10)ⁿ, isto é, 10, 1010, …?

Dividimos o autômato em dois “subautômatos”. O de cima se encarrega de reconhecer as palavras compostas de 1, e o de baixo cuida das palavras da forma (10)ⁿ. Vamos tentar aceitar a palavra 111. No começo, o autômato está no estado q₀ e tem na entrada a palavra 111. Como tem à disposição transições ε, ele pode decidir passar para o estado q₁ ou q₂, conforme lhe convier. Vemos que lhe convirá passar para o estado q₁. O autômato vai para lá. Nesse momento, na entrada ele ainda tem a palavra 111! Só agora ele começa a ler os símbolos da palavra e a passar do estado q₁ de novo para q₁, até ler a palavra inteira e aceitá-la.

Se tentássemos aceitar 1010, o autômato passaria no começo para o estado q₂ e só a partir dali começaria a processar os símbolos e de novo aceitaria a palavra.

Para a palavra 1100, o autômato poderia fazer qualquer coisa, mas não tem como aceitar essa palavra.

As transições ε e o não determinismo facilitam o nosso trabalho em muitos aspectos; por exemplo, a demonstração de que a união de linguagens regulares é também uma linguagem regular pode ser escrita com transições ε de forma muito mais simples do que no caso dos autômatos finitos determinísticos. Nessa demonstração tínhamos exemplos destes autômatos

e depois construímos um autômato finito determinístico que aceitava a união das duas linguagens. Com transições ε, podemos montar esse autômato assim:

Simplesmente acrescentamos um novo estado inicial, dele saem duas transições ε para os estados iniciais originais dos autômatos originais, e é só isso. O autômato decide de forma não determinística se tenta aceitar a palavra com um ou com o outro “subautômato”.

Definição de autômato não determinístico

Já mostramos em que o autômato finito determinístico e o não determinístico se diferenciam; falta apenas formalizar. Definimos o autômato finito determinístico como uma quíntupla ⟨Q, Σ, δ, q₀, F⟩, em que Q é o conjunto de estados, Σ é o alfabeto, δ é a função de transição, q₀ é o estado inicial e F é o conjunto dos estados finais. A única coisa que muda na definição dos autômatos não determinísticos é a definição da função de transição.

Na versão determinística, a função, ao ser chamada como δ(q, w), podia devolver apenas um estado, enquanto na versão não determinística ela pode devolver vários estados — se para um símbolo estão definidas várias transições. Como precisamos definir também as transições ε, vamos denotar o conjunto Σ ∪ {ε} por Σ_ε, isto é, Σ_ε = Σ ∪ {ε}. A função δ é então definida como

$δ : Q \times Σ_{ε} \to 2^{Q}$

Esse 2^Q representa o conjunto das partes, o conjunto de todos os subconjuntos do conjunto Q. A formalização da computação é muito parecida com a dos autômatos finitos. A configuração do autômato é, de novo, um par ⟨q, w⟩ ∈ Q × Σ^∗. O passo de computação ↦ é uma relação no conjunto das configurações tal que

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

se, e somente se, q_j ∈ δ(q_i, w₀). Nesta frase estava a maior diferença. Nos autômatos determinísticos, tínhamos essa condição escrita como q_j = δ(q_i, w₀), porque a função δ devolvia sempre um único estado. A versão não determinística da função de transição devolve um conjunto de estados, por isso aparece ali o símbolo ∈. Vamos novamente representar o fecho reflexivo e transitivo da relação por ↦ ^∗. Dizemos que o autômato aceita a palavra w se, e somente se, existe q_f ∈ F tal que

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Fontes

Capítulos: Autômato finito, Autômato completo, Autômato finito não determinístico, Simulação de um autômato não determinístico, Conversão de AFN em AFD

« Anterior: Autômato completo

Próximo: Simulação de um autômato não determinístico »