%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
S4((4<br/>inicial)) -->|ε| S0((0))
S4 -->|ε| S2((2))
S0 -->|a| S1((1))
S2 -->|b| S3((3))
S1 -->|ε| S5(((5)))
S3 -->|ε| S5
1 Autômatos não determinísticos e a construção de Thompson — Resumo
Versão de revisão. Ela recompõe o percurso inteiro depressa e não substitui a primeira leitura. As definições aparecem aqui na forma mais curta que ainda é correta. As três travessias contadas estado a estado, e os quarenta e dois casos da bateria, ficam na versão completa deste capítulo e no capítulo do livro.
Escreva (a|b)*c e pergunte onde a máquina está antes de ler o primeiro caractere. A resposta tem seis números, 6, 4, 7, 8, 0 e 2, e nenhum entrou nessa lista por sorteio. O capítulo anterior entregou uma máquina que ocupa uma posição de cada vez, com uma tabela por trás. Este devolve o direito de ocupar várias ao mesmo tempo — e cobra, em troca, um jeito novo de simular e uma disciplina nova de construir.
1.1 Seis lugares ao mesmo tempo, sem sorteio
O corredor não pede ficha; a catraca não abre sem uma.
Tente montar a máquina de ab|ac colando duas máquinas determinísticas prontas, uma de ab e outra de ac. As duas começam lendo a, e a combinada só pode ter uma saída por a a partir do estado inicial — que ela não tem, porque as duas peças não compartilham nada. Resolver isso abrindo as duas peças e achando o prefixo comum devolve o trabalho que montar por partes deveria poupar. A saída certa é outra: um estado novo, ligado às duas entradas por transições que não leem símbolo nenhum, e a máquina passa a ocupar um conjunto de estados.
Esse regime tem nome, não determinismo, e a definição troca duas peças da quíntupla do autômato determinístico: a transição, que vira função de conjunto para conjunto, e a aceitação, que vira existência de percurso.
NotaDefinição — Autômato finito não determinístico com transições vazias
Um autômato finito não determinístico com transições vazias é uma quíntupla N = (Q, \Sigma, \Delta, q_0, q_f), com Q finito, \Sigma o alfabeto, q_0 \in Q o estado inicial e q_f \in Q o único estado de aceitação. A função \Delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q) associa a cada estado, com um símbolo ou com o símbolo vazio \varepsilon, um subconjunto de Q, possivelmente vazio.
Pense numa estação de metrô. A catraca só gira com ficha; o corredor entre plataformas se atravessa de graça, quantas vezes você quiser. O símbolo da entrada é a ficha, e a transição vazia é o corredor. Na máquina de a|b, o estado 4 é a entrada, e \Delta(4,\varepsilon) = \{0,2\} é o corredor duplo que o põe nas duas plataformas de uma vez, sem gastar ficha.
A imagem popular é a de uma máquina vidente, que escolhe o caminho certo como se conhecesse o fim da cadeia. A definição de aceitação não menciona escolha nenhuma.
NotaDefinição — Aceitação em máquina não determinística
N aceita x \in \Sigma^* quando x = y_1 y_2 \ldots y_m, com cada y_i \in \Sigma \cup \{\varepsilon\}, e existe uma sequência r_0, \ldots, r_m com r_0 = q_0, r_i \in \Delta(r_{i-1}, y_i) e r_m = q_f. Basta que exista uma sequência dessas; as demais podem morrer em qualquer lugar. L(N) é o conjunto das cadeias aceitas.
Para um sim, um percurso vencedor confere em segundos. Para um não, é preciso examinar todos — o que muda de figura a execução, adiante. E o determinístico não desaparece: é o caso particular em que cada \Delta(q,a) tem um só elemento e nenhum corredor existe. As duas classes reconhecem exatamente as mesmas linguagens; a diferença mora na montagem, não no poder.
Se as duas classes reconhecem as mesmas linguagens, em que momento o não determinismo poupa trabalho — e em que momento ele o devolve, com juros?
1.2 Blocos com uma porta de entrada e uma de saída
Dois estados por regra, no máximo, e uma interface pobre demais para guardar curiosidade.
Em 1968, Ken Thompson publicou nas Communications of the ACM um método que monta, para cada nó da árvore de uma expressão, um pedaço de máquina por regra fixa — sem olhar o que o vizinho contém. A ele se deve o nome: construção de Thompson. Ela percorre a metade da equivalência que Kleene já tinha provado em 1951, expressão até máquina, e o que fica pelo caminho é justamente o determinismo.
Toda regra devolve um bloco com exatamente uma entrada e uma saída; por dentro pode haver bifurcação e corredor, mas de fora só as duas pontas contam. Escreva a alternância do jeito mais econômico, com uma entrada só e duas saídas devolvidas cruas, e ela funciona sozinha — até entrar numa concatenação, cuja regra seguinte não sabe o que fazer com duas saídas. A interface de duas pontas custa dois estados a mais por alternância e por fecho; em troca, nenhuma regra pergunta de onde veio o bloco que recebeu.
NotaDefinição — Casos compostos da construção
Sejam B_1=(e_1,s_1) e B_2=(e_2,s_2) blocos já construídos. A concatenação produz (e_1, s_2), com um corredor de s_1 a e_2 — nenhum estado novo. A alternância produz (e,s) com dois estados novos e quatro corredores: de e para e_1 e e_2, de s_1 e s_2 para s. O fecho de B_1 produz (e,s) com dois estados novos e quatro corredores: de e para e_1 (uma vez ou mais) e para s (zero vezes), de s_1 para e_1 (de novo) e para s (basta).
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
E((2<br/>entrada)) -->|"ε: uma vez ou mais"| I0((0))
I0 -->|a| I1((1))
I1 -->|"ε: de novo"| I0
I1 -->|"ε: basta"| S((3<br/>saída))
E -->|"ε: zero vezes"| S
Os casos base são três folhas: o símbolo, que rende dois estados e uma catraca; o coringa, com marca própria para não se confundir com o corredor; a cadeia vazia, que também vira um corredor sozinho. No código, as três dividem um único ramo do switch, e os operadores mexem só nas pontas dos blocos que recebem:
02_regex.h
enum class TipoDeNo {
Simbolo, // um símbolo literal do alfabeto
Qualquer, // o coringa `.`
Vazio, // a cadeia vazia, produzida pela redução de `?`
Concatenacao, // núcleo
Alternancia, // núcleo
Fecho, // núcleo
};
struct No {
TipoDeNo tipo = TipoDeNo::Vazio;
char simbolo = '\0'; // significativo apenas em Simbolo
std::size_t esquerda = kSemFilho;
std::size_t direita = kSemFilho;
};
DicaNo código
Seis construtores, três folhas e três operadores. esquerda e direita bastam para os três compostos; a folha usa só simbolo, e o compilador cobra a lista completa no switch de construir().
04_afn.cpp
case TipoDeNo::Alternancia: {
const Bloco esquerdo = construir(arvore, no.esquerda, afn);
const Bloco direito = construir(arvore, no.direita, afn);
const Estado entrada = afn.novoEstado();
const Estado saida = afn.novoEstado();
afn.adicionarTransicao(entrada, kEpsilon, esquerdo.entrada);
afn.adicionarTransicao(entrada, kEpsilon, direito.entrada);
afn.adicionarTransicao(esquerdo.saida, kEpsilon, saida);
afn.adicionarTransicao(direito.saida, kEpsilon, saida);
return Bloco{entrada, saida};
}
DicaNo código
Quatro chamadas a adicionarTransicao(), nenhuma lendo caractere. Os dois estados novos nascem depois das chamadas recursivas — é essa ordem que faz a|b terminar com as folhas em 0 a 3 e a alternância em 4 e 5.
Duas fusões parecem inocentes e não são. Junte entrada e saída do fecho de a* num único estado, faça o mesmo em b*, funda os dois resultados numa concatenação e simule ba: o percurso aceita, mas a*b* exige todos os a antes dos b. Cada fusão sozinha preservava a linguagem; as duas juntas quebraram a propriedade das pontas — a entrada de um bloco recém-devolvido não pode receber transição de dentro dele mesmo. É por essa propriedade, e não por economia de estados, que o código não funde nem onde fundir daria certo.
1.3 Seis estados antes do primeiro caractere
A árvore de (a|b)*c visita esquerda, direita e só então o nó, numerando cada estado ao nascer. As folhas a e b ficam com 0–1 e 2–3; a alternância cria 4 e 5, com corredores 4→0, 4→2, 1→5, 3→5; o fecho cria 6 e 7, com 6→4, 6→7, 5→4, 5→7; a folha c fecha com 8–9, e o corredor 7→8 da concatenação entrega o bloco (6,9). Dez estados, doze transições, nove delas corredores — os números que a tabela de custos previa antes de rodar qualquer coisa.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
S6((6<br/>inicial)) -->|ε| S4((4))
S6 -->|ε| S7((7))
S4 -->|ε| S0((0))
S4 -->|ε| S2((2))
S0 -->|a| S1((1))
S2 -->|b| S3((3))
S1 -->|ε| S5((5))
S3 -->|ε| S5
S5 -->|ε| S4
S5 -->|ε| S7
S7 -->|ε| S8((8))
S8 -->|c| S9(((9)))
Agora a pergunta da abertura tem resposta. Antes de ler qualquer coisa, a máquina ocupa todo lugar alcançável do inicial por corredor — e essa operação tem nome.
NotaDefinição — Fecho vazio
O fecho vazio de S \subseteq Q, denotado E(S), é o menor conjunto que satisfaz S \subseteq E(S) e, para todo q \in E(S), \Delta(q,\varepsilon) \subseteq E(S). Equivalentemente, E(S) reúne todo estado alcançável a partir de S por zero ou mais transições vazias.
A palavra que sustenta a definição é zero: o fecho contém o próprio S, e quem exige ao menos uma transição perde o ponto de partida. Do 6 saem corredores para 4 e 7; do 7, para 8; do 4, para 0 e 2 — e nenhum desses seis abre corredor novo. Logo E(\{6\}) = \{6,4,7,8,0,2\}, os seis números da abertura, na ordem em que uma busca os encontra.
Calcular isso pede cuidado com um detalhe que o papel esconde e o código não pode esconder: a** é uma repetição de repetição, e o interior de um fecho aplicado a outro fecho tem corredor de ida e de volta entre o mesmo par de estados. Uma busca sem marcação de visitado gira nesse ciclo para sempre.
04_afn.cpp
DicaNo código
Este trecho conta corredores e catracas na mesma lista de saídas, distinguidos só pela marca kEpsilon. A busca de fechoVazio(), no arquivo completo, usa a mesma lista com um vetor de marcação por estado — o que falta aqui é só a pilha que evita repetir estado já visitado.
Em a* sozinho, o defeito nunca aparece: a volta ao começo do interior passa pela catraca de a, e sem corredor de retorno não há ciclo para marcar. Ele exige um interior atravessável inteiramente de graça — a** serve, e (a?)* também, porque o ? também vira fecho por dentro da leitura de padrões. A bateria de casos do projeto guarda uma linha só para a**; sem a marcação, essa linha não falharia — travaria, o veredito mais caro que um teste pode dar.
1.4 Um conjunto por caractere
Rode a|b sobre b sem o fecho vazio: a partida seria \{4\}, o 4 não tem catraca para b, e uma cadeia válida do padrão sairia recusada. Com o fecho, a partida é \{4,0,2\}, o 2 lê o b, e a máquina aceita. O defeito engana porque ab passa sem ele — só falham os padrões cuja raiz é alternância ou fecho.
NotaDefinição — Passo da simulação
\text{mover}(S,a) = \bigcup_{q \in S} \{p \in Q : p \in \Delta(q,a)\}. A simulação sobre x = a_1 \ldots a_n produz S_0 = E(\{q_0\}) e S_i = E(\text{mover}(S_{i-1}, a_i)). A máquina aceita quando q_f \in S_n.
04_afn.cpp
// O conjunto inicial é o fecho vazio do estado inicial, e NÃO o estado
// inicial sozinho. Esquecer este fecho é o defeito mais comum da simulação:
// ele passa em quase todos os testes, porque só falha quando a máquina tem
// transição vazia logo na entrada — o que acontece exatamente nos blocos de
// alternância e de fecho.
std::vector<Estado> ativos = fechoVazio({inicial_});
simulacao.passos.push_back(PassoDaSimulacao{'\0', ativos});
simulacao.maiorConjuntoAtivo = ativos.size();
DicaNo código
O NÃO em maiúsculas, no comentário do arquivo completo, marca o engano mais comum: fechar só depois do laço e esquecer o fecho do passo zero acerta em todo padrão cujo inicial não tem corredor de saída — e falha silenciosamente nos outros.
Sobre abc, a partida \{6,4,7,8,0,2\} lê o a só pelo 0, chega a \{1,5,4,7,8,0,2\} depois de fechar; o b só acha catraca no 2 e refaz o mesmo conjunto trocando o 1 pelo 3; o c só acha catraca no 8 e o conjunto final é \{9\}. Onze transições, oito corredores, três catracas, e a cadeia é aceita.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
P["partida<br/>6, 4, 7, 8, 0, 2"] -->|a| A["1, 5, 4, 7, 8, 0, 2"]
A -->|b| B["3, 5, 4, 7, 8, 0, 2"]
B -->|c| C["9<br/>aceita"]
A -.->|"b, lido a partir do 8"| X["percurso encerrado:<br/>nenhuma catraca para b"]
E quanto custaria seguir cada percurso um por um, em vez de carregar conjuntos? Pegue (a|a)*b, com 10 estados; cada a tem duas alternativas, e trinta letras a dão 2^{30}, mais de um bilhão, de percursos. A um microssegundo cada, quase dezoito minutos por uma linha de trinta caracteres. A simulação por conjuntos recusa a mesma cadeia olhando no máximo 10 estados por caractere, porque nunca enumera percurso — só onde ele poderia estar.
Rode ababab na máquina de (a|b)*c e repare no que se repete: o conjunto de depois de um a e o de depois de um b se alternam seis vezes, recalculados do zero a cada passagem, como se a simulação nunca os tivesse visto antes. Guardar cada conjunto numa tabela, com um número e um destino por símbolo, é outra máquina — determinística, cujos estados são conjuntos desta. É o procedimento do próximo capítulo, e a memória separa os dois: a simulação usa cada conjunto uma vez e o descarta; a tabela paga o cálculo antes, para consultar depois.
1.5 Duas garantias que não se substituem
Uma prova diz que a regra está certa; uma bateria de casos diz se o código a copiou direito.
O tamanho da máquina se prevê sem construir nada: cada folha soma dois estados, cada alternância e cada fecho somam no máximo dois, e a concatenação não soma nenhum.
ImportanteTeorema — Toda expressão regular tem máquina equivalente de tamanho linear
Para toda expressão regular r sobre \Sigma, a aplicação recursiva das regras sobre a árvore de r produz N tal que L(N) = L(r), com O(|r|) estados: cada caso base introduz duas unidades, cada composição no máximo duas, e a concatenação nenhuma.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
D["regras dos casos<br/>base e compostos"] -->|"indução sobre a árvore"| T["a regra está certa"]
D -->|transcrição| C["construir()"]
C -->|"switch sobre enumeração"| K["nenhum construtor esquecido"]
C -->|"42 vereditos escritos à mão"| B["a transcrição está certa"]
A igualdade sai por indução sobre a árvore, com uma hipótese de duas partes: as cadeias de entrada a saída de cada bloco filho formam exatamente a linguagem daquela subexpressão, e a entrada de cada bloco não recebe transição enquanto a saída não emite nenhuma — a propriedade das pontas que as fusões da seção anterior destruíram. Na concatenação, o único contato é o corredor entre os dois blocos, e todo percurso se parte num trecho de cada linguagem. Na alternância, o percurso entra por um lado e só sai por ele. No fecho, ou usa o corredor de zero vezes, ou atravessa o interior k \ge 1 vezes — e a soma sobre todo k, inclusive zero, é o fecho da linguagem interna.
A prova garante a regra; não garante que o switch de seis rótulos a transcreveu sem erro. Para isso serve uma bateria de quarenta e duas linhas, padrão, cadeia e veredito decididos sem rodar o programa — ab com ab aceita, a.c com ac recusa, porque o ponto lê exatamente um caractere. Um caso copiado da própria saída do programa bate sempre, inclusive quando o programa errou; é conferir a conta do restaurante com a calculadora do garçom que a fez. O teste que protege compara o código com uma expectativa que não depende dele.
Uma pergunta antes de seguir
Se a construção esquecesse o corredor de zero vezes no fecho, a prova continuaria de pé — a indução não checa transcrição. Qual caso da sua bateria denunciaria o esquecimento, e por que ele precisa vir de um raciocínio sobre a linguagem, nunca sobre a máquina?
Volte à pergunta de abertura com a máquina inteira na mão. O 6 é a entrada do bloco raiz; o 4 veio do corredor que entra no interior do fecho, o 7 do que o pula; o 8 chegou pelo corredor que a concatenação abriu entre o fecho e o c; o 0 e o 2 são as entradas das duas folhas, alcançadas pela bifurcação da alternância. Pois é: seis estados, seis razões nomeáveis, nenhuma delas palpite — e é essa a máquina que o módulo nfa do seu próprio compilador precisa produzir, a partir da árvore que o regex_parser já entrega, antes de a determinização, no capítulo seguinte, dar um número único a cada conjunto de plataformas que hoje ainda se ocupa em bando.