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:

• um símbolo do alfabeto da linguagem;
• concatenação, $R S$;
• alternativa, $R \vert S$;
• repetição, $R ^ *$.

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]

[Concatenação]

[Alternativa]

[Repetição]

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:

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

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:

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:

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:

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$:

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$