Conversão para autômato finito determinístico

Autômatos finitos não-determinísticos precisam lidar com situações de ambigüidade, como no caso de um estado a partir do qual parte mais de uma transiçao vazia. É possível eliminar essas ambigüidades através da construção de um autômato finito determinístico que é equivalente a um autômato finito não-determinístico.

O procedimento aqui apresentado é freqüentemente denominado de construção de subconjuntos. Na descrição a seguir, o termo ``estado original'' refere-se a um estado do autômato não-determinístico, enquanto o termo ``novo estado'' refere-se a estados do autômato determinístico.

A base desse procedimento é criar novos estados que representem todas as possibilidades de estados originais em um dado momento da análise da sentença em processo de reconhecimento. Para tal, define-se o conjunto $\epsilon^*$ associado a um conjunto de estados de um autômato não determinístico. A $\epsilon^*$ (lê-se épsilon-clausura) é o conjunto que inclui cada um dos estados indicados e todos os estados alcançáveis a partir dele através de transições por strings vazias. O resultado é um conjunto de estados que irá representar um novo estado no autômato determinístico.

O procedimento da construção de subconjuntos começa pela computação da $\epsilon^*$ do conjunto que contém o estado inicial original. Neste caso, obtém-se um conjunto de estados que irá representar o novo estado inicial, pois o conjunto resultante inclui o estado inicial original.

Cada estado novo que é criado precisa ser posteriormente analisado. Para tanto, constrói-se uma lista de estados não-analisados que, inicialmente, contém apenas o novo estado inicial.

O procedimento prossegue com a análise dos novos estados ainda não analisados. Para cada novo estado $s$ nessa lista, é preciso analisar o que acontece quando o próximo símbolo da sentença for $\alpha$, onde $\alpha$ é cada um dos símbolos do alfabeto sob consideração na expressão regular. Por exemplo, se $\alpha_1$ é um dos símbolos que pode ocorrer na sentença, então analisa-se, para cada um dos estados originais em $s$, quais seriam os estados originais resultantes pela transição pelo símbolo $\alpha_1$. A $\epsilon^*$ desse conjunto de estados resultantes gera um novo estado $t$ (que eventualmente já pode ser um estado novo já existente). O autômato finito determinístico irá conter a transição $s\stackrel{\alpha}{\longrightarrow} t$.

Em outras palavras, para obter $t$, obtenha o conjunto $T_\alpha$ dos estados originais que podem ser alcançados através de uma transição pelo símbolo $\alpha$ a partir de cada estado original no conjunto $s$ e compute $\epsilon^*(T_\alpha)$. Se $t$ for um novo estado, inclua-o na lista de estados não-analisados. Se algum elemento de $t$ for um estado final no autômato original, então $t$ será um estado final no novo autômato.

A análise dos novos estados ainda não analisados deve prosseguir até que essa lista torne-se vazia. Quando isso ocorre, o procedimento está encerrado e o autômato finito determinístico está definido.

Como exemplo, considere a conversão do autômato não-determinístico da Figura 3.4 para um autômato determinístico através da aplicação desse procedimento.

O conjunto de estados originais daquele autômato é $T_0 = \{7\}$. Portanto, o novo estado inicial, $s_0$, será dado por $\epsilon^*(T_0)$, ou

$$s_0 = \{ 1, 3, 5, 7, 8\}$$

A lista de estados não-analisados contém $s_0$. Para esse estado, é preciso analisar as transições resultantes para cada um dos dois símbolos do alfabeto, $a$ e $b$.

O estado $s_0$ contém dois estados originais a partir dos quais existem transições com o símbolo $a$, $1$ e $8$. Os estados originais atingidos por essas transições são $2$ e $2'$. Portanto, $T_1 = \{2, 2'\}$ e o estado atingido a partir de $s_0$ pela transição através do símbolo $a$ será $s_1 = \epsilon^*(T_1)$, ou

$$s_1 = \{1, 2, 2', 3, 5, 6, 8\}$$

Similarmente, a partir de $s_0$ pelo símbolo $b$ atinge-se o conjunto de estados $T_2 = \{4\}$ e, portanto, $s_2 = \epsilon^*(T_2)$ resulta em

$$s_2 = \{1, 3, 4, 5, 6, 8\}$$

O estado $s_0$ foi retirado da lista de estados não-analisados, mas dois novos estados -- $s_1$ e $s_2$ -- foram incluídos. Esses dois novos estados precisam então ser analisados.

Da análise de $s_1$, obtém-se que a transição pelo símbolo $a$ também levará ao estado $s_1$, enquanto que a transição pelo símbolo $b$ leva aos estados originais $T_3 = \{4, 4'\}$, resultando em um novo estado, $s_3$, gerado por $\epsilon^*(T_3)$,

$$s_3 = \{1, 3, 4, 4', 5, 6, 8\}$$

A análise de $s_2$ indica que a transição pelo símbolo $a$ leva ao estado $s_1$, enquanto que a transição pelo símbolo $b$ leva ao próprio estado $s_2$. Nenhum novo estado é criado.

O estado $s_3$ permanece na lista de estados não-analisados. A transição a partir dele pelo símbolo $a$ leva também ao estado $s_1$. Pelo símbolo $b$, o conjunto de estados originais resultantes é $T_4 = \{4, 4''\}$; assim, um novo estado, $s_4$, é gerado a partir do cômputo de $\epsilon^*(T_4)$,

$$s_4 = \{ 1, 3, 4, 4'', 5, 6, 8 \}$$

Esse estado, que é incluído na lista de estados não-analisados, é um estado final, pois contém o estado original final $4''$.

Finalmente, a análise de $s_4$ indica que a transição pelo símbolo $a$ leva ao estado $s_1$, enquanto que a transição pelo símbolo $b$ leva ao estado $s_2$.

Após a análise de $s_4$, a lista de estados não-analisados ficou vazia, indicando a conclusão do processo de conversão do autômato. O autômato determinístico resultante, que reconhece sentenças expressas por $(a\vert b)^*abb$, é apresentado na Figura 3.5a.

Figura: Autômato finito determinístico que reconhece $(a\vert b)^*abb$

[Representação gráfica]

[Tabela de transição]

	$s_0$	$s_1$	$s_2$	$s_3$	$s_4$
a	$s_1$	$s_1$	$s_1$	$s_1$	$s_1$
b	$s_2$	$s_3$	$s_2$	$s_4$	$s_2$

Para fins computacionais, a representação mais adequada para autômatos é aquela na forma de tabelas de transição. Para esse autômato, a tabela correspondente é apresentada na Figura 3.5b.