IV EXPRESSÕES REGULARES E LINGUAGENS REGULARES (CONJUNTOS REGULARES) Um dos problemas que estudamos em Máquinas de Estado Finito é a caracterizaç...

IV EXPRESSÕES REGULARES E LINGUAGENS REGULARES (CONJUNTOS REGULARES)
Um dos problemas que estudamos em Máquinas de Estado Finito é a caracterização da linguagem reconhecida por um AFD, que deve ser exata, ou seja, “incluir” todas as seqüências reconhecidas e “excluir” todas as que serão rejeitadas pelo autômato.
Em muitos casos, a descrição exata de um conjunto de sequências em uma linguagem natural, como o português, pode não ser muito simples. Algum tipo de ambiguidade ou incompletude pode impor alguma informação extra e redundante, para melhor caracterização da linguagem reconhecida.
Uma solução para este problema é a utilização de outro tipo de linguagem, simbólica e universal, que facilita a correta caracterização de determinadas linguagens de um dado alfabeto.
Este capítulo estuda expressões regulares e linguagens regulares, que formam a linguagem simbólica universal para a caracterização de conjuntos reconhecidos por autômatos finitos, o que é provado pelo Teorema de Kleene, que será visto adiante.
IV.1 DEFINIÇÃO: EXPRESSÕES REGULARES
Expressões regulares são expressões formadas a partir de um dado alfabeto I, e conterão os símbolos deste alfabeto, além de operadores específicos. Para diferentes alfabetos, temos novas expressões regulares com símbolos do alfabeto considerado. O texto abaixo (apostila, pág. 443) define as expressões regulares com os símbolos de um alfabeto I:

• Os itens 1. e 2. compõem a base da definição por recorrência, e definem as expressões regulares “simples” ou “elementares”:
1. Os símbolos ∅ e λ são expressões regulares. Esta definição vale para qualquer alfabeto I.
2. Cada símbolo i pertencente ao alfabeto I é, por si só, uma expressão regular.
• O item 3. é o passo da recorrência, e define expressões regulares complexas, formadas a partir de outras expressões regulares mais simples:
(a) AB é formada pela concatenação da expressão regular A com a expressão regular B;
(b) A ∨ B é formada pela “operação” ou entre as expressões regulares A e B;
(c) A* é formada pela “operação” estrela aplicada sobre uma única expressão regular A.
Temos então alguns exemplos de expressões regulares formadas pelo alfabeto I = { a, b }:
∅ λ a b expressões básicas
aa ab ba bb item 3a – concatenação
a ∨ b b ∨ a item 3b – ou
a* b* item 3c – estrela
As expressões regulares “geradas” pelo item 3 podem ser “recombinadas” da mesma forma, gerando expressões mais complexas. Temos, por exemplo, as expressões regulares:
(a ∨ b)* item 3c: operação estrela aplicada sobre a expressão regular a ∨ b
a ∨ (b*) item 3b: operação ou aplicada às expressões regulares a e b*
Interessante notar que, na definição de alguma linguagem simbólica, a utilização de parênteses visa estabelecer a ordem de avaliação dos operadores, como nos exemplos acima. Além disso, geralmente é estabelecida uma convenção para a precedência de operadores, visando diminuir uma quantidade excessiva de parênteses. Com expressões regulares isso também acontece, e a convenção universalmente aceita estabelece a seguinte precedência:
1. maior precedência – operador * (estrela)
2. média precedência – operador de concatenação
3. menor precedência – operador ∨ (ou)
Vejamos mais exemplos de expressões regulares formadas por I = { a, b }, aplicando a convenção de precedência estabelecida (ou seja, sem parênteses desnecessários):
(a ∨ b)* estrela aplicada à expressão regular a ∨ b
a ∨ b* operação ou entre a expressão regular a e a expressão regular b

aa ∨ b operação ou entre a expressão regular aa e a expressão regular b
a (a ∨ b) concatenação de a com a ∨ b

aa* concatenação de a com a*
(aa)* estrela aplicada à expressão regular aa

aa ∨ b* ou entre as expressões regulares aa e b*
a (a ∨ b*) concatenação da expressão regular a com a expressão regular a ∨