Capítulo 4 — Propriedades das Linguagens Regulares

Lema do Bombeamento, Fechamento, Decisão e Minimização

Como provar que linguagens NÃO são regulares, propriedades de fechamento e algoritmos de decisão

Baseado em: Hopcroft, Motwani & Ullman — Cap. 4

1. Lema do Bombeamento (§4.1)

Seja L uma linguagem regular. Então existe uma constante n (o "comprimento de bombeamento") tal que, para todo string w ∈ L com |w| ≥ n, podemos dividir w = xyz onde:

  1. y ≠ ε  (a parte do meio não é vazia)
  2. |xy| ≤ n  (x e y cabem nos primeiros n caracteres)
  3. Para todo k ≥ 0, xykz ∈ L  (podemos "bombear" y qualquer número de vezes)
Intuição: Se L é regular, algum DFA com n estados a aceita. Qualquer string com ≥ n caracteres força o DFA a repetir um estado (princípio da casa de pombos). O loop entre as repetições é y — podemos percorrê-lo 0, 1, 2, ... vezes e o DFA ainda aceita.
Para que serve: O lema é usado como prova por contradição. Se assumimos que L é regular mas encontramos um string que NÃO pode ser bombeado, temos uma contradição → L não é regular. O lema não serve para provar que L É regular.

Exemplo 4.2 — Leq = { 0n1n : n ≥ 1 } não é regular

⚡ Interativo — clique em cada passo da prova
1. SUPOSIÇÃO Suponha por contradição que Leq é regular. Pelo lema, existe n.
2. ESCOLHA Clique para revelar...
3. DIVISÃO Clique para revelar...
4. BOMBEAMENTO Clique para revelar...
5. CONTRADIÇÃO Clique para revelar...

Simulador de Bombeamento — w = 0n1n

n = 4 → w = 0000·1111 → escolha |y| e veja o resultado de xykz
|y| =

Exemplo 4.3 — Lpr = { 1p : p é primo } não é regular

⚡ Interativo — clique em cada passo
1. SUPOSIÇÃO Suponha por contradição que Lpr é regular. Pelo lema, existe n.
2. ESCOLHA Clique para revelar...
3. DIVISÃO Clique para revelar...
4. BOMBEAMENTO Clique para revelar...
5. CONTRADIÇÃO Clique para revelar...

Exemplo 4.4 — L = { ww : w ∈ {0,1}* } não é regular

⚡ Clique em cada passo
1. SUPOSIÇÃO Suponha que L = {ww} é regular. Pelo lema, existe n.
2. ESCOLHA Clique para revelar...
3. DIVISÃO Clique para revelar...
4. BOMBEAMENTO Clique para revelar...
5. CONTRADIÇÃO Clique para revelar...

Exemplo 4.7 — Usando Fechamento para provar não-regularidade

Problema: Provar que M = { w ∈ {0,1}* : #0(w) ≠ #1(w) } não é regular. O lema do bombeamento é difícil de aplicar diretamente aqui (bombear y não muda a desigualdade necessariamente). Mas podemos usar fechamento sob complemento.
⚡ Clique em cada passo
1. ESTRATÉGIA M = complemento de Leq = {w : #0 = #1}. Se M é regular, pelo fechamento sob complemento, Leq = M̄ também é regular.
2. INTERSEÇÃO Clique para revelar...
3. CONTRADIÇÃO Clique para revelar...

2. Propriedades de Fechamento (§4.2)

Se L e M são linguagens regulares, as operações abaixo também produzem linguagens regulares:

OPERAÇÃODEFINIÇÃOREGULAR?COMO PROVAR
L ∪ Mstrings em L ou M✓ SIMRegex: R + S
L ∩ Mstrings em L e M✓ SIMDe Morgan: L̄ ∪ M̄ (barra)
L̄ (complemento)Σ* − L✓ SIMInverter F no DFA
L − Mstrings em L mas não em M✓ SIML ∩ M̄
LR (reverso)strings de L invertidos✓ SIMInverter arcos, trocar F ↔ q₀
h(L) (homomorfismo)substituir símbolos por strings✓ SIMSubstituir na regex
h⁻¹(L) (inverso)pré-imagem de h✓ SIMConstrução sobre DFA
Uso prático: O fechamento permite provar que linguagens NÃO são regulares sem usar o lema do bombeamento diretamente. Se L ∩ R não é regular e R é regular, então L não pode ser regular (senão a interseção seria regular por fechamento). Exemplo 4.7 do livro usa essa técnica.

Exemplo 4.6 — Complemento na prática

CONSTRUÇÃO DO COMPLEMENTO DFA para L = L((0+1)*01) = strings que terminam em 01
DFA para L̄ = strings que NÃO terminam em 01

Método: pegar o DFA de L e inverter os estados de aceitação.
Se q ∈ F → q ∉ F'   ·   Se q ∉ F → q ∈ F'

Exemplo 4.15 — Homomorfismo

Definição: Um homomorfismo h : Σ → T* substitui cada símbolo do alfabeto por um string. Aplicar h a uma linguagem L significa aplicar a substituição a cada string de L.
EXEMPLO RESOLVIDO L = L((00+1)*) = strings de 0's e 1's onde 0's sempre aparecem em pares
Homomorfismo: h(a) = 01, h(b) = 10

h⁻¹(L) = { w ∈ {a,b}* : h(w) ∈ L } = ?

h(a) = 01 → o 0 isolado não casa com (00+1)* → a não pode aparecer sozinho
h(b) = 10 → o 0 no final precisa de outro 0 → h(ba) = 1001 ∈ L ✓
h(baba) = 10·01·10·01 = 10011001 ∈ L ✓

h⁻¹(L) = L((ba)*) = repetições do padrão "ba" (incluindo ε).
Regularidade preservada: L regular → h⁻¹(L) regular. ✓

3. Propriedades de Decisão (§4.3)

L(A) = ∅ ?
Testar se algum estado de aceitação é alcançável a partir de q₀. Busca em grafo: O(n²).
w ∈ L(A) ?
Simular o DFA em w. Se termina em F, aceita. Tempo O(|w|).
L(A) é finita?
Verificar se existe ciclo nos estados alcançáveis que leva a F. Se sim, infinita. Busca em grafo.
L(A) = L(B) ?
Calcular a diferença simétrica: (L(A) − L(B)) ∪ (L(B) − L(A)). Se vazia, são equivalentes. Usa o autômato produto.
L(A) ⊆ L(B) ?
Verificar se L(A) ∩ L(B̄) = ∅. Se sim, toda cadeia de A também está em B.

4. Minimização de DFA (§4.4)

Dois estados p e q são distinguíveis se existe um string w tal que δ̂(p,w) ∈ F e δ̂(q,w) ∉ F (ou vice-versa).
Se não são distinguíveis, são equivalentes e podem ser fundidos em um único estado.
ALGORITMO DE PREENCHIMENTO DE TABELA 1. Marcar todos os pares (p,q) onde um é de aceitação e o outro não. (Base)
2. Para cada par não marcado (p,q), verificar: para algum símbolo a,
   o par (δ(p,a), δ(q,a)) já está marcado? Se sim, marcar (p,q). (Indução)
3. Repetir o passo 2 até nenhuma nova marcação.
4. Pares NÃO marcados = estados equivalentes → fundir.

Exemplo 4.18 — Minimização Interativa

DFA com 8 estados: A,B,C,D,E,F,G,H. Estado inicial = A. Estados de aceitação = {C}. Após minimização, estados equivalentes são fundidos.
⚡ Clique nos passos do algoritmo
BASE Marcar todos os pares {aceitação, não-aceitação}: (A,C), (B,C), (C,D), (C,E), (C,F), (C,G), (C,H).
ITER 1 Clique para revelar...
ITER 2 Clique para revelar...
RESULTADO Clique para revelar...
Ficha de Estudo — Hopcroft, Motwani & Ullman, Cap.4 — Propriedades das Linguagens Regulares
Lema do Bombeamento · Fechamento · Decisão · Minimização