Autômatos Finitos, Expressões Regulares e Lema do Bombeamento

AFN com ε‑transições: definições e exemplo

Definição: Para q ∈ Q define‑se a ε‑fecho (ε‑closure) de q como: ε‑closure(q) = { p | existe uma transição rotulada ε de q para p }.

Denotamos por d(q) o conjunto de estados que são diretamente alcançáveis a partir de q por uma transição rotulada por um símbolo a (ou por transições imediatas).

Exemplo / procedimento para remover ε‑transições (AFN ε → AFN sem ε):

1. Calcule a ε‑fecho de todos os estados.
2. Desenhe o autômato inicial sem as ε‑transições (substituindo transições apropriadas pelas obtidas usando ε‑fechos).
3. Para cada estado q e símbolo a, defina as novas transições como a união das transições a partirem de todos os estados em ε‑closure(q), possivelmente tomando depois o ε‑closure do conjunto resultante. Em notação comum: δ'(q,a) = ε‑closure( ⋃_{p∈ε‑closure(q)} δ(p,a) ).

Desenhe setas com o símbolo a de q para todos os p_i obtidos. Este processo garante que, em cada estado, as transições por cada símbolo sejam explícitas (sem ε).

Conversão: Expressões Regulares → Autômato Finito (ER → AF)

Casos base: as expressões regulares básicas correspondem a autômatos simples (∅, ε, e símbolo a).

Caso recursivo: para operações de união, concatenação e estrela de Kleene, constrói‑se autômatos para os operandos e combina‑se os autômatos resultantes (por exemplo, usando novos estados iniciais/finais e ε‑transições, ou construções sem ε conforme necessário).

Sejam M1 = (Q1, s1, F1) reconhecendo L(r1) e M2 = (Q2, s2, F2) reconhecendo L(r2); então existem construções padrão de autômatos para L(r1) ∪ L(r2), L(r1)·L(r2) e L(r1)*.

Conversão: Autômato Finito → Expressão Regular (AF → ER)

A classe das linguagens aceitas por autômatos finitos é a mesma das linguagens definidas por expressões regulares. O conjunto de linguagens regulares é fechado sob união, concatenação e estrela de Kleene.

Para converter um autômato em expressão regular pode‑se construir equações regulares por estado e resolver o sistema usando o Lema de Arden. Essa técnica associa a cada estado q_i uma expressão regular A_i que descreve as palavras que levam de q_i a um estado final.

Lema de Arden

Enunciado: Se A e B são expressões regulares e X é variável tal que X = A·X ∪ B, então a solução única é X = A*·B. Este lema é usado para resolver os sistemas lineares de equações regulares obtidos a partir de um autômato.

Propriedades de linguagens regulares

Quando uma linguagem L é regular? Algumas condições suficientes/necessárias:

• Se L é finita, então L é regular.
• Se existe uma expressão regular r tal que L(r) = L, então L é regular.
• Se existe um autômato finito M tal que L(M) = L, então L é regular.

Para testar se uma linguagem é regular costuma‑se tentar construir um autômato ou uma expressão regular. Para provar que uma linguagem não é regular, usa‑se normalmente o Lema do Bombeamento (pumping lemma) como técnica de contraposição (procurar um contra‑exemplo ao lema).

Lema do Bombeamento (para linguagens regulares)

Se L é regular e infinita, então existe uma constante k (dependente da linguagem/autômato) tal que qualquer palavra w ∈ L com |w| >= k pode ser decomposta como w = u v x, satisfazendo:

• |v| >= 1
• |u v| <= k
• para todo i >= 0, u vⁱ x ∈ L

O lema do bombeamento provê uma propriedade que deve ser satisfeita por toda linguagem regular e, portanto, fornece uma maneira de demonstrar que uma linguagem não é regular — basta encontrar uma palavra que viole as condições do lema.

Teoremas práticos sobre autômatos (intuições)

Se M é um AFD com k estados, então:

• Se L(M) ≠ ∅, existe uma palavra aceita cuja comprimento é menor que k (por eliminação de ciclos repetidos no caminho de aceitação).
• L(M) é infinito ⇔ existe um ciclo acessível que leva a um estado final (isto é, existe um loop que possibilita formar cadeias arbitrariamente longas aceitas por M).

Na prática, ao analisar M, devemos:

1. Eliminar todos os estados que não possuem caminho para algum estado final (estados inacessíveis ao conjunto de finais). Se a remoção do estado inicial fizer com que não exista mais caminho de aceitação, então L(M) = ∅.
2. Eliminar estados sumidouros (sinks) quando apropriado. Se ainda existirem ciclos após essas remoções, então L(M) é infinito.

Complemento de uma linguagem regular

Para obter o complemento de uma linguagem regular L (supondo alfabeto fixo), constrói‑se um AFD que reconheça L e troca‑se os estados finais pelos não finais (e vice‑versa). O resultado reconhece o complemento de L.

Observações finais

Resumo: os procedimentos principais apresentados incluem (i) eliminação de ε‑transições em AFN, (ii) conversões ER ↔ AF (com uso do Lema de Arden para AF → ER), (iii) propriedades de fechamento (união, concatenação, Kleene) e (iv) técnicas para provar não‑regularidade (Lema do Bombeamento). Para construção do complemento é suficiente trabalhar com AFD e inverter os estados finais.