Conversão de expressão regular em autômato

Vamos mostrar como converter qualquer expressão regular em um autômato finito não determinístico.

Exemplo

Antes de descrever o algoritmo em si, vamos mostrar em um exemplo aonde queremos chegar. Considere esta expressão regular: a(b|c)x^∗. Em palavras, descreveríamos a linguagem que a expressão regular gera como as palavras que começam com a letra “a”, seguida ou da letra “b” ou da “c” e depois de qualquer quantidade de letras “x”. Conseguiríamos construir um autômato que aceitasse essa linguagem? Claro que sim, veja:

Esse autômato evidentemente aceita a mesma linguagem. Surge, assim, a pergunta: será que, para toda expressão regular, existe um autômato que aceita a linguagem dada? Existe, sim.

Descrição do algoritmo de conversão de expressão regular em autômato

Supomos que na entrada temos a expressão regular R. Pela parte anterior, sobre expressões regulares, sabemos que a expressão regular pode ter, ao todo, seis formas diferentes. Distinguimos, assim, seis casos diferentes:

1. R = a para algum símbolo a ∈ Σ. Ou seja, a expressão regular é apenas um símbolo do alfabeto Σ sobre o qual trabalhamos. O autômato que aceitaria um único símbolo a seria assim:

   

2. R = ϵ, a palavra vazia. O autômato que aceitaria a palavra vazia seria assim:

   

3. R = ∅, a expressão regular que gera a linguagem vazia. O autômato que reconheceria essa linguagem é este:

   

4. R = R₁ ∪ R₂, em que R₁, R₂ são expressões regulares. Nós já sabemos que a união de linguagens regulares é de novo uma linguagem regular e que conseguimos construir um autômato que aceita essa linguagem. Em outras palavras, supomos que temos autômatos que reconhecem a linguagem gerada pelas expressões R₁ e R₂ e, com eles, construímos o autômato que aceita a linguagem gerada pela expressão R₁ ∪ R₂. Exemplo: se R₁ = a e R₂ = ϵ, então, pelo procedimento, obtemos este autômato:

   

5. R = R₁ ∘ R₂, em que R₁, R₂ são expressões regulares. É o mesmo caso do item anterior. A concatenação de linguagens regulares é uma linguagem regular, e por isso conseguimos construir um autômato que aceitará essa linguagem. Então, se R₁ = a, R₂ = b, a concatenação seria assim:

   

6. $R=(R_1^{\ast })$, em que R₁ é uma expressão regular. De novo sabemos que o fecho de uma linguagem regular é uma linguagem regular. Então, se R = a^∗, o autômato seria assim:

   

Aplicando esses itens sucessivamente, convertemos a expressão regular inteira em um autômato finito.

Exemplo completo

Vamos tentar converter a expressão regular (a|bc)^∗. Obtemos, sucessivamente, estes autômatos:

Esse autômato resultante aceita a linguagem gerada pela expressão regular (a|bc)^∗. É claro que o autômato é terrivelmente complicado e com certeza existe um autômato muito mais simples que aceita a mesma linguagem. Podemos usar o algoritmo de conversão de AFN em AFD e, em seguida, fazer a minimização do autômato.

Fontes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools