Regex e autômatos

Regex = linguagem para descrever linguagens

Uma expressão regular descreve um conjunto de strings — a linguagem que ela reconhece. Por exemplo, (a|b)*abb descreve todas as strings sobre {a, b} que terminam com "abb": "abb", "aabb", "babb", "aaabb", ...

O teorema de Kleene (1956) prova que as linguagens descritas por expressões regulares são exatamente as linguagens reconhecidas por DFAs — as linguagens regulares. Quando você escreve re.compile(r"\\d+"), o motor compila isso para um DFA (via NFA intermediário) e o executa contra a entrada.

DFA para o padrão (a|b)*abb

Digite uma string com letras 'a' e 'b' e avance passo a passo. O DFA tem 4 estados; q3 (duplo círculo) é o único aceitador — a string deve terminar aqui.

Regex em Python

# Expressões regulares em Python — sintaxe e operações
import re

# Metacaracteres fundamentais:
# .    qualquer caractere (exceto \n por padrão)
# *    zero ou mais do anterior
# +    um ou mais do anterior
# ?    zero ou um do anterior
# |    alternância (ou)
# ()   grupo
# []   classe de caracteres
# ^$   início e fim da string

# Exemplos:
re.match(r"(a|b)*abb", "aabb")       # match — termina em "abb"
re.match(r"\d+",          "42px")       # match "42"
re.fullmatch(r"[A-Za-z_]\w*", "nome_1") # identificador
re.findall(r"\b\w+\b", "olá mundo")  # ['olá', 'mundo']

# Grupos de captura:
m = re.match(r"(\d{4})-(\d{2})-(\d{2})", "2026-06-14")
m.group(1)  # '2026'
m.group(2)  # '06'
m.group(3)  # '14'

Construção de Thompson: de regex para NFA

# Compilação de regex para NFA (construção de Thompson)
# Cada operação de regex produz um fragmento de NFA

# Símbolo 'a':
#   →[q_ini] --a--> [q_fim]

# Concatenação: r · s  (r seguido de s)
#   NFA(r).fim → ε → NFA(s).ini

# Alternância: r | s
#   novo_ini → ε → NFA(r).ini
#   novo_ini → ε → NFA(s).ini
#   NFA(r).fim → ε → novo_fim
#   NFA(s).fim → ε → novo_fim

# Fechamento de Kleene: r*
#   novo_ini → ε → NFA(r).ini
#   novo_ini → ε → novo_fim     (aceita string vazia)
#   NFA(r).fim → ε → NFA(r).ini (repetição)
#   NFA(r).fim → ε → novo_fim

# Após construir NFA → algoritmo de subconjuntos → DFA
# re.compile() faz exatamente isso (em C, muito rápido)

Construindo um motor de regex

Mini projeto: implemente um motor de regex simplificado que suporte apenas ., * e caracteres literais (sem grupos ou alternância). Use a abordagem de simulação direta de NFA: para cada caractere da entrada, compute o conjunto de estados alcançáveis por transições ε. Teste com padrões como "a*b", ".*c".

Projeto principal: estenda o motor para suportar |, () e +. Compile a regex para NFA usando a construção de Thompson (representação explícita como grafo). Execute o NFA com simulação de subconjunto. Verifique que o resultado é idêntico ao módulo re para 1000 strings aleatórias.

Desafio extra: implemente um detector de ReDoS: dado um padrão regex, analise se ele pode exibir backtracking exponencial (ambiguidade exponencial). Use a técnica de análise de "caminhos de estrela aninhadas" — se encontrar, reporte qual subcadeia pode causar o pior caso e sugira uma reescrita.

Teste sua intuição

Onde você encontra isso