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 associado a um conjunto de estados de um autômato não determinístico. A (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 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 nessa lista, é preciso analisar o que acontece quando o próximo símbolo da sentença for , onde é cada um dos símbolos do alfabeto sob consideração na expressão regular. Por exemplo, se é um dos símbolos que pode ocorrer na sentença, então analisa-se, para cada um dos estados originais em , quais seriam os estados originais resultantes pela transição pelo símbolo . A desse conjunto de estados resultantes gera um novo estado (que eventualmente já pode ser um estado novo já existente). O autômato finito determinístico irá conter a transição .
Em outras palavras, para obter , obtenha o conjunto dos estados originais que podem ser alcançados através de uma transição pelo símbolo a partir de cada estado original no conjunto e compute . Se for um novo estado, inclua-o na lista de estados não-analisados. Se algum elemento de for um estado final no autômato original, então 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 é . Portanto, o novo estado inicial, , será dado por , ou
A lista de estados não-analisados contém . Para esse estado, é preciso analisar as transições resultantes para cada um dos dois símbolos do alfabeto, e .
O estado contém dois estados originais a partir dos quais existem transições com o símbolo , e . Os estados originais atingidos por essas transições são e . Portanto, e o estado atingido a partir de pela transição através do símbolo será , ou
Similarmente, a partir de pelo símbolo atinge-se o conjunto de estados e, portanto, resulta em
O estado foi retirado da lista de estados não-analisados, mas dois novos estados -- e -- foram incluídos. Esses dois novos estados precisam então ser analisados.
Da análise de , obtém-se que a transição pelo símbolo também levará ao estado , enquanto que a transição pelo símbolo leva aos estados originais , resultando em um novo estado, , gerado por ,
A análise de indica que a transição pelo símbolo leva ao estado , enquanto que a transição pelo símbolo leva ao próprio estado . Nenhum novo estado é criado.
O estado permanece na lista de estados não-analisados. A transição a partir dele pelo símbolo leva também ao estado . Pelo símbolo , o conjunto de estados originais resultantes é ; assim, um novo estado, , é gerado a partir do cômputo de ,
Esse estado, que é incluído na lista de estados não-analisados, é um estado final, pois contém o estado original final .
Finalmente, a análise de indica que a transição pelo símbolo leva ao estado , enquanto que a transição pelo símbolo leva ao estado .
Após a análise de , 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 , é apresentado na Figura 3.5a.
[Representação gráfica]
[Tabela de transição]
|
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.