next up previous contents
Next: Conversão para autômato finito Up: Análise léxica Previous: Autômatos finitos   Sumário

Construção do autômato finito não-determinístico

Na seqüência, apresenta-se o Algoritmo de Thompson para a construção de um autômato finito para reconhecer uma dada expressão regular. Esse procedimento determina como construir um autômato finito não-determinístico para reconhecer sentenças de uma gramática regular. Posteriormente, apresenta-se o procedimento para converter esse autômato para uma máquina determinística.

O primeiro passo do procedimento é decompor a expressão regular que define as sentenças que deverão ser reconhecidas em termos de suas relações elementares:

Uma vez que a expressão regular tenha sido estruturada em termos das relações elementares, é preciso construir um autômato para reconhecer cada uma das partes da expressão. Para cada relação elementar, a estrutura de um autômato correspondente é determinada.

Para reconhecer um símbolo $ a$ do alfabeto da linguagem $ \Sigma$, o autômato correspondente é composto simplesmente por um estado inicial que atinge um estado final através de uma transição pela ocorrência do símbolo $ a$ (Figura 3.3a).

Figura: Autômatos elementares para a construção de Thompson.
[Reconhecimento de um símbolo]
\includegraphics{umsimb.eps}
[Concatenação]
\includegraphics{concat.eps}


[Alternativa]
\includegraphics{altern.eps}
[Repetição]
\includegraphics{repet.eps}

Se a relação elementar for a concatenação de duas expressões regulares, $ R S$, é preciso compor as duas máquinas $ M_1$ e $ M_2$ que reconhecem $ R$ e $ S$, respectivamente. Para a máquina composta, o estado final de $ M_1$ é combinado com o estado inicial de $ M_2$ (Figura 3.3b).

Para reconhecer a relação elementar que estabelece a alternativa entre duas expressões regulares, $ R \vert S$, a forma de compor as duas respectivas máquinas $ M_1$ e $ M_2$ é através da introdução de um novo estado inicial. Este estado tem transições para os estados iniciais de cada uma das máquinas $ M_1$ e $ M_2$ através da string vazia. Similarmente, um novo estado final é introduzido, o qual pode ser atingido com transições pela string vazia a partir dos estados finais das duas máquinas originais (Figura 3.3c).

A última relação elementar a ser considerada é a repetição, $ R ^ * $, cuja máquina de reconhecimento deve ser derivada da máquina $ M_1$ que reconhece $ R$. Também neste caso novos estados inicial e final são introduzidos. Para reconhecer zero ocorrências de $ R$, há uma transição pela string vazia direta do novo estado inicial para o novo estado final. Para reconhecer uma ocorrência de $ R$, há transições pela string vazia entre o novo estado inicial e o estado inicial original, assim como entre o estado final original e o novo estado final. Finalmente, o reconhecimento de várias ocorrências de $ R$ dá-se através de uma transição pela string vazia do estado final para o estado inicial da máquina original $ M_1$ (Figura 3.3d).

A título de exemplo, considere a construção de um um autômato finito não-determinístico para reconhecer sentenças descritas pela expressão regular $ R = (a\vert b)^*abb$. O primeiro passo é decompor a expressão em termos de suas relações elementares:

$ R_1 = a$   $ R_2 = b$
$ R_3 = R_1\vert R_2$   $ R_4 = {R_3}^*$
$ R_5 = R_4R_1$   $ R_6 = R_5R_2$
$ R = R_6 R_2 $

Uma vez determinadas as expressões regulares elementares que compõem a expressão regular sob análise, é possível construir os autômatos que reconhecem cada uma dessas expressões elementares.

Para reconhecer a expressão $ R_1$, constrói-se a máquina $ M_1$ que reconhece o símbolo $ a$, usando a construção apresentada na Figura 3.3a:

\includegraphics[scale=.8]{n1.eps}

Similarmente, para reconhecer $ R_2$, constrói-se a máquina $ M_2$ que reconhece o símbolo $ b$:

\includegraphics[scale=.8]{n2.eps}

A expressão regular $ R_3$ é a composição pela alternativa das expressões $ R_1$ e $ R_2$. O autômato para reconhecer $ R_3$ é construído pela combinação das máquinas $ M_1$ e $ M_2$ conforme a estratégia apresentada na Figura 3.3c:

\includegraphics{n3.eps}
Neste caso, os estados 5 e 6 são os novos estados introduzidos respectivamente como o estado inicial e o estado final da nova máquina $ M_3$.

O reconhecimento da expressão regular $ R_4$ é feito pelo autômato que reconhece zero ou mais ocorrências de $ R_3$, ou seja, a máquina $ M_4$ é construída a partir da máquina $ M_3$ conforme a estratégia apresentada na Figura 3.3d:

\includegraphics{n4.eps}
Observe-se que os novos estados inicial e final de $ M_4$ passam a ser os estados 7 e 8, respectivamente.

Como a expressão $ R_5$ é formada pela concatenação de $ R_4$ com $ R_1$, a máquina $ M_5$ deve combinar a máquina $ M_4$ com uma nova instância da máquina $ M_1$ segundo a estratégia apresentada na Figura 3.3b:

\includegraphics{n5.eps}
Observe que o estado inicial da nova máquina $ M_1'$, $ 1'$, foi combinado com o estado final da máquina $ M_4$, enquanto que o estado final de $ M_1'$, $ 2'$, passou a ser o estado final de $ M_5$.

Similarmente, $ R_6$ é uma concatenação de $ R_5$ e $ R_2$. Combinando a máquina $ M_5$ com uma nova instância da máquina que reconhece $ R_2$, obtém-se para a máquina $ M_6$:

\includegraphics{n6.eps}

Finalmente, a expressão completa é uma concatenação de $ R_6$ com $ R_2$. Combinando $ M_6$ com uma máquina $ M_2''$ obtém-se a máquina que reconhece a expressão regular completa, que é apresentada na Figura 3.4. Para essa máquina, o estado inicial é o estado inicial de $ M_6$, ou seja, o estado 7, e o estado final é o estado final de $ M_2''$, o estado $ 4''$.

Figura: Autômato não-determinístico que reconhece $ (a\vert b)^*abb$
\includegraphics{n7.eps}


next up previous contents
Next: Conversão para autômato finito Up: Análise léxica Previous: Autômatos finitos   Sumário
Ivan L. M. Ricarte 2003-02-14