%%{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
Seis estados ocupados antes do primeiro caractere, e cada um com endereço conhecido.
Deixe papel e lápis por perto. A máquina de (a|b)*c é montada nestas páginas à mão, estado por estado, e depois executada sobre quatro cadeias. Os números que você anotar são os mesmos que o programa imprime.
Escreva (a|b)*c e deixe a construção de Thompson transformar o padrão em máquina. Saem dez estados, numerados de 0 a 9. Agora pergunte onde essa máquina está antes de ler o primeiro caractere de abc. A resposta tem seis números: 6, 4, 7, 8, 0 e 2. Os seis valem juntos, e nenhum está ali como candidato à espera de sorteio.
Quem vem do autômato determinístico estranha a conta. Aquela máquina ocupava um estado por vez. Seis estados simultâneos parecem hesitação, como se a máquina apostasse em vários caminhos e torcesse por um. Mas cada um dos seis tem uma razão enunciável para estar ali, e a lista sai de uma conta sem sorteio e sem volta atrás.
Essa aparente bagunça compra a montagem sem entendimento. Até aqui, todo autômato nasceu de alguém lendo uma frase em português e decidindo o que cada estado lembra. Agora uma função recursiva percorre a árvore da expressão, aplica a cada nó uma regra fixa e entrega a máquina, sem passo criativo no meio. O trabalho migra para a execução, que carrega um conjunto de estados por caractere em vez de um número.
1.1 Estar em vários estados sem adivinhar nenhum
Tente montar a máquina de ab|ac juntando a de ab com a de ac, as duas prontas e determinísticas. Ambas começam lendo a, e a máquina combinada só pode ter uma saída por a a partir do estado inicial. Para decidir qual, ela precisaria abrir as duas peças e achar o prefixo que elas dividem. Montar por partes pede o oposto: usar cada peça como caixa lacrada.
A saída é um estado inicial novo, ligado às entradas das duas peças por transições que não leem nada. A máquina passa a ocupar um conjunto de estados e aceita se algum percurso terminar bem. Esse regime se chama não determinismo. O nome diz só isto: o estado atual e o símbolo lido deixam de fixar o próximo estado. A definição formal troca duas peças da quíntupla determinística, a transição e a aceitação.
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). Nela, Q é um conjunto finito de estados, \Sigma é um alfabeto finito, q_0 \in Q é o estado inicial e q_f \in Q é o único estado de aceitação. A função de transição \Delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q) associa a cada estado, combinado com um símbolo de \Sigma ou com o símbolo vazio \varepsilon, um subconjunto de Q, possivelmente vazio.
A máquina de a|b tem seis estados, de 0 a 5. O 4 é o inicial, e \Delta(4, \varepsilon) = \{0, 2\} o põe nas duas entradas de uma vez. Do 0, o a leva a \{1\}. Do 2, o b leva a \{3\}. O 1 e o 3 seguem sem ler para o 5, que aceita. Todos os outros pares devolvem \emptyset. O determinístico precisava de um estado de erro para a entrada inválida, e aqui o percurso sem destino simplesmente acaba, enquanto os outros continuam.
| Peça | Autômato determinístico | Autômato não determinístico |
|---|---|---|
| Transição | \delta(q, a) é um estado | \Delta(q, a) é um conjunto, talvez vazio |
| Símbolo vazio | não existe | \Delta(q, \varepsilon) muda de estado sem ler |
| Aceitação | conjunto F de estados | um único estado q_f |
| Entrada sem saída prevista | estado de erro | conjunto vazio, sem estado extra |
Para uma teoria geral de máquinas, exigir um só estado de aceitação seria capricho. Para quem vai montar máquinas por partes, porém, ele poupa trabalho. Cada peça ganha uma porta de entrada e uma de saída, e a porta de saída da peça mais externa acaba servindo de aceitação para o conjunto.
1.1.1 A ficha e o corredor
Pense numa estação de metrô. A catraca só gira com ficha, e o corredor entre duas plataformas se atravessa de graça, quantas vezes você quiser. O símbolo da entrada é a ficha, e a transição vazia é o corredor (em termos literais, ela muda de estado sem consumir símbolo). Na máquina de ab, quem entra com a cadeia ab gasta duas fichas e faz três travessias. Uma catraca leva o 0 ao 1 lendo a, um corredor liga o 1 ao 2, e outra catraca leva o 2 ao 3 lendo b.
NotaDefinição — Transição vazia
Uma transição vazia é um elemento de \Delta(q, \varepsilon): a máquina passa do estado q a um estado desse conjunto sem ler símbolo algum da entrada, e a posição na cadeia não muda. A transição está disponível sempre que a máquina esteja em q, qualquer que seja o próximo símbolo.
Duas certezas do determinístico caem aqui. A primeira é o número de passos, que lá era o comprimento da cadeia. Aqui, ab tem dois símbolos e o percurso que a aceita tem três transições. A segunda é mais sutil. O corredor não espera convite, então estar no estado 1 de ab já é estar também no 2. Aqui a estação vence o prazo de validade. Um passageiro ocupa uma plataforma de cada vez, e a máquina ocupa todas as que algum passageiro alcançaria.
Na memória, o corredor precisa de uma marca que nenhum padrão produza por acidente; se fosse uma letra, ela viraria passagem gratuita. O projeto de referência usa o byte zero, a constante kEpsilon, porque o zero encerra cadeias de caracteres e ninguém o escreve num padrão.
1.1.2 Um percurso basta para dizer sim
A imagem popular é a da máquina vidente, que diante de duas saídas escolhe a certa como se já conhecesse o fim da cadeia. Não é bem assim, e a definição de aceitação nem menciona escolha.
NotaDefinição — Aceitação em máquina não determinística
A máquina N aceita a cadeia x \in \Sigma^* quando x pode ser escrita como y_1 y_2 \ldots y_m, com cada y_i \in \Sigma \cup \{\varepsilon\}, e existe uma sequência de estados r_0, r_1, \ldots, r_m com r_0 = q_0, r_i \in \Delta(r_{i-1}, y_i) para todo i, e r_m = q_f. Basta que exista uma dessas sequências; as demais, se houver, não precisam terminar em q_f. A linguagem reconhecida é L(N) = \{\, x \in \Sigma^* : N \text{ aceita } x \,\}.
A decomposição y_1 \ldots y_m sai mais comprida que x porque carrega os \varepsilon, e é por ela que os corredores entram na conta. Para ab na máquina de ab, ela é a, \varepsilon, b, com os estados 0, 1, 2 e 3; apagados os \varepsilon, sobra ab.
Uma definição existencial separa aceitar de recusar. Para um sim, basta exibir um percurso, que qualquer pessoa confere em segundos. Para um não, o percurso que falhou prova pouco, porque recusar é afirmar algo sobre todos eles. Com a|b e a cadeia ab são dois percursos. Um lê o a, chega ao 5 e não acha catraca para o b. O outro vai ao 2 e morre antes de ler qualquer coisa. Em máquinas maiores, o número de percursos pode dobrar a cada símbolo, e por isso a execução carregará conjuntos em vez de caminhos.
E o determinístico, onde fica? É caso particular: troque cada \delta(q, a) = p por \Delta(q, a) = \{p\}, sem corredor algum, e cada cadeia passa a ter um só percurso. Vários estados de aceitação ganham, cada um, um corredor para um q_f novo. Daí não se segue que o não determinismo reconheça mais linguagens. As duas classes reconhecem exatamente as mesmas, como a determinização vai provar convertendo uma máquina na outra. O ganho está na montagem: a|b saiu de duas peças prontas e dois corredores.
Se as duas classes de máquina reconhecem as mesmas linguagens, em que momento a não determinística poupa trabalho, e em que momento ela o devolve?
1.1.3 A árvore da Peneira ganha um consumidor
A Peneira, a linguagem de reconhecimento de padrões que acompanha estas páginas, tem até aqui duas peças que não se falam. Uma é o leitor da mini-notação de padrões. Ele recebe o texto de um pattern e devolve a árvore correspondente, com seis tipos de nó. A outra é o executor de autômatos determinísticos, que decide sobre uma cadeia com uma consulta de tabela por símbolo. As máquinas que esse executor rodou foram digitadas estado a estado. Nenhuma nasceu de um padrão.
O módulo que entra agora se chama nfa. A responsabilidade dele na arquitetura da Peneira é uma só: da árvore do padrão à máquina não determinística com transições vazias, pela construção de Thompson. Pela primeira vez, um pattern escrito por alguém atravessa o sistema sem intervenção manual, do texto até uma máquina que aceita ou recusa cadeias. Essa máquina ainda não é a que o executor determinístico sabe rodar. Por isso o módulo traz a sua própria simulação por conjunto de estados.
A peça tem uma segunda função, e ela pesa mais do que a construção em si. O arquivo de casos conferidos à mão que acompanha o módulo vira a referência contra a qual as peças seguintes serão comparadas. Quando a máquina for determinizada e reduzida, é contra esses vereditos, escritos sem rodar o programa, que se saberá se a redução preservou a linguagem.
1.2 Peças com uma porta de entrada e uma de saída
Dois estados por regra, no máximo, e um tipo de dado que não deixa espaço para curiosidade.
Em junho de 1968, Ken Thompson publicou nas Communications of the ACM o artigo Regular Expression Search Algorithm. O programa descrito ali lia uma expressão regular e escrevia código do IBM 7094 para procurá-la no texto. O método leva hoje o nome dele: a construção de Thompson. Ela monta, para cada nó da árvore, um pedaço de máquina por regra fixa, sem olhar o que os vizinhos contêm. Kleene já tinha mostrado, em 1951, que expressão e máquina de estados finitos descrevem os mesmos conjuntos. A construção percorre a metade que vai da expressão à máquina, e o que fica pelo caminho é o determinismo.
1.2.1 O que um bloco deixa ver
Toda regra devolve um pedaço com exatamente um estado de entrada e um de saída. Por dentro pode haver bifurcação, volta e corredor; de fora, só as duas pontas contam.
NotaDefinição — Bloco
Um bloco é um par de estados (e, s) de uma máquina em construção, chamados entrada e saída, tal que o conjunto de cadeias que levam de e a s é exatamente a linguagem denotada pela subexpressão que o bloco representa. Nenhum outro estado do bloco é estado de aceitação, e, uma vez formado, o bloco só se relaciona com o restante da construção pelos seus dois estados distinguidos.
No código, a definição virou a estrutura Bloco, com os campos entrada e saida. Mais nada: nem segunda saída, nem lista de estados internos, nem tipo de nó de origem. Uma regra que quisesse saber se o bloco recebido veio de um fecho não teria onde guardar a resposta.
Quer ver o que essa pobreza evita? Escreva a alternância do jeito mais econômico, com um estado de entrada ligado às duas peças e as duas saídas devolvidas como estão. Para a|b sozinho, funciona. Mas dentro de uma concatenação a regra seguinte recebe um bloco de duas saídas. Precisa ligar cada uma ao que vem depois, e um bloco vindo de fecho teria outra forma. Cada regra passaria a perguntar de onde veio o que recebeu, e as combinações cresceriam com o número de operadores. A alternância de verdade gasta dois estados e quatro corredores, onde um estado e dois dariam conta. Eu aceito esses dois estados em qualquer implementação que outra pessoa vá manter.
1.2.2 Três folhas e três operadores
As folhas da árvore são três, e no código dividem um único ramo do switch:
04_afn.cpp
case TipoDeNo::Simbolo:
case TipoDeNo::Qualquer:
case TipoDeNo::Vazio: {
// Os três casos base têm a mesma forma — dois estados e uma
// transição —, e diferem apenas no rótulo dela.
const Estado entrada = afn.novoEstado();
const Estado saida = afn.novoEstado();
const char rotulo = no.tipo == TipoDeNo::Simbolo ? no.simbolo
: no.tipo == TipoDeNo::Qualquer ? kQualquer
: kEpsilon;
afn.adicionarTransicao(entrada, rotulo, saida);
return Bloco{entrada, saida};
}
DicaNo código
Só o rótulo varia entre as três folhas: o próprio caractere, kQualquer para o coringa ., kEpsilon para a cadeia vazia. Essa última surge quando a leitura de padrões reescreve x? como (x|ε).
NotaDefinição — Casos base da construção
Para o símbolo a \in \Sigma, o bloco é formado por dois estados novos e e s com \Delta(e, a) = \{s\}. Para o coringa, que casa qualquer símbolo de \Sigma, o bloco é formado por dois estados novos com uma transição de e para s rotulada por uma marca distinta de \varepsilon e de todo símbolo de \Sigma, interpretada na simulação como “casa qualquer a \in \Sigma”. Para a cadeia vazia \varepsilon, o bloco é formado por dois estados novos com \Delta(e, \varepsilon) = \{s\}.
A folha a rende a menor máquina da construção: dois estados e uma catraca. A folha \varepsilon rende outra do mesmo tamanho, que só aceita a cadeia vazia. E por que o coringa não usa a marca do corredor? Porque ele consome um caractere; com as marcas iguais, a.c aceitaria ac. Por isso kQualquer vale '\x01', vizinho do '\0' de kEpsilon.
Falta a folha \emptyset, que a definição indutiva das expressões regulares tinha e que não denota cadeia nenhuma. A notação de padrões não a escreve, e a árvore não tem nó para ela: são seis construtores, três folhas e três operadores. Para completar a teoria, \emptyset vira dois estados novos sem transição entre eles. A definição de máquina aceita isso, já que o conjunto vazio é imagem legítima de \Delta.
Os operadores recebem blocos prontos e só mexem nas pontas deles.
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 o bloco (e_1, s_2), acrescentando a transição vazia de s_1 para e_2 — nenhum estado novo é criado. A alternância produz o bloco (e, s) com dois estados novos e quatro transições vazias: de e para e_1, de e para e_2, de s_1 para s e de s_2 para s. O fecho de B_1 produz o bloco (e, s) com dois estados novos e quatro transições vazias: de e para e_1 (uma vez ou mais), de e para s (zero vezes), de s_1 para e_1 (de novo) e de s_1 para s (basta).
A concatenação é a regra mais barata, um corredor da saída da esquerda para a entrada da direita:
04_afn.cpp
case TipoDeNo::Concatenacao: {
// A saída do primeiro passa a alimentar a entrada do segundo. Uma
// transição vazia liga os dois em vez de fundir os estados: fundir
// funcionaria aqui e quebraria a uniformidade da interface.
const Bloco esquerdo = construir(arvore, no.esquerda, afn);
const Bloco direito = construir(arvore, no.direita, afn);
afn.adicionarTransicao(esquerdo.saida, kEpsilon, direito.entrada);
return Bloco{esquerdo.entrada, direito.saida};
}
DicaNo código
As chamadas recursivas vêm antes do corredor, a da esquerda primeiro. Essa ordem numera as folhas de ab como 0, 1, 2 e 3, e o total é de 4 estados e 3 transições, 1 delas vazia. O comentário admite que fundir saída e entrada funcionaria aqui, e dá a uniformidade da interface como razão para não fundir.
Na alternância, dois estados novos abrem e fecham o desvio:
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 estados novos nascem depois das chamadas recursivas. Em a|b, então, as folhas ficam com 0 a 3 e a alternância recebe o 4 e o 5, num total de 6 estados e 6 transições, 4 delas vazias.
O fecho também cria dois estados e quatro corredores:
04_afn.cpp
case TipoDeNo::Fecho: {
const Bloco interno = construir(arvore, no.esquerda, afn);
const Estado entrada = afn.novoEstado();
const Estado saida = afn.novoEstado();
afn.adicionarTransicao(entrada, kEpsilon, interno.entrada); // uma vez ou mais
afn.adicionarTransicao(entrada, kEpsilon, saida); // zero vezes
afn.adicionarTransicao(interno.saida, kEpsilon, interno.entrada); // de novo
afn.adicionarTransicao(interno.saida, kEpsilon, saida); // basta
return Bloco{entrada, saida};
}
DicaNo código
Os comentários à direita, lidos em sequência, repetem a definição: entrar, pular, voltar, sair. Em a*, a folha ocupa o 0 e o 1, e o fecho acrescenta o 2 e o 3. São 4 estados e 5 transições, 4 delas vazias. Sem o corredor de zero vezes, a cadeia vazia deixa de ser aceita; sem o de novo, o padrão para depois de uma repetição.
%%{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
| Nó da árvore | Estados novos | Transições novas | Das quais vazias |
|---|---|---|---|
| folha (símbolo, coringa ou \varepsilon) | 2 | 1 | 0, ou 1 se a folha é \varepsilon |
| concatenação | 0 | 1 | 1 |
| alternância | 2 | 4 | 4 |
| fecho | 2 | 4 | 4 |
1.2.3 Duas fusões inocentes
Dois estados ligados só por um corredor parecem o mesmo estado com dois nomes, e às vezes são. Funda-os em a*b* nos dois lugares em que a tentação aparece. No fecho de a*, entrada e saída viram um estado x. A linguagem de a* isolado não muda, e o mesmo vale para b*, com y. Na concatenação, a segunda fusão junta x e y num m que é entrada, saída e passagem das duas voltas.
Simule ba. De m se vai à volta do b, lê-se o b e volta-se a m. Daí se vai à volta do a, lê-se o a e volta-se a m, que aceita. Só que a*b* exige todos os a antes dos b, e ba está fora. Cada fusão sozinha preservava a linguagem, e as duas juntas a quebraram.
O que se perdeu foi a propriedade das pontas. Na construção fiel, a entrada de um bloco recém-devolvido não recebeu transição nenhuma, e a saída não emitiu nenhuma (as ligações chegam depois, de fora). A primeira fusão fez a entrada receber a volta do interior. A emenda com outro bloco igual deixou, então, o percurso voltar de um fecho ao anterior. O código não funde nem onde fundir daria certo, e a*b* mostra o que essa teimosia protege.
1.3 Seis estados antes do primeiro caractere
A árvore de (a|b)*c tem seis nós. Na raiz fica uma concatenação, à esquerda um fecho guardando a alternância entre a e b, e à direita a folha c. A construção visita o filho esquerdo, o direito e só então o nó, e cada estado recebe o próximo número livre ao nascer. A folha a fica com 0 e 1, a b com 2 e 3. A alternância cria 4 e 5, com os corredores 4→0, 4→2, 1→5 e 3→5.
O fecho cria 6 e 7 e acrescenta 6→4, 6→7, 5→4 e 5→7. Só então a construção desce à folha c, que ganha 8 e 9, e o corredor 7→8 da raiz fecha o bloco (6, 9). A tabela de custos previa o total antes de rodar. Três folhas somam 6 estados e 3 catracas. Alternância e fecho somam 2 estados e 4 corredores cada, e a concatenação, 1 corredor. São 10 estados e 12 transições, 9 delas vazias, os números que a demonstração do código imprime. Visitar a direita primeiro daria a mesma máquina com outros nomes (o c com 0 e 1, o inicial no 8). Só que aí o traço impresso deixaria de bater linha a linha com o papel.
| Estado | Pelo símbolo | Pela transição vazia |
|---|---|---|
| 0 | a leva a 1 |
— |
| 1 | — | 5 |
| 2 | b leva a 3 |
— |
| 3 | — | 5 |
| 4 | — | 0 e 2 |
| 5 | — | 4 e 7 |
| 6 (inicial) | — | 4 e 7 |
| 7 | — | 8 |
| 8 | c leva a 9 |
— |
| 9 (aceitação) | — | — |
%%{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)))
O desenho também diz que linguagem esperar. Todo caminho do 6 ao 9 termina na catraca de c, alcançada pelo corredor 7→8. Até o 7, o percurso pode girar entre 4 e 5 lendo a ou b em qualquer ordem. São as cadeias de a e b seguidas de um único c. Esse gabarito dá vereditos sem simular. Entram abc e c; ficam fora abb (não termina em c), ca (tem a depois do c) e a cadeia vazia (não tem c).
1.3.1 Tudo o que se alcança de graça
O padrão a** é redundante e perfeitamente legal, e vira um fecho aplicado a outro fecho. A máquina tem dois corredores entre o mesmo par de estados, um de ida e outro de volta. Liste os alcançáveis por corredor sem anotar por onde passou e você gira nesse ciclo para sempre. Para não girar, a função fechoVazio() faz uma busca em profundidade que marca cada estado visitado:
04_afn.cpp
std::vector<Estado> Afn::fechoVazio(const std::vector<Estado>& conjunto) const {
// Busca em profundidade sobre as transições vazias, com marcação de visitado
// num vetor denso (um byte por estado, por chamada). A marcação garante o
// término quando há ciclo de transições vazias, o que acontece quando o
// interior de um fecho pode ser atravessado sem ler símbolo — `a**` e
// `(a?)*`, por exemplo. Em `a*` o retorno passa pela transição que lê `a`,
// não há ciclo de transições vazias, e o defeito não aparece.
std::vector<char> visitado(transicoes_.size(), 0);
std::vector<Estado> pilha;
std::vector<Estado> resultado;
for (const Estado estado : conjunto) {
if (!visitado[estado]) {
visitado[estado] = 1;
pilha.push_back(estado);
resultado.push_back(estado);
}
}
while (!pilha.empty()) {
const Estado atual = pilha.back();
pilha.pop_back();
for (const TransicaoAfn& transicao : transicoes_[atual]) {
if (transicao.simbolo != kEpsilon) {
continue;
}
if (!visitado[transicao.destino]) {
visitado[transicao.destino] = 1;
pilha.push_back(transicao.destino);
resultado.push_back(transicao.destino);
}
}
}
return resultado;
}
DicaNo código
O vetor visitado reserva um byte por estado. Um estado só entra na pilha se ainda não estava marcado, e, como os estados são finitos, a pilha esvazia. O comentário explica por que a* sozinho nunca expõe o defeito: a volta ao começo do interior passa pela catraca de a. O ciclo exige um interior atravessável de graça, como o de a** ou o de (a?)*.
A bateria de casos do projeto tem uma linha para a**, e uma versão sem marca não reprovaria nela. O teste rodaria até alguém desligar o computador, o veredito mais demorado e menos informativo que um teste consegue dar.
NotaDefinição — Fecho vazio
O fecho vazio de um conjunto 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) é o conjunto de todos os estados alcançáveis a partir de algum estado de S por zero ou mais transições vazias.
A palavra que segura a definição é zero: o fecho contém o próprio S. Na máquina de ab, E(\{0\}) = \{0\}, porque do 0 só sai catraca, e E(\{1\}) = \{1, 2\}. Quem define o fecho por pelo menos uma transição vazia perde o ponto de partida, e a simulação desanda daí. E por que o menor conjunto? Porque Q inteiro também contém S e é fechado pelos corredores, e o fecho fica só com quem se alcança a partir de S.
Agora a conta da abertura sai sozinha. Do 6 saem corredores para 4 e 7, do 7 para o 8, do 4 para 0 e 2. Nenhum desses seis oferece outro corredor. Logo E(\{6\}) = \{6, 4, 7, 8, 0, 2\}, na ordem em que a busca os encontra. O 8 entrou pelo corredor de zero vezes, que pula o fecho inteiro e deixa a máquina pronta para um c já no primeiro caractere.
1.4 Um conjunto por caractere
Tire de simular() uma única chamada, o fecho vazio do estado inicial, e rode a|b sobre a cadeia b. A partida vira \{4\}, o 4 não tem catraca para b, e uma cadeia do padrão acaba recusada. Com o fecho, a partida é \{4, 0, 2\}, o 2 lê o b, e o corredor 3→5 chega à aceitação. O defeito engana porque ab passa sem ele: o inicial de ab não tem corredor. Só falham os padrões cuja raiz é alternância ou fecho, e os que começam por uma delas.
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, aponta o engano mais comum. O fecho entra em dois lugares: uma vez antes do laço, em S_0 = E(\{q_0\}), registrado como passo zero, e uma vez por símbolo, em S_i = E(\text{mover}(S_{i-1}, a_i)). Quem escreve só o segundo começa no estado inicial cru e segue acertando em todo padrão cujo inicial não emite corredor.
NotaDefinição — Passo da simulação
Dada uma máquina N, define-se \text{mover}(S, a) = \bigcup_{q \in S} \{\, p \in Q : p \in \Delta(q, a) \,\}, que reúne os destinos de todos os estados de S pelo símbolo a \in \Sigma. A simulação de N sobre x = a_1 \ldots a_n produz a sequência de conjuntos S_0 = E(\{q_0\}) e S_i = E(\text{mover}(S_{i-1}, a_i)) para 1 \le i \le n. A máquina aceita a cadeia quando q_f \in S_n.
Leia S_i como a lista de todos os lugares onde algum percurso poderia estar depois de i símbolos. Um percurso vencedor deixa o seu ponto final dentro de S_n, e a ausência de vencedores deixa q_f de fora. Recusar, que exigia examinar todos os caminhos, vira uma consulta ao último conjunto, e a conta passa a ser o tamanho dele.
1.4.1 Três caracteres e onze transições
Sobre abc, a partida é \{6, 4, 7, 8, 0, 2\}, e o a só encontra catraca no 0, que leva ao 1. Do 1, os corredores vão ao 5, do 5 ao 4 e ao 7, do 7 ao 8, do 4 ao 0 e ao 2. Ficam sete estados: \{1, 5, 4, 7, 8, 0, 2\}. Essa ordem sai da pilha de fechoVazio(), que o traço impresso não mostra. O 5 empilha o 4 e depois o 7, e o 7 sai primeiro, por ter entrado por último, trazendo o 8. Só então o 4 traz o 0 e o 2, e por isso o 8 sai na frente do 0 na saída da demonstração.
O b só acha catraca no 2, que leva ao 3, e os corredores refazem o caminho até \{3, 5, 4, 7, 8, 0, 2\}. Repare no que morreu. O 8 estava pronto para um c e recebeu um b, e, como \Delta(8, b) é vazio, esse percurso acabou ali, sem estado de erro. Dos sete ativos, só o 2 cruzou catraca. O c só acha catraca no 8, e o conjunto final é \{9\}. A cadeia abc é aceita por um percurso de 11 transições, 8 corredores e 3 catracas.
%%{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"]
Com abb, o último conjunto não tem o 9. A recusa vem com prova completa, porque o conjunto reúne o ponto de chegada de todos os percursos que leem abb. A cadeia c é aceita num passo, sem regra especial para zero repetições, pois o 8 já estava na partida. Já ca chega a \{9\}, lê o a e fica com o conjunto vazio. Refazer esses traços à mão e comparar com a saída da demonstração é a conferência mais barata que a construção admite. A cadeia abbac sai pelo mesmo método, com sete estados depois de cada a ou b.
E quanto custaria seguir os caminhos um por um? Pegue (a|a)*b, padrão bobo e legal, com 10 estados. Cada a pode ser lido por qualquer das duas alternativas, e n letras a dão 2^n percursos. Com trinta a e nenhum b, quem tentasse cada percurso e voltasse atrás esgotaria 1.073.741.824 deles antes de dizer não. A um microssegundo por percurso, seriam quase dezoito minutos por uma linha de trinta letras. A simulação recusa a mesma cadeia olhando no máximo 10 estados por caractere.
1.4.2 O conjunto na memória
A definição diz conjunto, e simular() usa dois vetores. Um lista os estados ativos na ordem de entrada e é o que se percorre. O outro, presente, tem uma posição por estado. Ele responde em tempo constante se um estado já entrou no passo corrente, pergunta feita a cada transição examinada. Sem ele, dois ativos com o mesmo destino pelo mesmo símbolo o inseririam duas vezes, e as duplicatas se multiplicariam.
O presente nasce uma vez por simulação. Ao fim de cada passo, o código zera só as posições que entraram: numa máquina de mil estados com três ativos, três escritas. Na leitura do a sobre (a|b)*c, só presente[1] é marcado, volta a zero no fim do laço, e \{1\} segue para o fecho. Um conjunto ordenado da biblioteca padrão responderia em tempo logarítmico, mas alocaria um nó por inserção, e num milhão de caracteres seriam milhões de alocações.
Zero alocação por caractere, o código ainda não entrega, e a pendência está declarada. Cada chamada de fechoVazio() monta um vetor de marcas novo, e há uma chamada por caractere. Na máquina de mil estados, isso significa alocar e zerar mil bytes a cada passo, e o vetor dos próximos estados também é recriado. Enquanto o vetor do fecho não for reaproveitado, o custo por passo não fica proporcional ao conjunto. Em troca, a função de fecho se lê sozinha e não divide estado com quem a chama.
A leitura para quando o conjunto esvazia, porque nada reativa estado depois disso. O veredito não muda, e de quebra a leitura encurta. Uma linha de um milhão de caracteres que comece por ca é recusada depois de dois, e os outros 999.998 nem são lidos. O traço guarda ainda o maior conjunto observado, a medida do trabalho por símbolo, que vale 7 para (a|b)*c sobre abc.
1.4.3 Guardar os conjuntos já seria outra máquina
Rode ababab em (a|b)*c. Os conjuntos de depois do a e de depois do b se alternam seis vezes. A simulação recalcula cada um como se nunca o tivesse visto. Um programa que guardasse cada conjunto novo numa tabela, com número e destino por símbolo, consultaria a linha na segunda ocorrência. Esse programa estaria construindo um autômato determinístico cujos estados são conjuntos, que é o procedimento da determinização.
O que separa os dois é memória. A simulação calcula um conjunto, usa-o para o seguinte e o descarta. Guardar o conjunto ativo numa variável não constrói máquina nenhuma, assim como marcar num mapa onde o carro está não asfalta estrada alguma. Ela nunca ocupa mais memória que a máquina e refaz o trabalho a cada caractere. A determinização faz o trabalho antes e decide com uma consulta por caractere, só que 10 estados têm 1024 subconjuntos possíveis.
Para (a|b)*c a conta é modesta. A partir da partida, a, b e c produzem só quatro conjuntos além do vazio. São o inicial, os dois que se alternam e \{9\}, de onde nada sai. A tabela usaria cinco dos 1024. Se a proporção se repete em outros padrões, esta máquina não responde.
A ordem das duas operações também engana. A regra manda mover e depois fechar, e quem fecha antes de mover perde os estados alcançados por corredor depois da última catraca. Com a* sobre a, a partida é \{2, 0, 3\} e o movimento leva a \{1\}. O 3 só viria pelo corredor de saída, que ninguém cruzou, e a versão invertida recusa a. Por isso o mesmo a*, rodado sobre a cadeia vazia e sobre a, serve para diagnosticar quatro situações diferentes:
| Cadeia vazia | Cadeia a |
Diagnóstico |
|---|---|---|
| aceita | aceita | ordem e fecho inicial corretos |
| aceita | recusada | ordem invertida: fecha antes de mover |
| recusada | recusada | falta o fecho do conjunto inicial |
| recusada | aceita | defeito na construção: falta o corredor de zero vezes |
Determinizar primeiro daria uma tabela menor e mais rápida de conferir. Eu fico com a simulação enquanto a máquina for a que a construção entregou. Qualquer divergência entre traço e papel aponta, então, direto para a construção, sem um segundo procedimento no meio. A determinização entra com esta máquina já conferida, e é contra ela que a nova será comparada.
1.5 Duas garantias que não se substituem
Uma prova diz que a regra está certa; quarenta e dois casos dizem se o código a copiou direito.
O switch de construir() tem seis rótulos, e nenhum saiu de uma decisão de quem programou. Cada um é um construtor da árvore, e o ramo faz o que a regra daquele caso manda. A definição indutiva das expressões regulares dava algumas expressões de saída e formava as outras com operadores. As regras de Thompson seguem o mesmo molde, com os operadores usando só os blocos dos filhos. Uma definição nesse formato já é uma função recursiva, escrita antes de alguém abrir o editor.
A lista do código, porém, difere da matemática num item. Sai \emptyset, que nenhum padrão consegue expressar, e entra o coringa, que a notação de padrões oferece. É contra essa lista, e não contra a definição matemática, que a correspondência se verifica item a item:
| Construtor da árvore | Regra | Estados novos |
|---|---|---|
Simbolo |
caso base do símbolo | 2 |
Qualquer |
caso base do coringa | 2 |
Vazio |
caso base da cadeia vazia | 2 |
Concatenacao |
concatenação | 0 |
Alternancia |
alternância | 2 |
Fecho |
fecho | 2 |
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
Quem cobra a tabela acima é o compilador. Os construtores formam uma enumeração, e o projeto compila com avisos tratados como erro. No GCC e no Clang, o conjunto em uso acusa o switch sobre enumeração ao qual falta um valor, e esquecer o fecho impede a compilação. No MSVC esse aviso vem desligado por padrão, e o caso ausente só aparece quando alguém roda o padrão que o exige. O retorno depois do switch nunca executa e só está ali porque o compilador não sabe disso.
A correspondência desce à linha. No ramo da alternância, duas chamadas obtêm B_1 e B_2 e duas criam e e s. As quatro chamadas a adicionarTransicao() são os quatro corredores, na ordem em que a regra os enumera. E a mesma forma indutiva entrega também a prova de que a construção está certa, junto com o tamanho da máquina.
ImportanteTeorema — Toda expressão regular tem máquina equivalente de tamanho linear
Para toda expressão regular r sobre um alfabeto \Sigma, a aplicação recursiva das regras dos casos base e dos casos compostos sobre a árvore de r produz um autômato finito não determinístico com transições vazias N tal que L(N) = L(r), e o número de estados de N é O(|r|): cada caso base introduz duas unidades, cada composição introduz no máximo duas, e a concatenação não introduz nenhuma.
1.5.1 A indução que atravessa a árvore
A igualdade L(N) = L(r) sai por indução sobre a árvore, com hipótese de duas partes. Na primeira, as cadeias da entrada à saída de cada bloco filho formam exatamente a linguagem da subexpressão. Na segunda, a entrada de cada bloco não recebe transição e a saída não emite nenhuma. É a propriedade das pontas, a que as fusões de a*b* destruíram. Nas folhas não há hipótese a usar: cada bloco tem um percurso só, que lê o símbolo, lê qualquer caractere ou não lê nada.
Na concatenação, o único contato entre os blocos é o corredor de s_1 para e_2, e todo percurso se parte num trecho de cada linguagem. Na alternância, o percurso entra num bloco e só sai pela saída dele, sem trocar de lado, e a linguagem é a união. No fecho, há duas formas de percurso. Ou ele usa o corredor de zero vezes e lê a cadeia vazia, ou atravessa o interior k \ge 1 vezes, voltando pelo de novo entre uma travessia e outra. Somados todos os k, inclusive o zero, o bloco reconhece o fecho da linguagem interna.
A travessia é o passo que precisa da segunda parte da hipótese. Quem entrou em e_1 só deixa o interior por s_1. Nenhum estado interno emite transição para fora, e as transições novas saem só de e e de s_1. De s_1, ou se recomeça pelo de novo ou se encerra pelo basta, e toda chegada a s conta travessias inteiras. O bloco novo herda a propriedade, pois os estados que cada regra cria nascem sem chegada na entrada e sem partida na saída.
Dá para ver k = 2 acontecendo: rode a* sobre aa. Antes de qualquer leitura o conjunto já é \{2, 0, 3\}, e o 3 ali presente é o caminho sem travessia nenhuma. Cada a lido produz \{1, 0, 3\}. Nele, o 1 marca uma travessia recém-concluída, o 0 está de volta ao começo do interior, pronto para outra, e o 3 foi alcançado saindo pelo basta.
%%{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"]
1.5.2 O tamanho, contado nó a nó
A outra metade do teorema é aritmética. Cada nó acrescenta no máximo dois estados e quatro transições, qualquer que seja a árvore em volta. Para (a|b)*c, 6 nós dão teto de 12 estados e 24 transições, e a máquina tem 10 e 12. Das 12 transições, 9 são corredores, contados sem esperteza nenhuma:
DicaNo código
Dois laços e uma comparação com kEpsilon, a mesma marca que o caso base põe na folha \varepsilon. Corredores e catracas moram na mesma lista de saídas de cada estado, distinguidos só pelo rótulo. Uma lista separada para os corredores tornaria esta contagem imediata. Em troca, todo o resto do código passaria a ter dois caminhos para examinar as saídas de um estado.
Na mesma régua, os quatro padrões da demonstração mostram a fração de corredores subindo com os operadores. É 1 de 3 em ab, 4 de 6 em a|b, 4 de 5 em a* e 9 de 12 em (a|b)*c. O maior conjunto ativo acompanha, com 2, 3, 3 e 7 estados. Tempo de execução e memória do processo não são medidos pela demonstração, e por isso nenhum número deles aparece aqui. Por caractere, as marcas garantem que cada estado entra uma vez e cada transição é examinada uma vez. O trabalho por caractere fica limitado pelo tamanho da máquina, e o total, pelo produto do comprimento do padrão pelo da entrada.
O |r| do teorema conta nós da árvore, e não caracteres digitados. [a-z]+ tem seis caracteres e 104 nós: a faixa vira 26 folhas ligadas por 25 alternâncias, e o fecho positivo duplica a subárvore. Pela tabela de custos, 52 folhas dão 104 estados, 50 alternâncias mais 100, o fecho 2. Pois é: 206 estados por seis caracteres, ainda abaixo do teto de 208 que o teorema promete.
E o fragmento .*.*=.*, que levou um motor com retrocesso a trabalhar com o cubo do comprimento da linha? Quatro folhas, três fechos e três concatenações dão 14 estados e 19 transições, o máximo que a simulação examina por caractere. Dobrar a linha dobra esse trabalho e multiplica por oito o do retrocesso. O teorema, porém, fala só da máquina não determinística; a determinística pode precisar de um estado por subconjunto encontrado, e 14 estados têm 16.384 subconjuntos. A garantia é da classe; a entrega é da implementação. A classe garante uma consulta por caractere, e Thompson entrega uma máquina correta, linear e sem determinismo.
ImportanteSimular agora ou tabelar antes
Simular não pede preparação e gasta, a cada caractere, no máximo o tamanho da máquina de Thompson. Tabelar gasta uma consulta por caractere, mas só depois de montar uma linha para cada conjunto que a entrada puder alcançar. Muitas entradas lidas pelo mesmo padrão diluem essa montagem, e uma leitura curta acaba antes de a tabela ficar pronta. Para decidir, estime primeiro quantos estados a construção vai produzir; a tabela de custos dá esse número sem construir nada.
1.5.3 Quarenta e dois casos decididos no papel
O arquivo de casos do projeto tem 42 linhas. Cada uma traz padrão, cadeia e veredito separados por tabulação: ab com ab aceita, a.c com ac recusa, a* com a cadeia vazia aceita. O valor da linha Bateria conferida a mao: 42/42 casos passaram., que o programa imprime hoje, depende de algo que o arquivo não registra. Todo veredito foi decidido sem rodar o programa.
Caso escrito a partir da saída, conferindo se ela “parece certa”, tem a mesma cara e outra natureza. É conferir a conta do restaurante com a calculadora do garçom que a fez: bate sempre, inclusive quando ele errou. Um teste compara o código com uma expectativa independente dele, e um registro compara o código consigo mesmo, ontem e hoje. As duas baterias passam, e só o registro protege os defeitos contra a correção.
E que diferença faz, se os 42 passam? Acontece que ela só aparece na primeira correção. Suponha que a construção tivesse esquecido o corredor de zero vezes. O arquivo copiado da saída anotaria a* recusando a cadeia vazia como esperado. Consertar o corredor faria a bateria falhar, apontando para o conserto. É o quarto caso do diagnóstico de a*, desarmado pela cópia.
Cada decisão tomada até aqui tem linhas próprias no arquivo: folhas, com símbolo e cadeia vazia em casos separados, e cada um dos três operadores. As reescritas da leitura de padrões são testadas também, pois a+ chega à construção como a seguido de a*, e a? como (a|ε). Para o coringa há a.c contra ac, recusa, já que o ponto precisa comer exatamente um caractere. Fecham o arquivo três cadeias contra [a-z]+@[a-z]+\.[a-z]+: um endereço inteiro, um sem ponto no domínio e um sem a parte do usuário.
Cada veredito sai de raciocínio sobre a linguagem, nunca sobre a máquina. (ab)* recusa aba porque toda cadeia dele tem comprimento par; -?[0-9]+ recusa --42 porque o opcional admite um só sinal de menos. Nenhum dos raciocínios passa por estado ou corredor, e por isso eles servem de juiz. Se a simulação discordar, o erro está no código ou em quem escreveu o caso, e acrescentar um caso novo é acrescentar uma linha, sem recompilar nada.
Uma conferência dispensa cadeia. Toda máquina da construção tem um só estado de aceitação, marcado na saída do bloco raiz. E cada estado, exceto a entrada da raiz, recebe ao menos uma transição. Uma alternância sem o corredor de e para e_2 deixaria órfã a entrada do segundo bloco, o estado 2 em a|b. Contar chegadas estado por estado acusaria isso. A cadeia a não acusaria, porque o lado esquerdo segue intacto; só b, recusada por engano, denunciaria.
O subcomando da bateria devolve código de saída diferente de zero quando algum caso discorda, e por isso entra na verificação automática do projeto. A mensagem traz arquivo e linha do caso, veredito esperado e obtido, e um padrão recusado pela leitura conta como falha, com o erro anexado. Prova e bateria pegam defeitos diferentes. A indução garante que a regra do fecho está certa, e a bateria verifica se o código a transcreveu. Um corredor esquecido derruba o quarto caso de a*, mas deixa a prova de pé.
1.5.4 Onde a transcrição direta cobra
A recursão tem um limite, e ele mora na pilha de execução. A profundidade de construir() é a altura da árvore. Como a leitura associa a concatenação à esquerda, abcd vira abc seguido de d, e n literais em sequência dão altura n - 1. Em padrões digitados por gente, nada se nota. Mas um padrão gerado por outro programa pode ter centenas de milhares de símbolos e esgotar a pilha (que tem tamanho fixo). Aí a transcrição teria de virar percurso com pilha explícita.
E se alguém pulasse a máquina não determinística e montasse a determinística direto? Para a|b funciona. Para ab|ac, a regra da alternância teria de abrir as duas peças, achar o prefixo comum e fundi-lo, perdendo a interface de duas pontas. A etapa poupada voltaria multiplicada, um caso especial para cada par de alternativas com prefixo comum. O código nascido assim acerta os casos simples e falha em união e fecho.
Poucas etapas do compilador oferecem esse conforto de novo. A determinização itera sobre conjuntos até que nada mude, e árvore nenhuma guia esse processo. O analisador descendente fica mais perto, porque gramáticas também se definem por indução. Só que ali certas regras chamam a si mesmas antes de consumir um único símbolo, e a transcrição literal precisa ser adaptada. Já na geração de código, as decisões entre a ideia de percorrer a árvore emitindo instruções e o programa que o faz não vêm de definição alguma.
Para ir além, os livros se separam na mesma linha que separa implementar de provar. Em Compiladores: princípios, técnicas e ferramentas, Aho põe a construção a serviço do analisador léxico. Já a Introdução à teoria de autômatos, linguagens e computação, de Hopcroft, Motwani e Ullman, e Linguagens formais e autômatos, de Menezes, a usam como metade de um teorema: expressões e autômatos descrevem a mesma classe. A outra metade vai da máquina de volta à expressão, eliminando estados um a um, e é um caminho que compilador nenhum precisa percorrer.
1.6 A Peneira transforma padrões em máquinas
O módulo nfa da Peneira inteiro, lido com as Definições 4.6 e 4.7 abertas ao lado.
O módulo nfa tem três partes. A construção transforma a árvore de um padrão em máquina. A simulação executa essa máquina sobre uma cadeia. E a bateria de casos confere as duas contra vereditos determinados à mão. Os trechos mostrados ao longo das seções anteriores saíram daqui e aparecem agora no contexto do arquivo inteiro. O marco executável deste ponto compila só os módulos 01 a 04 da Peneira. A demonstração que ele roda imprime a máquina de quatro expressões, o traço dos conjuntos ativos e o resultado da bateria.
1.6.1 A construção, caso a caso
04_afn.h
// 04_afn.h — A máquina não determinística e a construção de Thompson.
//
// Aqui a árvore produzida pela leitura de patterns vira máquina. A construção é
// indutiva sobre a estrutura da árvore, e é o único ponto do percurso em que a
// definição do quadro se transcreve quase sem adaptação: cada caso da definição
// vira uma função, e a composição dos casos vira a recursão.
//
// O que torna a construção sistemática é a INTERFACE UNIFORME dos blocos. Todo
// bloco construído tem exatamente uma entrada e exatamente uma saída, e é essa
// promessa que permite compor blocos sem saber o que há dentro deles. Se um
// único caso quebrasse a promessa — devolvendo dois estados de saída, digamos —,
// os outros três precisariam tratá-lo como exceção, e a construção deixaria de
// ser mecânica.
//
// Não determinismo aqui não é curiosidade: é ferramenta de construção. Ele
// permite que os casos sejam locais (cada um só conhece os blocos que recebe),
// ao preço de uma máquina que precisa de simulação por conjunto de estados em
// vez de um estado corrente. O arco seguinte paga esse preço de volta.
#ifndef PENEIRA_04_AFN_H
#define PENEIRA_04_AFN_H
#include <cstddef>
#include <string>
#include <vector>
#include "02_regex.h"
#include "03_afd.h"
namespace peneira {
// A transição vazia não consome símbolo. Marcamos com o byte zero porque ele não
// pode aparecer num pattern escrito por quem usa a Peneira — o texto do programa
// é uma cadeia de caracteres, e o zero termina cadeias.
inline constexpr char kEpsilon = '\0';
// O coringa `.` chegou da leitura como folha própria, e não expandido em
// alternância (decisão registrada no arco anterior). Ele precisa, portanto, de
// uma marca de transição própria: casa qualquer símbolo, mas não é vazia.
inline constexpr char kQualquer = '\x01';
struct TransicaoAfn {
char simbolo = kEpsilon;
Estado destino = 0;
};
// Um bloco de máquina com uma entrada e uma saída — o invariante da construção.
struct Bloco {
Estado entrada = 0;
Estado saida = 0;
};
// O traço de uma simulação: quais estados estavam ativos depois de cada símbolo.
// É o que mostra o não determinismo acontecendo, em vez de afirmá-lo.
struct PassoDaSimulacao {
char simboloLido = '\0';
std::vector<Estado> ativos;
};
struct Simulacao {
bool aceitou = false;
std::vector<PassoDaSimulacao> passos;
std::size_t maiorConjuntoAtivo = 0;
};
class Afn {
public:
Estado novoEstado();
void adicionarTransicao(Estado origem, char simbolo, Estado destino);
void definirInicial(Estado estado);
void definirAceitacao(Estado estado);
Estado inicial() const;
Estado aceitacao() const;
std::size_t quantidadeDeEstados() const;
std::size_t quantidadeDeTransicoes() const;
std::size_t quantidadeDeTransicoesVazias() const;
// O fecho vazio de um conjunto: todos os estados alcançáveis a partir dele
// sem consumir símbolo algum. É a operação básica da simulação, e a que
// quem implementa esquece de aplicar ao conjunto INICIAL.
std::vector<Estado> fechoVazio(const std::vector<Estado>& conjunto) const;
// Acrescentado no arco da determinizacao: a construcao de subconjuntos
// precisa percorrer as saidas de cada estado a partir de fora da classe.
const std::vector<TransicaoAfn>& transicoesDe(Estado estado) const;
bool aceita(const std::string& cadeia) const;
Simulacao simular(const std::string& cadeia) const;
std::string formatarSimulacao(const std::string& cadeia, const Simulacao& simulacao) const;
private:
std::vector<std::vector<TransicaoAfn>> transicoes_;
Estado inicial_ = 0;
Estado aceitacao_ = 0;
};
// A construção propriamente dita: árvore do arco anterior em máquina.
Afn construirThompson(const Arvore& arvore);
// Um caso da bateria conferida à mão: o pattern, a cadeia e o veredito que
// determinamos sem rodar o programa.
struct CasoDeTeste {
std::string expressao;
std::string cadeia;
bool esperado = false;
std::string origem; // arquivo:linha, para a mensagem de falha ser útil
};
struct ResultadoDaBateria {
std::size_t total = 0;
std::size_t passaram = 0;
std::vector<std::string> falhas;
bool arquivoLido = false;
};
// Lê a bateria do arquivo de casos e executa cada linha contra a simulação.
std::vector<CasoDeTeste> lerCasos(const std::string& caminho);
ResultadoDaBateria rodarBateria(const std::vector<CasoDeTeste>& casos);
} // namespace peneira
#endif // PENEIRA_04_AFN_H
04_afn.cpp
#include "04_afn.h"
#include <fstream>
#include <sstream>
namespace peneira {
Estado Afn::novoEstado() {
transicoes_.emplace_back();
return transicoes_.size() - 1;
}
void Afn::adicionarTransicao(const Estado origem, const char simbolo, const Estado destino) {
transicoes_[origem].push_back(TransicaoAfn{simbolo, destino});
}
void Afn::definirInicial(const Estado estado) { inicial_ = estado; }
void Afn::definirAceitacao(const Estado estado) { aceitacao_ = estado; }
Estado Afn::inicial() const { return inicial_; }
Estado Afn::aceitacao() const { return aceitacao_; }
std::size_t Afn::quantidadeDeEstados() const { return transicoes_.size(); }
const std::vector<TransicaoAfn>& Afn::transicoesDe(const Estado estado) const {
return transicoes_[estado];
}
std::size_t Afn::quantidadeDeTransicoes() const {
std::size_t total = 0;
for (const std::vector<TransicaoAfn>& saidas : transicoes_) {
total += saidas.size();
}
return total;
}
// recorte:inicio contar-transicoes-vazias
std::size_t Afn::quantidadeDeTransicoesVazias() const {
std::size_t total = 0;
for (const std::vector<TransicaoAfn>& saidas : transicoes_) {
for (const TransicaoAfn& transicao : saidas) {
if (transicao.simbolo == kEpsilon) {
++total;
}
}
}
return total;
}
// recorte:fim contar-transicoes-vazias
// recorte:inicio fecho-vazio-com-marcacao
std::vector<Estado> Afn::fechoVazio(const std::vector<Estado>& conjunto) const {
// Busca em profundidade sobre as transições vazias, com marcação de visitado
// num vetor denso (um byte por estado, por chamada). A marcação garante o
// término quando há ciclo de transições vazias, o que acontece quando o
// interior de um fecho pode ser atravessado sem ler símbolo — `a**` e
// `(a?)*`, por exemplo. Em `a*` o retorno passa pela transição que lê `a`,
// não há ciclo de transições vazias, e o defeito não aparece.
std::vector<char> visitado(transicoes_.size(), 0);
std::vector<Estado> pilha;
std::vector<Estado> resultado;
for (const Estado estado : conjunto) {
if (!visitado[estado]) {
visitado[estado] = 1;
pilha.push_back(estado);
resultado.push_back(estado);
}
}
while (!pilha.empty()) {
const Estado atual = pilha.back();
pilha.pop_back();
for (const TransicaoAfn& transicao : transicoes_[atual]) {
if (transicao.simbolo != kEpsilon) {
continue;
}
if (!visitado[transicao.destino]) {
visitado[transicao.destino] = 1;
pilha.push_back(transicao.destino);
resultado.push_back(transicao.destino);
}
}
}
return resultado;
}
// recorte:fim fecho-vazio-com-marcacao
Simulacao Afn::simular(const std::string& cadeia) const {
Simulacao simulacao;
// recorte:inicio conjunto-ativo-comeca-no-fecho
// 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();
// recorte:fim conjunto-ativo-comeca-no-fecho
// Marcação densa reusada entre os símbolos: zerar um vetor de bytes é mais
// barato do que alocar um conjunto ordenado por símbolo consumido, e a
// simulação faz isso uma vez por caractere de entrada.
std::vector<char> presente(transicoes_.size(), 0);
for (const char simbolo : cadeia) {
std::vector<Estado> proximos;
for (const Estado estado : ativos) {
for (const TransicaoAfn& transicao : transicoes_[estado]) {
const bool casa =
transicao.simbolo == simbolo ||
(transicao.simbolo == kQualquer && simbolo != kEpsilon);
if (!casa) {
continue;
}
if (!presente[transicao.destino]) {
presente[transicao.destino] = 1;
proximos.push_back(transicao.destino);
}
}
}
for (const Estado estado : proximos) {
presente[estado] = 0;
}
ativos = fechoVazio(proximos);
simulacao.passos.push_back(PassoDaSimulacao{simbolo, ativos});
if (ativos.size() > simulacao.maiorConjuntoAtivo) {
simulacao.maiorConjuntoAtivo = ativos.size();
}
if (ativos.empty()) {
// Sem estado ativo, nenhum símbolo posterior reativa coisa alguma.
break;
}
}
// Aceitação por EXISTÊNCIA de caminho: basta que o estado de aceitação esteja
// entre os ativos ao fim. Não é preciso que todos os caminhos aceitem — e é
// essa assimetria que distingue o não determinismo do determinismo.
for (const Estado estado : ativos) {
if (estado == aceitacao_) {
simulacao.aceitou = true;
break;
}
}
return simulacao;
}
bool Afn::aceita(const std::string& cadeia) const { return simular(cadeia).aceitou; }
std::string Afn::formatarSimulacao(const std::string& cadeia, const Simulacao& simulacao) const {
std::string texto = " pattern sobre \"" + cadeia + "\"\n";
for (const PassoDaSimulacao& passo : simulacao.passos) {
texto += " ";
if (passo.simboloLido == '\0') {
texto += "inicio ";
} else {
texto += "apos '";
texto += passo.simboloLido;
texto += "' ";
}
texto += "-> { ";
for (std::size_t i = 0; i < passo.ativos.size(); ++i) {
if (i > 0) {
texto += ", ";
}
texto += std::to_string(passo.ativos[i]);
}
texto += " }\n";
}
texto += std::string(" resultado: ") + (simulacao.aceitou ? "ACEITA" : "RECUSA");
texto += " | maior conjunto ativo: " + std::to_string(simulacao.maiorConjuntoAtivo) + "\n";
return texto;
}
// --- a construção de Thompson ------------------------------------------------
namespace {
// Um caso por construtor da árvore, e a recursão faz a composição. Repare que
// nenhum caso precisa saber o que há dentro dos blocos que recebe: só que cada
// um tem uma entrada e uma saída.
Bloco construir(const Arvore& arvore, const std::size_t indice, Afn& afn) {
const No& no = arvore.nos[indice];
switch (no.tipo) {
// recorte:inicio thompson-caso-base
case TipoDeNo::Simbolo:
case TipoDeNo::Qualquer:
case TipoDeNo::Vazio: {
// Os três casos base têm a mesma forma — dois estados e uma
// transição —, e diferem apenas no rótulo dela.
const Estado entrada = afn.novoEstado();
const Estado saida = afn.novoEstado();
const char rotulo = no.tipo == TipoDeNo::Simbolo ? no.simbolo
: no.tipo == TipoDeNo::Qualquer ? kQualquer
: kEpsilon;
afn.adicionarTransicao(entrada, rotulo, saida);
return Bloco{entrada, saida};
}
// recorte:fim thompson-caso-base
// recorte:inicio thompson-concatenacao
case TipoDeNo::Concatenacao: {
// A saída do primeiro passa a alimentar a entrada do segundo. Uma
// transição vazia liga os dois em vez de fundir os estados: fundir
// funcionaria aqui e quebraria a uniformidade da interface.
const Bloco esquerdo = construir(arvore, no.esquerda, afn);
const Bloco direito = construir(arvore, no.direita, afn);
afn.adicionarTransicao(esquerdo.saida, kEpsilon, direito.entrada);
return Bloco{esquerdo.entrada, direito.saida};
}
// recorte:fim thompson-concatenacao
// recorte:inicio thompson-alternancia
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};
}
// recorte:fim thompson-alternancia
// recorte:inicio thompson-fecho
case TipoDeNo::Fecho: {
const Bloco interno = construir(arvore, no.esquerda, afn);
const Estado entrada = afn.novoEstado();
const Estado saida = afn.novoEstado();
afn.adicionarTransicao(entrada, kEpsilon, interno.entrada); // uma vez ou mais
afn.adicionarTransicao(entrada, kEpsilon, saida); // zero vezes
afn.adicionarTransicao(interno.saida, kEpsilon, interno.entrada); // de novo
afn.adicionarTransicao(interno.saida, kEpsilon, saida); // basta
return Bloco{entrada, saida};
}
// recorte:fim thompson-fecho
}
// Inalcançável: o switch cobre todos os construtores da árvore. O retorno
// existe porque o compilador não sabe disso, e omiti-lo seria aviso — que
// aqui é erro.
return Bloco{0, 0};
}
} // namespace
Afn construirThompson(const Arvore& arvore) {
Afn afn;
if (arvore.vazia()) {
const Estado unico = afn.novoEstado();
afn.definirInicial(unico);
afn.definirAceitacao(unico);
return afn;
}
const Bloco raiz = construir(arvore, arvore.raiz, afn);
afn.definirInicial(raiz.entrada);
afn.definirAceitacao(raiz.saida);
return afn;
}
// --- a bateria de casos conferidos à mão -------------------------------------
std::vector<CasoDeTeste> lerCasos(const std::string& caminho) {
std::vector<CasoDeTeste> casos;
std::ifstream arquivo(caminho);
if (!arquivo) {
return casos;
}
std::string linha;
std::size_t numeroDaLinha = 0;
while (std::getline(arquivo, linha)) {
++numeroDaLinha;
if (linha.empty() || linha[0] == '#') {
continue;
}
// Formato: expressao <TAB> cadeia <TAB> aceita|recusa
std::istringstream campos(linha);
CasoDeTeste caso;
std::string veredito;
if (!std::getline(campos, caso.expressao, '\t') ||
!std::getline(campos, caso.cadeia, '\t') || !std::getline(campos, veredito)) {
continue;
}
caso.esperado = veredito == "aceita";
caso.origem = caminho + ":" + std::to_string(numeroDaLinha);
casos.push_back(caso);
}
return casos;
}
ResultadoDaBateria rodarBateria(const std::vector<CasoDeTeste>& casos) {
ResultadoDaBateria resultado;
resultado.arquivoLido = !casos.empty();
for (const CasoDeTeste& caso : casos) {
++resultado.total;
const Resultado leitura = analisarExpressao(caso.expressao);
if (!leitura.ok) {
resultado.falhas.push_back(caso.origem + ": pattern recusado pela leitura — " +
leitura.erro.mensagem);
continue;
}
const Afn afn = construirThompson(leitura.arvore);
const bool obtido = afn.aceita(caso.cadeia);
if (obtido == caso.esperado) {
++resultado.passaram;
continue;
}
resultado.falhas.push_back(caso.origem + ": /" + caso.expressao + "/ sobre \"" +
caso.cadeia + "\" — esperado " +
(caso.esperado ? "aceita" : "recusa") + ", obtido " +
(obtido ? "aceita" : "recusa"));
}
return resultado;
}
} // namespace peneira
Um só detalhe da construção não apareceu em recorte nenhum, porque não está no switch: a função pública que o envolve cuida de um caso que a árvore não cobre, o padrão vazio. Para ele, a máquina tem um estado só, ao mesmo tempo inicial e de aceitação, e aceita apenas a cadeia vazia.
1.6.2 A bateria conferida à mão
A bateria é um arquivo de dados, lido linha a linha pela função que carrega os casos. Linhas vazias e comentários são ignorados; as demais são partidas em três campos por tabulação. Cada caso guarda também o arquivo e a linha de onde veio, para que a mensagem de falha aponte o lugar exato a corrigir.
exemplos/04_casos.txt
# 04_casos.txt — bateria conferida A MAO, caso por caso.
#
# Formato: expressao <TAB> cadeia <TAB> aceita|recusa
#
# O veredito de cada linha foi determinado SEM rodar o programa. E essa
# independencia que da valor a bateria: a partir do proximo capitulo, tudo o
# mais sera verificado contra algo que o proprio sistema produziu, e estes
# casos serao a unica evidencia externa que resta.
#
# A cadeia vazia e o campo vazio entre dois tabuladores.
# --- casos base
a a aceita
a recusa
a b recusa
a aa recusa
# --- concatenacao
ab ab aceita
ab a recusa
ab abc recusa
# --- alternancia
a|b a aceita
a|b b aceita
a|b c recusa
a|b ab recusa
x|y|z y aceita
# --- fecho: o unico operador que aceita a cadeia vazia
a* aceita
a* a aceita
a* aaa aceita
a* aab recusa
a** aaa aceita
# --- fecho positivo, reduzido a concat(x, fecho(x)) na leitura
a+ recusa
a+ a aceita
a+ aaa aceita
# --- opcional, reduzido a alt(x, vazio) na leitura
a? aceita
a? a aceita
a? aa recusa
# --- coringa: casa um simbolo qualquer, mas NAO a cadeia vazia
a.c abc aceita
a.c a c aceita
a.c ac recusa
a.c abbc recusa
# --- grupo e composicao
(ab)* aceita
(ab)* abab aceita
(ab)* aba recusa
(a|b)*c c aceita
(a|b)*c abbac aceita
(a|b)*c abb recusa
# --- classes de simbolos
[0-9]+ 240 aceita
[0-9]+ 24a recusa
[0-9]+ recusa
-?[0-9]+ -42 aceita
-?[0-9]+ 42 aceita
-?[0-9]+ --42 recusa
# --- o pattern de endereco do primeiro exemplo do percurso
[a-z]+@[a-z]+\.[a-z]+ ana@exemplo.com aceita
[a-z]+@[a-z]+\.[a-z]+ ana@exemplo recusa
[a-z]+@[a-z]+\.[a-z]+ @exemplo.com recusa
Os três últimos casos voltam ao padrão de endereço de correio eletrônico, o primeiro exemplo que a Peneira precisou reconhecer. Ele atravessa agora o sistema inteiro: é lido como texto, vira árvore, vira máquina e é executado sobre três cadeias, sem que nenhuma parte do caminho tenha sido escrita à mão para ele.
1.7 De volta aos seis estados
Volte à pergunta da abertura com a máquina montada na mão. O 6 está no conjunto por ser a entrada do bloco raiz. O 4 veio do corredor do fecho que entra no interior, e o 7, do que o pula. O 8 chegou pelo corredor que a concatenação pôs 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. Cada um dos seis estados tem uma regra com nome por trás, e nenhum foi palpite.
A estação de metrô sai desta história com a ressalva que ela exigia. Enquanto a máquina é a da construção, ela ocupa todas as plataformas alcançáveis ao mesmo tempo, e um passageiro de verdade não faz isso. A determinização vai dar um número único a cada conjunto de plataformas. Aí a imagem volta a servir sem ressalva: um passageiro, uma plataforma, uma ficha por catraca.
1.7.1 A Peneira antes da determinização
A Peneira agora aceita um padrão escrito por quem usa a linguagem e o transforma, sem intervenção manual, numa máquina que decide sobre cadeias. Essa máquina é a da construção de Thompson, com as transições vazias e o conjunto ativo que a simulação carrega a cada caractere. O executor determinístico construído antes continua sem receber nenhuma máquina gerada a partir de padrão, porque ainda falta o procedimento que converte uma máquina na outra.
Esse procedimento é o próximo módulo da Peneira, e ele chega com um problema de verificação já resolvido. Toda máquina determinística obtida da construção de subconjuntos terá de aceitar exatamente as mesmas cadeias que a máquina de Thompson aceita. Os quarenta e dois vereditos do arquivo de casos são o primeiro juiz dessa igualdade. O segundo é a comparação direta entre as duas máquinas, sobre as mesmas cadeias.
Faça agora a conta sobre o seu próprio projeto. Escolha o padrão mais complicado que a sua linguagem precisa aceitar, desenhe a árvore dele e conte os nós por tipo. Pela tabela de custos dos casos, calcule quantos estados e quantas transições vazias a construção vai produzir. Só depois rode a sua implementação e compare. Se os números não baterem, a divergência aponta uma regra transcrita de forma diferente da definição, e a tabela de transições com a regra de origem ao lado é o lugar de procurá-la.
O que construir no seu próprio projeto, com a máquina destas páginas como modelo, está nos enunciados a seguir.
Tarefa 1: Converter a árvore em máquina não determinística
Implemente a construção que transforma a estrutura em árvore produzida pela leitura de padrões em uma máquina não determinística. A tarefa se cumpre quando qualquer expressão aceita pela leitura produz uma máquina — sem exceção reservada para um operador que ficou de fora, porque um operador não coberto aqui reaparece como falha silenciosa três capítulos adiante, sobre uma entrada que ninguém escreveu à mão.
Vale registrar no diário da construção uma observação sobre esta etapa: a construção teórica se transcreve quase diretamente em código, praticamente sem adaptação. É o único ponto do percurso em que isso acontece de forma tão limpa, e perceber a diferença entre este caso e os seguintes é parte do que se aprende aqui.
Tarefa 2: Simular a máquina não determinística
Implemente a simulação que executa a máquina construída sobre uma cadeia de entrada. A dificuldade não está no algoritmo, e sim em manter a coleção de estados simultaneamente ativos sem que o custo dessa manutenção domine a execução — o que exige decidir como representar um conjunto de estados, e não apenas um estado.
Tarefa 3: Montar a bateria de casos conferidos à mão
Construa um conjunto de casos em que o resultado da simulação é comparado com o que você determinou à mão, cadeia por cadeia. Casos conferidos à mão são caros de produzir e é justamente por isso que valem: eles são a única evidência independente do próprio código, e a partir daqui todas as peças do sistema serão verificadas contra alguma coisa que o sistema mesmo produziu. Guarde-os no repositório e mantenha-os rodando pelo comando único de reconstrução — a partir do capítulo seguinte, é essa bateria que vai avisar quando a máquina reduzida deixar de aceitar o que a original aceitava.