next up previous contents
Next: Minimização de estados Up: Análise léxica Previous: Construção do autômato finito   Sumário

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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)$,

$\displaystyle 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)$,

$\displaystyle 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]
\includegraphics{nd.eps}
[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.


next up previous contents
Next: Minimização de estados Up: Análise léxica Previous: Construção do autômato finito   Sumário
Ivan L. M. Ricarte 2003-02-14