Capítulo 3 — Expressões Regulares e Linguagens

Expressões Regulares: Definição, Equivalência e Leis Algébricas

Notação algébrica para linguagens regulares e sua equivalência com autômatos finitos

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

1. Os Três Operadores (§3.1.1)

Expressões regulares são construídas a partir de três operações sobre linguagens:

União (L ∪ M) — notação: +

Strings que estão em L ou em M (ou ambos).
Ex: {01, 10} ∪ {10, 11} = {01, 10, 11}

Concatenação (LM) — notação: justaposição

Cada string de L colado com cada string de M.
Ex: {0, 1}{a, b} = {0a, 0b, 1a, 1b}

Fecho/Estrela (L*) — notação: *

Zero ou mais concatenações de strings de L.
L* = {ε} ∪ L ∪ LL ∪ LLL ∪ ...

2. Definição Formal de Expressão Regular (§3.1.2)

BASE:
  • ε é uma regex. L(ε) = {ε}
  • ∅ é uma regex. L(∅) = ∅
  • Para cada símbolo a ∈ Σ, a é uma regex. L(a) = {a}

INDUÇÃO: Se E e F são regex, então:
  1. E + F é regex → L(E+F) = L(E) ∪ L(F)
  2. EF é regex → L(EF) = L(E) · L(F)
  3. E* é regex → L(E*) = (L(E))*
  4. (E) é regex → L((E)) = L(E)

PRECEDÊNCIA DOS OPERADORES (do mais forte ao mais fraco) 1. * (estrela) — se aplica ao menor operando à esquerda
2. concatenação (justaposição) — agrupa da esquerda para a direita
3. + (união) — agrupa da esquerda para a direita

Exemplo: 01*+1 é lido como (0(1*))+1 → L = {0, 01, 011, 0111, ...} ∪ {1}

3. Exemplos Interativos

Exemplo 3.1 — Fecho de Kleene de L = {0, 11}

⚡ Interativo — selecione a potência de L

Exemplo 3.2 — Strings alternados de 0's e 1's

Objetivo: Escrever uma regex para L = {strings de 0's e 1's que alternam}. Ex: ε, 0, 1, 01, 10, 010, 101, 0101, ...

⚡ Interativo — construção passo a passo

Testador de Regex

Selecione uma regex e teste strings contra ela

L = todos os strings da forma 0...01...1 (qualquer número de 0's seguido de qualquer número de 1's)

4. Regex → ε-NFA: Construção de Thompson (§3.2.3)

Toda expressão regular pode ser convertida em um ε-NFA equivalente. A construção é recursiva: para cada operador, combinamos os autômatos menores.

BASE: ε

L(ε) = {ε}

BASE: símbolo a

L(a) = {a}

UNIÃO: E + F

Escolhe E ou F via ε-transições

CONCATENAÇÃO: EF

Saída de E conecta à entrada de F via ε

ESTRELA: E*

Loop verde: repete E. Arco laranja: pula E (aceita ε). Garante 0 ou mais repetições.

4b. DFA → Regex: Exemplos Resolvidos (§3.2.1–3.2.2)

Exemplo 3.5 — Método R_ij^(k) Completo

DFA: 2 estados {1, 2}. Estado inicial = 1. Estado de aceitação = {2}. Transições: δ(1,0) = 2, δ(1,1) = 1, δ(2,0) = 2, δ(2,1) = 2. Aceita: strings com pelo menos um 0.

⚡ Interativo — Clique nos passos do cálculo R_ij^(k)

Exemplo 3.6 — Eliminação de Estados

Método alternativo: Em vez de calcular todas as R_ij^(k), removemos estados um por um, substituindo as transições por expressões regulares nos arcos. Mais visual e prático.

⚡ Interativo — Elimine estados um por um

5. Equivalência: RE ⟺ DFA ⟺ NFA ⟺ ε-NFA (§3.2)

Teorema central: As quatro notações — DFA, NFA, ε-NFA e Expressão Regular — definem exatamente a mesma classe de linguagens: as linguagens regulares. Qualquer linguagem descrita por uma delas pode ser descrita por qualquer outra.

CONVERSÕES DFA → Regex: método R_ij^(k) ou eliminação de estados (§3.2.1/3.2.2)
Regex → ε-NFA: construção de Thompson (§3.2.3) — mostrada acima
NFA → DFA: construção de subconjuntos (§2.3)
ε-NFA → DFA: ECLOSE + subconjuntos (§2.5)

6. Leis Algébricas das Expressões Regulares (§3.4)

LEI	FÓRMULA
Comutatividade de +	R + S = S + R
Associatividade de +	(R + S) + T = R + (S + T)
Associatividade de ·	(RS)T = R(ST)
Distributividade	R(S + T) = RS + RT · (S + T)R = SR + TR
Identidade de +	R + ∅ = R
Identidade de ·	Rε = εR = R
Aniquilação	R∅ = ∅R = ∅
Idempotência de *	(R) = R*
∅* e ε*	∅* = ε · ε* = ε
Absorção de ε	(ε + R)* = R*
Mistura	(RS)* = (R + S)*

Cuidado: A concatenação não é comutativa! RS ≠ SR em geral. Ex: se R = 0 e S = 1, então RS = 01 e SR = 10 — linguagens diferentes.