1 Determinização e minimização

Uma máquina que segue vários caminhos ao mesmo tempo vira uma tabela de consulta, e depois as linhas da tabela que respondem igual viram uma só.

Deixe papel e lápis por perto: as tabelas de (a|b)*abb se refazem à mão, linha a linha.

Duas espécies de máquina que leem texto já apareceram. A primeira responde a cada leitura com uma consulta a uma tabela, mas as três máquinas dessa espécie que apareceram foram escritas à mão. A segunda sai pronta de um procedimento, a partir de um molde de texto, mas a cada leitura o programa refaz uma conta sobre a máquina inteira. Aqui, um procedimento converte uma máquina da segunda espécie numa da primeira, e outro deixa a tabela que resulta com o menor número de linhas. Oito palavras que já apareceram voltam, nas seis linhas do quadro:

Palavra	O que é, com um exemplo
símbolo, alfabeto	uma peça que pode aparecer num texto, como a ou 7; a lista dos símbolos permitidos, escrita \Sigma (sigma maiúsculo), aqui quase sempre a e b
cadeia, comprimento	uma fileira de símbolos, como abb; quantos símbolos ela tem, aqui 3
cadeia vazia	a fileira com zero símbolos, escrita \varepsilon (épsilon): o que falta ler de abb depois dos três símbolos
\Sigma^*	“sigma estrela”: todas as cadeias feitas com os símbolos de \Sigma, inclusive a vazia; com a e b, abb está nele, e abc não
linguagem	um conjunto de cadeias, como o das cadeias de a e b que terminam em abb
expressão regular, ou padrão	um molde curto que descreve uma linguagem: (a|b)*abb

Um programa guarda a expressão numa árvore, um desenho em forma de organograma. Cada caixinha é um nó; as de baixo são as folhas, e as de cima guardam operações. Dos seis tipos de nó, três são folhas: o símbolo, a cadeia vazia e o coringa, o ponto ., que vale por um símbolo qualquer do alfabeto. Os outros três são operações: a concatenação cola dois pedaços (xy), a alternância escolhe um entre vários, como em a|b|c, juntando dois pedaços em cada nó (x|y), e o fecho repete zero ou mais vezes (x*). O resto da notação é atalho. O leitor de padrões, a parte que lê o texto do padrão e monta a árvore, traduz cada atalho antes de montar:

• x+, “x uma ou mais vezes”, vira xx*;
• x?, “x, ou nada”, vira (x|ε);
• a faixa [0-9], “um dígito de 0 a 9”, vira 0|1|…|9: dez folhas ligadas por nove alternâncias.

O autômato finito determinístico é a máquina que lê cadeias, e a imagem dele é um jogo de tabuleiro. Cada estado é uma casa, e um peão marca a casa atual, a começar pelo estado inicial. Cada transição é uma seta com um símbolo escrito, e o peão anda por ela quando esse símbolo é lido. Se a cadeia acaba com o peão num estado de aceitação, a máquina aceita a cadeia; se acaba em outro, ela a recusa. Determinístico quer dizer que de cada casa, com cada símbolo, sai exatamente uma seta: o peão nunca tem escolha. O símbolo que não serve leva ao estado de erro, de onde o peão não sai mais. A tabela de transição tem uma linha por estado e uma coluna por símbolo, e cada célula, o cruzamento de uma linha com uma coluna, guarda o estado de destino.

A máquina do módulo da construção de Thompson é não determinística: depois de ler um símbolo, ela pode estar em vários estados ao mesmo tempo, com um peão em cada um. As setas dela têm nomes de uma estação de metrô. A catraca lê um símbolo; o corredor não lê nada, e o nome técnico dele é transição vazia, que nos desenhos leva a letra \varepsilon. O peão sem catraca para o símbolo lido sai do tabuleiro, e por isso essa máquina dispensa o estado de erro. Ela aceita a cadeia quando algum peão termina num estado de aceitação. Os estados ocupados depois de cada leitura formam o conjunto ativo. A construção de Thompson monta a máquina a partir da árvore, com uma regra por tipo de nó, e a máquina que ela monta tem um único estado de aceitação. A tabela de custos diz quantos estados cada regra cria: dois por folha, dois por alternância, dois por fecho e nenhum por concatenação.

O padrão -?[0-9]+ descreve um número inteiro com sinal de menos opcional, como -42. Traduzidos os atalhos, a árvore dele tem três partes:

• -? vira (-|ε): duas folhas e uma alternância;
• [0-9]+ vira a faixa seguida do fecho de uma cópia dela: vinte folhas, dezoito alternâncias, um fecho e uma concatenação;
• uma concatenação junta os dois pedaços.

Pela tabela de custos, as 22 folhas, as 19 alternâncias, o fecho e as duas concatenações, que não criam estado, dão à máquina de Thompson 22 \times 2 + 19 \times 2 + 1 \times 2 = 84 estados. Trocar essa máquina por uma determinística que aceita as mesmas cadeias é determinizar a máquina, e o procedimento é a determinização. Para esse padrão, a determinização entrega 23 estados, e a minimização troca a máquina de 23 por uma de quatro, a menor possível. As duas contagens incluem o estado de erro, e as três máquinas aceitam as mesmas cadeias. As contas do 23 e do 4 estão em Seção 1.4.

Cada estado da máquina determinística é um conjunto de estados da máquina de Thompson. Cada um dos 84 estados pode estar ou não estar num conjunto, e por isso há 2^{84} conjuntos possíveis: o produto de 84 fatores iguais a 2, um número de 26 algarismos. Daí vem a ideia de que determinizar aumenta a máquina. Mas a determinística saiu menor nos quatro padrões da tabela de Seção 1.5, (a|b)*abb, a(b|c)*d, -?[0-9]+ e a.c. Já numa linguagem com um número n à escolha, montada de propósito em Seção 1.3.1, a máquina de Thompson vai de 10 a 52 estados com n de 1 a 8. A determinística, no mesmo intervalo, vai de 4 a 258, também com o estado de erro na conta.

De um caso para o outro, o procedimento é o mesmo; muda a linguagem pedida. Separar os dois casos tem uso direto: diante de uma máquina que ficou grande, você precisa decidir se o defeito está no seu programa ou se o tamanho vem do padrão que alguém escreveu.

1.1 Do conjunto ativo à tabela de consulta

A expressão (a|b)*abb descreve as cadeias de a e b que terminam em abb, como babb. A construção de Thompson monta para ela uma máquina de 14 estados, de 0 a 13. Os oito primeiros, com as setas entre eles, são os oito primeiros da máquina de (a \mid b)^{*}c, do módulo da construção de Thompson; os seis últimos são os das folhas a, b e b do fim:

Estado	Lendo um símbolo, vai para	Por transição vazia, vai para
0	1, com a	—
1	—	5
2	3, com b	—
3	—	5
4	—	0 e 2
5	—	4 e 7
→ 6	—	4 e 7
7	—	8
8	9, com a	—
9	—	10
10	11, com b	—
11	—	12
12	13, com b	—
13	—	—

O → marca o estado inicial, e o negrito, o de aceitação. Cinco folhas, uma alternância, um fecho e três concatenações dão, pela tabela de custos, 5 \times 2 + 2 + 2 = 14 estados.

A simulação é a execução dessa máquina sobre uma cadeia, como no módulo da construção de Thompson. O conjunto ativo de partida reúne o estado inicial e tudo o que se alcança dele só por corredores. A cada símbolo lido, andam os peões que têm catraca para ele, e depois se seguem os corredores a partir dos estados aonde eles chegaram. Com abb:

Leitura	Depois das catracas	Conjunto ativo	Tamanho
nenhuma ainda	—	\{0, 2, 4, 6, 7, 8\}	6
a	\{1, 9\}	\{0, 1, 2, 4, 5, 7, 8, 9, 10\}	9
b	\{3, 11\}	\{0, 2, 3, 4, 5, 7, 8, 11, 12\}	9
b	\{3, 13\}	\{0, 2, 3, 4, 5, 7, 8, 13\}	8

Os conjuntos vêm em ordem crescente, e a ordem dos elementos não muda o conjunto. O último contém o 13, e abb é aceita. A conta do conjunto seguinte usa só o conjunto atual e o símbolo lido, e por isso dá sempre o mesmo resultado para o mesmo par. Em aab, cada a faz andar os mesmos peões, os do 0 e do 8, e devolve o conjunto da segunda linha. Mesmo assim, a simulação refaz a conta a cada símbolo de cada cadeia.

Uma conta que dá sempre o mesmo resultado pode ser feita uma vez e guardada numa tabela. O módulo da construção de Thompson deu nome a isso: determinizar, que é construir o autômato determinístico cujos estados são conjuntos de estados da máquina original. Em (a|b)*abb, o estado inicial da máquina nova é \{0, 2, 4, 6, 7, 8\}. No tabuleiro da máquina de Thompson havia um peão em cada casa do conjunto ativo. O tabuleiro novo tem um peão só, e cada casa dele é um conjunto de casas do antigo: a casa em que o peão está diz onde estariam todos os peões da máquina de Thompson. O tabuleiro novo não tem corredores, e toda seta dele lê um símbolo.

O procedimento que monta o tabuleiro novo é a construção de subconjuntos. Ele usa as duas contas da simulação (a das catracas e a dos corredores) e duas listas: vamos chamar de catálogo a dos conjuntos que já receberam número, e de pendentes os conjuntos do catálogo cujas transições ainda falta calcular.

1. Calcule o conjunto de partida da simulação. Dê a ele o número 0 e ponha-o no catálogo e nos pendentes.
2. Tire um conjunto dos pendentes. Para cada símbolo do alfabeto, calcule o conjunto a que ele leva: primeiro as transições que leem o símbolo, depois as transições vazias.
3. Se o resultado já está no catálogo, a transição vai para o número dele. Se não está, ele recebe o próximo número e entra no catálogo e nos pendentes.
4. Volte ao passo 2 enquanto houver pendentes.

Para (a|b)*abb, com o alfabeto de a e b:

Conjunto tirado dos pendentes	Lendo a	Lendo b	Entra no catálogo
0, que é \{0, 2, 4, 6, 7, 8\}	\{0, 1, 2, 4, 5, 7, 8, 9, 10\}, que é novo: 1	\{0, 2, 3, 4, 5, 7, 8\}, que é novo: 2	1 e 2
1	o próprio 1	\{0, 2, 3, 4, 5, 7, 8, 11, 12\}, que é novo: 3	3
2	1	o próprio 2	nenhum
3	1	\{0, 2, 3, 4, 5, 7, 8, 13\}, que é novo: 4	4
4	1	2	nenhum

Refaça a segunda linha com a tabela da máquina de Thompson ao lado: no conjunto 1, as catracas de a saem do 0 e do 8, e as de b, do 2 e do 10. Depois da quinta linha não há pendentes, e o catálogo tem cinco conjuntos, número que ninguém escolheu. As três primeiras colunas do quadro são a tabela de transição da máquina nova, com o estado inicial 0. O 4 é o único conjunto que contém o 13, o estado de aceitação da máquina de Thompson, e por isso é o único estado de aceitação da máquina nova. A ordem em que os conjuntos saem dos pendentes não muda os conjuntos, mas pode mudar os números que eles recebem. Daqui em diante, a máquina determinística que sai dessa construção é a máquina determinizada, para separá-la das que alguém escreve à mão.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}") -->|a| D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D0 -->|b| D2("2<br/>{0,2,3,4,5,7,8}")
    D1 -->|a| D1
    D1 -->|b| D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D2 -->|a| D1
    D2 -->|b| D2
    D3 -->|a| D1
    D3 -->|b| D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    D4 -->|a| D1
    D4 -->|b| D2

Figura 1: A máquina determinizada de (a|b)*abb, sem o estado de erro: cinco estados, cada um com o conjunto de estados da máquina de Thompson que ele é.

No desenho, o estado inicial e o de aceitação vêm indicados por extenso, e cada seta vale por uma transição. O estado de erro não aparece, e em (a|b)*abb nenhuma seta leva a ele. Os cinco conjuntos contêm o 0 e o 2 da máquina de Thompson, de onde saem as transições que leem a e b, e por isso nenhuma conta do quadro deu um conjunto sem estados. O projeto de referência, o programa visto por dentro neste módulo, cria o estado de erro em toda máquina determinística, mesmo quando nada leva a ele, e o conta. Os números de estados daqui em diante seguem essa contagem: a determinizada de (a|b)*abb tem seis estados, contra os 14 da máquina de Thompson.

Na definição, as duas contas da simulação têm os nomes do módulo da construção de Thompson. A dos corredores é o fecho vazio, E(S): os estados que se alcançam a partir dos de S por zero ou mais transições vazias. A das catracas é \text{mover}(S, a): os destinos das transições que leem o símbolo a e saem dos estados de S.

NotaDefinição — Construção de subconjuntos

Seja N = (Q, \Sigma, \Delta, q_0, F) um autômato finito não determinístico com transições vazias. A construção de subconjuntos produz o autômato finito determinístico D = (Q', \Sigma, \delta', q_0', F') definido por: q_0' = E(\{q_0\}); \delta'(S, a) = E(\text{mover}(S, a)) para S \in Q' e a \in \Sigma; F' = \{\, S \in Q' : S \cap F \neq \emptyset \,\}; e Q' é o menor conjunto de subconjuntos de Q que contém q_0' e é fechado por \delta' — obtido, na prática, expandindo apenas os subconjuntos alcançáveis a partir de q_0', nunca todo \mathcal{P}(Q).

• N é a máquina não determinística: Q são os estados, \Delta (delta maiúsculo) reúne as setas, q_0 é o inicial e F, o conjunto dos estados de aceitação. Na máquina de Thompson de (a|b)*abb, q_0 é o 6, e F = \{13\}.
• D é a máquina nova. O sinal ', lido “linha”, marca o que é dela, e \delta' é a tabela de transição. q_0' = E(\{6\}) = \{0, 2, 4, 6, 7, 8\} é o passo 1. \delta'(S, a) é o passo 2, para cada conjunto S do catálogo e cada símbolo a: \delta'(1, b) é o conjunto 3. F' reúne os conjuntos que têm algum estado de F, aqui só o 4.
• “Fechado por \delta'” quer dizer que nenhuma transição leva para fora de Q', e “o menor”, que não entra conjunto além dos alcançados a partir de q_0': é o catálogo quando os pendentes acabam. \mathcal{P}(Q) reúne todos os subconjuntos de Q: para os 14 estados de (a|b)*abb, são 2^{14} = 16.384, e a construção chegou a cinco.

Na tabela nova, abb custa três consultas, do 0 ao 1, ao 3 e ao 4, onde a simulação montou conjuntos de 9, 9 e 8 estados.

O programa de exemplo do projeto de referência imprime os cinco conjuntos com esses números. No projeto, o conjunto tirado dos pendentes é sempre o último que entrou, e o 2 sai antes do 1. Refaça o quadro nessa ordem: os números não mudam, porque o 3 só aparece quando o 1 é tirado, e o 4, quando o 3 é tirado.

1.1.1 O catálogo reconhece conjuntos, e não listas

Os pendentes acabam porque os conjuntos acabam. Todo conjunto do catálogo é um subconjunto de Q, e Q é finito: com |Q| estados há no máximo 2^{|Q|} subconjuntos. Cada um entra nos pendentes uma vez só, quando recebe número, e por isso o passo 2 se repete no máximo 2^{|Q|} vezes.

O argumento supõe que o catálogo reconhece um conjunto que já viu. Mas um programa que guarda o conjunto numa lista guarda também uma ordem: no módulo da construção de Thompson, o fecho vazio de \{6\} saiu como 6, 4, 7, 8, 0, 2. Para uma consulta que compara o primeiro elemento com o primeiro, o segundo com o segundo e assim por diante, 4, 0, 2 e 0, 2, 4 são listas diferentes. Se o catálogo comparar assim, o conjunto \{0, 2, 4\} que chegar como 4, 0, 2 não será encontrado e receberá número novo.

O catálogo passa então a guardar listas, e o mesmo conjunto recebe um número para cada ordem em que chegar. Três elementos podem vir em seis ordens: 0, 2, 4, 0, 4, 2, 2, 0, 4, 2, 4, 0, 4, 0, 2 e 4, 2, 0. São três escolhas para o primeiro lugar, duas para o segundo e uma para o terceiro: 3 \times 2 \times 1 = 6. Com dez elementos, são 10 \times 9 \times 8 \times \cdots \times 1 = 3.628.800 ordens, e o teto de 2^{|Q|} dá lugar ao número de listas.

A construção ainda termina, porque as listas possíveis também são em número finito. A máquina continua aceitando as cadeias certas, porque as cópias de um conjunto levam aos mesmos conjuntos e se comportam igual. Por isso nenhum teste feito com cadeias acusa o defeito: ele aparece na contagem de estados. A máquina fica com dois estados para o mesmo subconjunto, o que a definição não admite, porque Q' é um conjunto de subconjuntos, e \{0, 2, 4\} e \{4, 0, 2\} são o mesmo subconjunto. A minimização junta as cópias de volta, e a máquina final não guarda sinal delas.

O conserto é pôr a lista em ordem crescente antes de consultar o catálogo. A lista ordenada passa a ser a chave, o que o catálogo usa para procurar: 4, 0, 2 e 0, 2, 4 viram as duas 0, 2, 4. A lista com um estado repetido, 0, 2, 2, 4, continua diferente de 0, 2, 4, e por isso se tiram as repetições depois de ordenar. As duas operações juntas fazem de uma lista a chave de um conjunto. Quem aprendeu que uma lista ordenada se consulta mais depressa pode ler a ordenação da chave como ganho de velocidade, mas ela serve para o programa tratar como iguais dois conjuntos iguais.

Implementação

No projeto de referência, a construção de subconjuntos é a função determinizar. O começo dela declara três estruturas e faz o passo 1:

05_determinizacao.cpp

// Cada estado do AFD é um subconjunto de estados do AFN. O mapa liga cada
// subconjunto já visto ao seu índice; reencontrá-lo não cria estado, e a
// construção termina porque os subconjuntos distintos são finitos, ainda
// que muitos.
std::map<std::vector<Estado>, Estado> indiceDoSubconjunto;
std::vector<std::vector<Estado>> subconjuntos;
std::vector<std::vector<Estado>> pendentes;

std::vector<Estado> inicialDoAfn = afn.fechoVazio({afn.inicial()});
std::sort(inicialDoAfn.begin(), inicialDoAfn.end());
indiceDoSubconjunto[inicialDoAfn] = 0;
subconjuntos.push_back(inicialDoAfn);
pendentes.push_back(inicialDoAfn);

indiceDoSubconjunto é o catálogo: um std::map, que procura pela chave comparando elemento por elemento, na ordem, e devolve o número do conjunto. No comentário, ele é o “mapa”, o conjunto “já visto” é o que já está no catálogo, e o “índice” é o número. AFN e AFD, nos comentários, são o autômato finito não determinístico e o determinístico. A lista subconjuntos guarda os conjuntos na ordem dos números, e inicialDoAfn é o fecho vazio do estado inicial. O std::sort vem antes de o conjunto receber o número 0. O trecho ordena e não tira repetições. Não há o que tirar: fechoVazio anota os estados já visitados e não devolve nenhum duas vezes.

Uma versão sem a ordenação, medida nos quatro padrões da tabela de Seção 1.5, dá as mesmas contagens. Nesses padrões, fechoVazio percorre as transições vazias sempre na mesma sequência, e cada conjunto chega sempre escrito do mesmo jeito. Sem a ordenação, o programa acerta por coincidência, e uma cópia apareceria no primeiro conjunto que chegasse por dois caminhos em ordens diferentes. Com a ordenação, ele acerta porque a chave representa um conjunto.

A peça que faltava entre as duas metades da Peneira

A Peneira é o sistema que o projeto de referência constrói: uma linguagem pequena em que se escrevem padrões, e o compilador dela. Esse compilador tem até aqui duas partes que não se falam. A parte nfa, sigla em inglês de autômato finito não determinístico, recebe a árvore de um padrão, devolve a máquina da construção de Thompson e sabe executá-la carregando um conjunto de estados. O executor de autômatos determinísticos faz uma consulta de tabela por símbolo para responder se uma cadeia é aceita, e ainda não recebeu nenhuma máquina nascida de um padrão.

A parte que entra neste módulo se chama dfa, sigla em inglês de autômato finito determinístico. Ela faz duas coisas: troca a máquina que a nfa devolve por uma máquina determinística e depois junta os estados dessa máquina que se comportam igual. Com ela, um padrão escrito por quem usa a Peneira vai do texto até uma tabela que o executor sabe rodar, sem que ninguém escreva a tabela à mão.

A dfa é a parte mais reaproveitada de todo o sistema. Ela serve a dois usos: reconhecer as unidades com que se escreve um programa na própria Peneira e transformar em máquina os padrões declarados por quem usa a Peneira. Um defeito deixado na dfa aparece duas vezes: nos dois usos, que parecem não ter relação um com o outro.

1.2 O que a definição deixa ao programa: o conjunto vazio e o alfabeto

A máquina de ab, do módulo da construção de Thompson, tem quatro estados: do 0, lendo a, vai-se ao 1; do 1, por um corredor, ao 2; do 2, lendo b, ao 3, o de aceitação. Com o alfabeto de a e b, a construção de subconjuntos dá:

Conjunto	Lendo a	Lendo b
→ 0, que é \{0\}	\{1, 2\}, que é novo: 1	\emptyset
1, que é \{1, 2\}	\emptyset	\{3\}, que é novo: 2
2, que é \{3\}	\emptyset	\emptyset

Em quatro das seis células, nenhum estado do conjunto tem transição que leia o símbolo, e o resultado é o conjunto vazio, \emptyset, um subconjunto de Q como os outros. A definição não impede que ele entre no catálogo. Se entrar, será um estado de onde não se sai, porque sem estado nenhum não há transição nenhuma, e do conjunto vazio, com qualquer símbolo, só se chega ao conjunto vazio. E será um estado que não aceita, porque não contém estado de F. Um estado assim já tem nome no módulo dos autômatos determinísticos: o estado de onde todas as setas voltam para ele mesmo é absorvente, e o absorvente que não é de aceitação é o estado de erro. A definição do autômato determinístico não menciona o estado de erro, mas exige uma seta para cada estado e cada símbolo, e com isso obriga o programa a ter para onde mandar o símbolo que não serve.

Há então dois jeitos de montar a máquina. Num, o conjunto vazio recebe número e vira mais um estado. No outro, as células que dariam o conjunto vazio apontam para o estado de erro que a máquina determinística já tem. A definição da construção de subconjuntos admite os dois, e a escolha é de quem escreve o programa. Pelo segundo, a determinizada de ab tem os três conjuntos e o estado de erro: quatro estados.

Implementação

O projeto de referência segue o segundo jeito, no trecho que se repete para cada símbolo do alfabeto:

05_determinizacao.cpp

if (proximo.empty()) {
    // Conjunto vazio: é o estado de erro, que o construtor do Afd
    // já cria. A posição fica sem destino e continua apontando
    // para ele na tabela final.
    continue;
}

Quando o conjunto recém-calculado, proximo, está vazio, o continue passa ao símbolo seguinte sem consultar o catálogo nem anotar transição. No comentário, Afd é o autômato determinístico, o “construtor” é o que cria um Afd já com o estado de erro e com toda célula apontando para esse estado, e a “posição” é a célula. Com o conjunto vazio como estado novo, a máquina teria dois estados com o comportamento do erro, e a contagem traria uma cópia que a minimização depois juntaria.

1.2.1 Uma coluna para cada símbolo escrito

O passo 2 diz “para cada símbolo do alfabeto”, e a tabela da máquina nova tem uma coluna para cada um. Na definição, o alfabeto \Sigma vem junto com a máquina; num programa, alguém tem de calculá-lo. Na máquina de Thompson de -?[0-9]+, as transições que leem símbolo levam escritos o sinal de menos e os dez dígitos: 11 símbolos. A determinizada desse padrão tem 23 estados, pela conta de Seção 1.4, e a tabela dela tem 23 \times 11 = 253 células. Um caractere, do jeito que o computador o guarda, pode ter 256 valores. Com o alfabeto de todos os 256, a tabela teria 23 \times 256 = 5.888 células, e 245 das 256 colunas só repetiriam o estado de erro.

O padrão a.c pede um a, um símbolo qualquer e um c. A máquina de Thompson dele tem seis estados e cinco setas em fila: do 0 ao 1, a catraca do a; do 1 ao 2, um corredor; do 2 ao 3, a seta do coringa; do 3 ao 4, outro corredor; do 4 ao 5, a catraca do c. A seta do coringa não leva símbolo escrito, e sim uma marca própria, que a definição dos casos base, no módulo da construção de Thompson, manda ler como “qualquer símbolo de \Sigma”.

NotaDefinição — Alfabeto fechado da determinização

O alfabeto \Sigma usado na construção de subconjuntos é o conjunto dos símbolos concretos que rotulam alguma transição de N, em qualquer ordem fixa — nem o símbolo vazio \varepsilon nem a marca de coringa entram nele diretamente. Uma transição de coringa em N passa a corresponder, na construção de subconjuntos, a uma transição por cada símbolo de \Sigma: o coringa deixa de ser um símbolo à parte e se torna uma abreviação decidida no momento em que \Sigma é fechado.

O rótulo de uma transição é o que a seta leva escrito. Os símbolos concretos que rotulam alguma transição são os que aparecem escritos em alguma delas: a e c em a.c, o sinal de menos e os dez dígitos em -?[0-9]+. O alfabeto “é fechado” quando a lista fica completa e para de mudar, antes de a construção começar, e daí o nome alfabeto fechado. Esse fechado não tem relação com o fecho, que repete, nem com o fecho vazio, nem com o “fechado por \delta'” da construção de subconjuntos. Dois rótulos ficam fora de \Sigma. O \varepsilon é o rótulo das transições vazias, que não leem nada e que o fecho vazio já percorre. A marca do coringa fica de fora porque a entrada, o texto que a máquina recebe para ler, não traz um caractere “qualquer”: traz um caractere determinado, como a ou c.

Sobre o alfabeto fechado, a construção de subconjuntos de a.c dá:

Conjunto	Lendo a	Lendo c
→ 0, que é \{0\}	\{1, 2\}, que é novo: 1	\emptyset
1, que é \{1, 2\}	\{3, 4\}, que é novo: 2	\{3, 4\} outra vez: 2
2, que é \{3, 4\}	\emptyset	\{5\}, que é novo: 3
3, que é \{5\}	\emptyset	\emptyset

Na linha do conjunto 1, a seta do coringa, que sai do estado 2, foi usada duas vezes, na coluna do a e na do c: é a “transição por cada símbolo de \Sigma” da definição. A máquina nova tem quatro conjuntos e o estado de erro, cinco estados, e aceita duas cadeias, aac e acc.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    C0("0, inicial<br/>{0}") -->|a| C1("1<br/>{1,2}")
    C1 -->|a| C2("2<br/>{3,4}")
    C1 -->|c| C2
    C2 -->|c| C3["3, de aceitação<br/>{5}"]

Figura 2: A máquina determinizada de a.c, sem o estado de erro: as duas setas do conjunto 1 ao conjunto 2 são as duas células que a seta do coringa preencheu.

No desenho, como no de (a|b)*abb, o estado de erro não aparece, e cada seta vale por uma transição: as duas setas do conjunto 1 ao 2 são as duas células que a seta do coringa da máquina de Thompson preencheu.

A ordem dos símbolos em \Sigma pode ser qualquer uma, mas tem de ser a mesma em todo lugar em que a tabela é usada, porque a coluna de um símbolo é o lugar dele na lista. Monte a tabela de a.c com a ordem a, c e consulte-a com a ordem c, a: do estado 0, o a cai na coluna do c, que leva ao erro, e aac é recusada.

O leitor de padrões guardou o coringa num nó só, e a construção de Thompson lhe deu uma seta só. Trocá-lo por alternâncias daria quase uma centena de folhas por ocorrência, uma para cada caractere que a tela do computador mostra. Com 100 folhas, a tabela de custos daria 2 \times 100 = 200 estados das folhas e 2 \times 99 = 198 das alternâncias, perto de 400 por coringa, contra os dois da folha de coringa. Na determinização, o coringa se desfaz sem estado nenhum a mais: a cada seta examinada, a construção pergunta se o rótulo dela é o símbolo da coluna ou a marca do coringa.

A cadeia abc tem um símbolo de fora do alfabeto fechado de a.c, e a tabela não tem coluna para o b. O programa que executa a tabela traduz cada caractere da entrada no número da coluna dele, como no módulo dos autômatos determinísticos, e responde com o estado de erro quando o caractere não tem coluna: abc é recusada. Para o coringa valer também pelo b, a máquina tem de ser construída sobre um alfabeto que contenha o b.

Implementação

No projeto de referência, quem faz as duas contas do passo 2 é a função avancar:

05_determinizacao.cpp

std::vector<Estado> avancar(const Afn& afn, const std::vector<Estado>& conjunto,
                            const char simbolo) {
    std::vector<Estado> alcancados;
    for (const Estado estado : conjunto) {
        for (const TransicaoAfn& transicao : afn.transicoesDe(estado)) {
            // O coringa casa qualquer símbolo do alfabeto recebido. Expandido
            // aqui, ele não acrescenta coluna nem estado; na árvore, seriam
            // quase cem folhas por ocorrência.
            const bool casa = transicao.simbolo == simbolo || transicao.simbolo == kQualquer;
            if (casa) {
                alcancados.push_back(transicao.destino);
            }
        }
    }
    std::vector<Estado> resultado = afn.fechoVazio(alcancados);
    std::sort(resultado.begin(), resultado.end());
    resultado.erase(std::unique(resultado.begin(), resultado.end()), resultado.end());
    return resultado;
}

A linha de casa é o \text{mover}, com o coringa incluído. O nome vem do verbo casar, e não da casa do tabuleiro: a transição casa com o símbolo, isto é, serve a ele, quando o rótulo dela é o símbolo pedido ou é kQualquer, a marca do coringa. A partir dos destinos, fechoVazio segue as transições vazias: primeiro \text{mover}, depois E, na ordem da definição. O módulo da construção de Thompson mostrou, com a* e a cadeia a, o que a ordem invertida deixa de fora: os estados que só se alcançam por transição vazia depois da última leitura. As duas linhas antes do return fazem a chave: std::sort ordena, e o par std::unique e erase tira as repetições, que depois da ordenação ficam lado a lado. Aqui não há nenhuma; se fechoVazio devolvesse alguma, o par a tiraria, e a chave ficaria certa. A construção chama avancar uma vez para cada símbolo do alfabeto que recebeu, e o programa de exemplo entrega o alfabeto fechado: assim a seta do coringa de a.c serve à coluna do a e à do c.

A simulação do módulo da construção de Thompson não usa alfabeto: nela, a seta do coringa serve a qualquer caractere, e a máquina de Thompson de a.c aceita abc. O arquivo de casos daquele módulo traz esse caso, com aceita como veredito, a resposta esperada. As duas máquinas do projeto respondem diferente a essa cadeia, e a diferença está no alfabeto entregue à determinização, e não na construção. Essa diferença não desmente o teorema de Seção 1.3, que prova que as duas máquinas aceitam as mesmas cadeias sobre o alfabeto fechado: abc não é cadeia sobre a e c.

Depois da determinização, a máquina não guarda qual célula veio de um coringa. O padrão aac|acc, sem coringa, descreve as duas cadeias que a determinizada de a.c aceita, mas a máquina de Thompson dele tem 14 estados, e a determinizada, sete, contra seis e cinco em a.c. As duas determinizadas são diferentes, e Seção 1.5 mostra que a minimização tira das duas a mesma máquina.

1.3 O que a construção garante, e o que ela não promete

O módulo dos autômatos determinísticos contou que Stephen Kleene mostrou que as linguagens descritas por expressão são exatamente as reconhecidas por máquina de estados finitos, e que a tradução existe nos dois sentidos. Duas construções fazem o sentido que vai da expressão à máquina: a de Thompson, no módulo dela, e a de subconjuntos, neste. O outro sentido fica de fora dos dois módulos. Falta garantir que a construção de subconjuntos não muda a linguagem: das cadeias sobre o alfabeto fechado, a determinizada tem de aceitar exatamente as que a de Thompson aceita.

«As duas máquinas fazem a mesma coisa, cada uma do seu jeito.» Essa analogia parece uma explicação, mas não diz por que uma cadeia aceita por uma seria aceita pela outra. Uma lista de cadeias em que as duas concordam também não garante. A lista diz o que acontece com as cadeias que estão nela, e as cadeias sobre o alfabeto são infinitas. Ponha as duas máquinas de (a|b)*abb lado a lado enquanto leem abb:

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    P0("lido: nada<br/>conjunto ativo {0,2,4,6,7,8}<br/>estado 0 da determinizada") -->|a| P1("lido: a<br/>conjunto ativo {0,1,2,4,5,7,8,9,10}<br/>estado 1 da determinizada")
    P1 -->|b| P2("lido: ab<br/>conjunto ativo {0,2,3,4,5,7,8,11,12}<br/>estado 3 da determinizada")
    P2 -->|b| P3("lido: abb<br/>conjunto ativo {0,2,3,4,5,7,8,13}<br/>estado 4 da determinizada, de aceitação")

Figura 3: As duas máquinas de (a|b)*abb lendo abb: depois de cada começo da cadeia, o estado da determinizada é o número que o catálogo deu ao conjunto ativo da máquina de Thompson.

Cada caixa traz o que já foi lido, o conjunto ativo da máquina de Thompson e o estado da determinizada, que é o número que o catálogo deu a esse conjunto. Os começos de abb, do vazio até a cadeia inteira, são os prefixos dela. Se a correspondência vale depois de cada prefixo, vale depois do último, e as duas máquinas dão a mesma resposta. O teorema a seguir diz isso para toda máquina e para toda cadeia sobre o alfabeto dela.

ImportanteTeorema — Equivalência entre autômato não determinístico e determinístico por construção

Para todo autômato finito não determinístico com transições vazias N, o autômato determinístico D obtido pela construção de subconjuntos satisfaz L(D) = L(N). A prova segue por indução no comprimento do prefixo consumido: após ler um prefixo qualquer da entrada, o estado em que D se encontra é exatamente o conjunto de estados em que N poderia estar — vale para o prefixo vazio, porque q_0' = E(\{q_0\}), e se vale para um prefixo, vale para ele mais um símbolo, porque é assim que \delta' é definida. A cadeia inteira é o caso particular em que o prefixo é a cadeia toda, e D aceita exatamente quando algum estado de F pertence ao conjunto — que é o critério de F'.

• L(D) é a linguagem reconhecida por D, o conjunto das cadeias que D aceita, e L(N), a de N; a igualdade é a equivalência do título. As cadeias são as do alfabeto fechado, o mesmo nas duas máquinas, e em N o coringa vale por um símbolo de \Sigma. Sobre abc, que tem um símbolo de fora do \Sigma de a.c, o teorema não diz nada.
• A afirmação provada é a das caixas do desenho, e vamos chamá-la de invariante, uma afirmação que vale do começo ao fim da leitura. A prova é em duas partes: no prefixo vazio, q_0' é o conjunto de partida da simulação; e cada símbolo a mais leva D pela mesma conta com que a simulação passa de um conjunto ativo ao seguinte. No fim, o critério de F' é o da simulação: algum estado de F no último conjunto.

O argumento não cita cadeia, padrão nem comprimento, e por isso vale para todos. Ele garante a construção como a definição a descreve, mas nada diz de um programa que a tenha copiado com erro, e é para conferir a cópia que a lista de cadeias volta. Três erros de cópia, pontos em que o código não faz o que o algoritmo manda, mudam a resposta de alguma cadeia, em algum padrão:

• esquecer o fecho vazio do estado inicial e começar de \{q_0\};
• inverter a ordem do passo 2, com o fecho vazio antes de \text{mover};
• não usar a seta do coringa para todos os símbolos de \Sigma.

«Se as duas máquinas concordam em todas as cadeias até um comprimento grande, isso não resolve?» Escolhido a olho, o comprimento não resolve: o erro que sobra depois do teste é o que só aparece numa cadeia mais longa que as testadas. Mas, para duas máquinas determinísticas sobre o mesmo alfabeto, as próprias máquinas fixam um comprimento: some os números de estados das duas, contado o de erro, e tire 2. Se elas concordam em todas as cadeias até esse comprimento, concordam em todas as outras; o porquê vem em Seção 1.4.2. Para uma máquina de seis estados e outra de cinco, o comprimento é 6 + 5 - 2 = 9, e uma lista que chegue até ele prova que aquele par aceita as mesmas cadeias, só aquele par, e depois de construído. A regra não serve, como está, ao par da pergunta, a máquina de Thompson e a determinizada, porque pede duas máquinas determinísticas. O que garante a construção para todo padrão continua sendo o teorema.

O invariante também serve para achar um erro de cópia, porque se confere em qualquer ponto da construção. Escolha um conjunto que já tem número e uma cadeia que leve a determinizada até ele, e passe essa cadeia pela simulação: o conjunto ativo no fim tem de ser o próprio conjunto. Se não for, você tem na mão um ponto em que a construção se afastou da definição. Uma cadeia aceita por uma máquina e recusada pela outra diz menos: mostra que elas se afastaram em algum ponto antes do fim, sem dizer qual.

Com o teorema, as duas espécies de máquina, a determinística e a não determinística, reconhecem exatamente as mesmas linguagens. Num sentido, a determinística já é um caso particular da não determinística, como o módulo da construção de Thompson mostrou; no outro, a construção de subconjuntos dá, para cada não determinística, uma determinística que aceita as mesmas cadeias. O não determinismo facilita a montagem, porque a máquina de Thompson sai de regras fixas, uma por tipo de nó. Essa máquina só existe enquanto o padrão é transformado em tabela, e quem usa a tabela pronta faz uma consulta por símbolo sem precisar saber que houve uma máquina de Thompson. É o caso da análise léxica, a parte do compilador que separa o texto de um programa em unidades. E o que se conclui sobre a linguagem de uma espécie vale para a da outra, o que deixa usar a mais cômoda em cada raciocínio.

1.3.1 A linguagem que obriga a crescer

O único teto que a construção de subconjuntos dá para a determinizada é o dos 2^{|Q|} subconjuntos de Q. Os padrões vistos até aqui ficaram longe dele: (a|b)*abb foi de 14 estados para seis, e -?[0-9]+, de 84 para 23. Um subconjunto só entra no catálogo quando alguma cadeia deixa a máquina de Thompson exatamente naquela combinação de estados, e nesses padrões poucas combinações acontecem. O teto leva a esperar uma máquina sempre maior que a de origem, mas o teorema fala da linguagem aceita, e não do número de estados. A construção não promete aumentar nem diminuir a máquina.

Tome, sobre a e b, as cadeias em que o n-ésimo símbolo contado do fim é um a. Com n = 3, aabb pertence a essa linguagem, porque o terceiro símbolo do fim é a, e abab não, porque o terceiro do fim é b. O padrão é (a|b)*a seguido de n - 1 cópias de (a|b); para n = 3, (a|b)*a(a|b)(a|b). Na máquina de Thompson, a cada a lido, um peão a mais passa pela catraca do a que vem depois do fecho e entra na fila das cópias de (a|b), onde atravessa uma cópia por símbolo lido. Os peões da fila marcam, juntos, quais dos últimos símbolos foram a. A máquina determinística tem um peão só, e a cadeia pode acabar depois de qualquer símbolo: a casa em que ele está precisa guardar quais dos últimos n símbolos foram a.

Esse “precisa” vira contagem com a ferramenta do módulo dos autômatos determinísticos. Dois prefixos são distinguíveis quando alguma continuação, a testemunha, põe exatamente um deles na linguagem. Se há k prefixos distinguíveis dois a dois, toda máquina determinística da linguagem tem pelo menos k estados, e esse número k é o piso. Para n = 2, os quatro prefixos de comprimento 2 formam seis pares:

Par de prefixos	Testemunha	As duas cadeias	Qual pertence à linguagem
aa e ab	a	aaa e aba	só a primeira
ba e bb	a	baa e bba	só a primeira
os outros quatro pares: um de aa e ab com um de ba e bb	\varepsilon	os próprios prefixos	só aa ou ab

Os quatro são distinguíveis dois a dois, e toda máquina determinística dessa linguagem tem pelo menos quatro estados. Para um n qualquer, tome as 2^n cadeias de comprimento n, porque cada um dos n símbolos é a ou b. Duas delas diferem em algum lugar, digamos o i-ésimo símbolo contado do começo, onde uma tem a e a outra tem b. Cole nas duas uma continuação de i - 1 símbolos quaisquer: o i-ésimo símbolo do começo vira o n-ésimo do fim, e só uma das duas pertence à linguagem. Com n = 3, aab e abb diferem no segundo símbolo, e a continuação a dá aaba, que pertence, e abba, que não. As 2^n cadeias são distinguíveis duas a duas, e o piso é 2^n.

Antes de olhar as medidas. Quanto vale o piso quando se conta o terceiro símbolo do fim? E quando se conta o quarto?

NotaConfira

Oito e dezesseis: 2^3 = 8 e 2^4 = 16, as cadeias de três e de quatro símbolos, distinguíveis duas a duas.

O projeto de referência monta esse padrão para n de 1 a 8 e conta os estados das três máquinas. A coluna “Reduzido” é a da máquina reduzida, a que sai da minimização (Seção 1.5); por enquanto, leia-a como um número medido.

n	Thompson	Determinizado	Reduzido
1	10	4	3
2	16	6	5
3	22	10	9
4	28	18	17
5	34	34	33
6	40	66	65
7	46	130	129
8	52	258	257

Coluna	Fórmula	De onde ela vem
Thompson	6n + 4	pela tabela de custos, (a|b)*a dá 10 estados, e cada (a|b) a mais dá 6: duas folhas e uma alternância
Determinizado	2^n + 2	o piso e mais dois estados
Reduzido	2^n + 1	o piso e mais um estado

O estado que a reduzida tem acima do piso é o de erro, que o projeto cria sempre e a que aqui nenhuma seta leva. Todo conjunto contém dois estados do trecho de (a|b)*, um com a transição que lê a e outro com a que lê b, e por isso nenhuma conta dá o conjunto vazio. A determinizada tem mais um acima do piso. O conjunto inicial e o conjunto a que se chega lendo um b são diferentes, porque só o primeiro contém o estado inicial da máquina de Thompson, a que nenhuma seta chega. Mas os dois se comportam igual, e a minimização os junta, como junta os conjuntos 0 e 2 de (a|b)*abb em Seção 1.4.1.

Em n = 5, as colunas “Thompson” e “Determinizado” empatam em 34. Antes dessa linha, determinizar diminui o número de estados; depois dela, aumenta. Esse crescimento da máquina determinizada tem nome: explosão de estados.

Suponha que você transformou um padrão em máquina e a determinizada saiu com milhares de estados. Há duas explicações, e elas pedem providências opostas: ou o programa está criando estados que não precisariam existir, ou a linguagem descrita exige aquele número. A coluna “Reduzido” separa as duas. Se o crescimento fosse desperdício do algoritmo de construção de subconjuntos, a minimização desfaria esse crescimento. Em n = 8, ela tira um estado de 258. Os 256 do piso continuam lá, nenhuma máquina determinística reconhece essa linguagem com menos, e a providência é rever o padrão, e não o programa.

ImportanteDe quem é o crescimento?

Diante de uma máquina determinizada que ficou grande, rode a minimização e compare o número de estados dela com o da reduzida.

1. Os dois números ficam próximos, como 258 e 257. O crescimento é da linguagem, e nenhum programa o evita.
2. O da reduzida fica várias vezes menor, como 4 contra 23. A determinizada tem estados que se comportam igual. Uma parte deles vem da construção de Thompson e é esperada: são as cópias que a minimização junta quando leva -?[0-9]+ de 23 estados a 4. Outra parte pode ser defeito do programa, e os suspeitos são a chave sem ordenação e o coringa trocado por folhas na árvore.
3. Os dois números, sozinhos, não separam as duas partes do caso 2. Só a conferência dos dois suspeitos diz se há defeito.

O critério depende de o programa informar os dois números a cada padrão convertido em máquina, e não só quando alguém pede. A linguagem desta seção foi montada para exigir a lembrança dos últimos n símbolos. Um padrão como -?[0-9]+ pede outra coisa: saber em qual dos três pontos do formato a leitura está, antes de tudo, depois do sinal ou depois de algum dígito.

1.4 Estados que nenhuma continuação separa

A determinizada de -?[0-9]+ tem 23 estados: o de erro e 22 conjuntos de estados da máquina de Thompson.

A cadeia lida até aqui é	Conjuntos	Quais
nada	1	o conjunto de partida
só o sinal de menos	1	o que espera o primeiro dígito
um dígito, com ou sem sinal antes	10	um para cada dígito lido
dois dígitos ou mais	10	um para cada último dígito lido

São 1 + 1 + 10 + 10 = 22 conjuntos. As duas últimas linhas têm dez cada porque, na árvore, cada dígito da faixa tem a sua folha: lido um dígito, o destino da transição da folha dele entra no conjunto seguinte. A terceira linha vem das folhas da faixa, e a quarta, das folhas da cópia que fica dentro do fecho.

Os vinte conjuntos das duas últimas linhas guardam qual foi o último dígito lido e se ele era o único, e nada disso importa à linguagem. De qualquer um deles, mais um dígito leva a um dos dez da última linha, o sinal de menos leva ao erro, e a cadeia que acabar ali é aceita: são vinte estados com um comportamento só. Os outros três têm cada um o seu: o conjunto de partida, o que espera o primeiro dígito e o estado de erro. São quatro comportamentos, o 4 da máquina reduzida. A construção de Thompson cria estados próprios para cada folha e não verifica se outra folha já faz o mesmo papel. A construção de subconjuntos herda essas cópias, porque junta num conjunto os estados ocupados ao mesmo tempo, e não os que se comportam igual.

Ponha um peão no estado a que se chega lendo 7 e outro no estado a que se chega lendo 42, e dê aos dois a mesma continuação. Com 5, os dois terminam em estados de aceitação; com -, os dois terminam no erro; com a cadeia vazia, os dois já estão em estados de aceitação. Nenhuma continuação leva um deles a aceitar e o outro a recusar. A definição diz isso com a função de transição estendida, do módulo dos autômatos determinísticos. Lá, \delta(q, a) é o estado a que a seta do símbolo a leva, saindo de q. E \hat\delta(p, w), lido “delta chapéu de p e w”, é o estado a que o peão chega saindo de p e lendo a cadeia w inteira.

NotaDefinição — Estados equivalentes (indistinguibilidade)

Dois estados p, q \in Q de um autômato finito determinístico (Q, \Sigma, \delta, q_0, F) são equivalentes (ou indistinguíveis) quando, para toda cadeia w \in \Sigma^*, \hat\delta(p, w) \in F se e somente se \hat\delta(q, w) \in F — em que \hat\delta estende \delta a cadeias da forma usual. Ou seja: nenhuma cadeia, por mais longa que seja, os separa quanto à aceitação.

Aqui p e q são dois estados quaisquer, e q não é o estado inicial, que continua sendo q_0. “Para toda cadeia w” quer dizer com qualquer continuação, inclusive a vazia. A condição diz que, lendo w, ou os dois peões chegam a estados de aceitação, ou nenhum chega. Até aqui, equivalentes eram duas máquinas, ou duas expressões, com a mesma linguagem; nesta definição, a palavra vale para dois estados de uma mesma máquina. No módulo dos autômatos determinísticos, os distinguíveis eram dois prefixos, medidos contra uma linguagem. Aqui são dois estados, e a testemunha é a cadeia que leva um deles à aceitação e o outro não: dois estados são equivalentes quando não têm testemunha. A definição olha só para o que vem depois, e não para a cadeia que levou a máquina a cada estado.

Como está, a definição não serve de procedimento, porque pede uma conferência para cada cadeia de \Sigma^*, e as cadeias são infinitas. O procedimento que chega à mesma resposta com um número finito de contas trabalha com grupos. Uma partição dos estados é uma divisão deles em grupos, com cada estado em exatamente um grupo, e cada grupo é um bloco. No módulo da construção de Thompson, bloco era um pedaço de máquina com um estado de entrada e um de saída; aqui, a palavra nomeia só o grupo de estados.

1.4.1 Uma rodada por símbolo

A continuação mais curta é a cadeia vazia: lendo nada, o peão fica onde está, \hat\delta(p, \varepsilon) = p. Se p é de aceitação e q não é, a cadeia vazia é testemunha, e por isso um estado de aceitação e um que não é nunca são equivalentes. Isso divide os estados em dois blocos, a partição inicial. Na determinizada de (a|b)*abb, com os seis estados, o bloco dos de aceitação é \{4\}, e o dos demais, \{0, 1, 2, 3, \text{erro}\}. Quando nenhum estado é de aceitação, ou quando todos são, a partição inicial tem um bloco só.

Dois estados em blocos diferentes estão separados, e continuarão. Dois no mesmo bloco ainda não foram separados, o que não quer dizer que sejam equivalentes, nem no bloco dos que não aceitam nem no dos que aceitam. O 1 e o 3 estão no mesmo bloco, e a cadeia b é testemunha: do 3, o b leva ao 4, de aceitação; do 1, leva ao 3. Numa máquina para a linguagem das três cadeias ab, abb e ba, os estados a que se chega lendo ab e lendo ba são ambos de aceitação. Um b a mais os separa: abb é aceita, e bab não.

Implementação

A função minimizar, do projeto de referência, começa pela partição inicial:

05_determinizacao.cpp

// Refinamento de partições. A partição inicial põe os estados de aceitação
// no bloco 1 e os demais no bloco 0: é a única diferença visível sem
// consumir símbolo. Dois estados no mesmo bloco ainda não foram
// distinguidos; cada rodada testa se algum símbolo os separa.
std::vector<std::size_t> bloco(total, 0);
std::size_t aceitantes = 0;
for (std::size_t estado = 0; estado < total; ++estado) {
    bloco[estado] = afd.ehDeAceitacao(estado) ? 1 : 0;
    aceitantes += bloco[estado];
}
// Conta só os blocos com estado dentro. Sem estado de aceitação, ou só com
// eles, a partição começa com um bloco: contar dois incluiria um vazio, e
// a contagem cairia de 2 para 1 na primeira rodada sem bloco algum se
// fundir.
std::size_t quantidadeDeBlocos = 2;
if (aceitantes == 0 || aceitantes == total) {
    quantidadeDeBlocos = 1;
    bloco.assign(total, 0);
}
resultado.blocosPorRodada.push_back(quantidadeDeBlocos);

A lista bloco guarda o bloco de cada um dos total estados, contado o de erro: o 1 para os de aceitação, contados em aceitantes, e o 0 para os demais. Como diz o segundo comentário, sem estado de aceitação, ou só com eles, a contagem começa em 1, e não em 2. blocosPorRodada recebe uma contagem por partição e serve, no fim, para conferir que o procedimento parou no ponto certo. No primeiro comentário, refinamento de partições é o nome do procedimento que começa aqui, rodada é cada cálculo de uma partição nova a partir da anterior, e consumir um símbolo é lê-lo.

Para separar mais, olhe um símbolo adiante. Se o símbolo b leva p e q a estados que já estão em blocos diferentes, então p e q também são distinguíveis: a testemunha é o b seguido da testemunha que separava os dois destinos. Foi assim que o b separou o 1 do 3, porque os destinos, 3 e 4, já estavam separados pela cadeia vazia. A pergunta sobre todas as cadeias vira uma pergunta sobre um símbolo e a partição que se tem, e ela se responde com uma consulta à tabela de transição.

Para cada estado, anote o bloco em que ele está e, para cada símbolo do alfabeto, o bloco do estado a que esse símbolo leva. A lista dessas anotações é a assinatura do estado, e cada lugar dela é um item. Na máquina de (a|b)*abb, chame de A o bloco \{0, 1, 2, 3, \text{erro}\} e de B o bloco \{4\}:

Estado	Bloco dele	Com a, vai ao	Com b, vai ao	Assinatura
0	A	1, que está em A	2, que está em A	A, A, A
1	A	1, em A	3, em A	A, A, A
2	A	1, em A	2, em A	A, A, A
3	A	1, em A	4, em B	A, A, B
erro	A	erro, em A	erro, em A	A, A, A
4	B	1, em A	2, em A	B, A, A

Estados com a mesma assinatura ficam no mesmo bloco da partição nova, e assinaturas diferentes separam: o estado 3 sai do bloco A, e a partição nova tem três blocos. Cada cálculo de uma partição nova a partir da anterior é uma rodada, e a partição inicial não conta como rodada. As rodadas seguintes, pelo mesmo método:

Partição	Blocos	Quantos	O que a rodada separou
inicial	\{0, 1, 2, 3, \text{erro}\}, \{4\}	2	—
depois da 1ª rodada	\{0, 1, 2, \text{erro}\}, \{3\}, \{4\}	3	o 3: o b dele leva ao 4
depois da 2ª	\{0, 2, \text{erro}\}, \{1\}, \{3\}, \{4\}	4	o 1: o b dele leva ao 3, já isolado
depois da 3ª	\{0, 2\}, \{\text{erro}\}, \{1\}, \{3\}, \{4\}	5	o erro: o a dele leva a ele mesmo, e o do 0 e do 2 leva ao 1
depois da 4ª	os mesmos cinco	5	nada

Refaça a terceira rodada com a tabela de transição ao lado; o estado de erro entra nas contas como os outros, mesmo sem seta que leve a ele.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
    R0("partição inicial<br/>{0,1,2,3,erro} {4}") -->|"b separa o 3"| R1("depois da 1ª rodada<br/>{0,1,2,erro} {3} {4}")
    R1 -->|"bb separa o 1"| R2("depois da 2ª rodada<br/>{0,2,erro} {1} {3} {4}")
    R2 -->|"abb separa o erro"| R3("depois da 3ª rodada<br/>{0,2} {erro} {1} {3} {4}")
    R3 -->|"nada se separa"| R4("depois da 4ª rodada<br/>os mesmos cinco blocos")

Figura 4: As partições da determinizada de (a|b)*abb, da inicial à que não muda mais, com a testemunha que cada rodada achou.

No desenho, as partições vêm uma abaixo da outra, e cada seta traz a testemunha da rodada. Cada rodada alcança testemunhas com um símbolo a mais: a partição inicial usou a cadeia vazia, e as rodadas seguintes, b, bb e abb. A cadeia abb separa o erro porque leva à aceitação a partir do 0 e do 2, e não a partir do erro. A última seta é a da rodada que não separa nada.

NotaDefinição — Refinamento de partições

O refinamento de partições calcula a indistinguibilidade por aproximações sucessivas. A partição inicial P_0 separa F de Q \setminus F. Dada uma partição P_i, a assinatura de um estado q sob P_i é a sequência formada pelo bloco de P_i que contém q seguido, para cada símbolo a \in \Sigma, do bloco de P_i que contém \delta(q, a). A partição P_{i+1} agrupa em um mesmo bloco exatamente os estados de P_i com a mesma assinatura sob P_i. O processo para na primeira rodada em que P_{i+1} = P_i.

O refinamento de partições é o procedimento das rodadas: cada partição nova divide blocos da anterior e chega mais perto da divisão que a definição de estados equivalentes pede. Em P_i, o número embaixo do P conta as rodadas feitas, e P_{i+1} é a partição seguinte. Q \setminus F são os estados que não são de aceitação, a “sequência” é a última coluna do quadro das assinaturas, e o processo para quando uma rodada devolve a partição que recebeu: no exemplo, na quarta.

O primeiro item da assinatura, o bloco do próprio estado, não pode faltar. Sem esse item, na primeira rodada, a assinatura do estado 4 seria A, A, a mesma dos estados 0, 1 e 2 e do erro, e um estado de aceitação voltaria ao bloco dos que não aceitam. Com o primeiro item, estados de blocos diferentes têm assinaturas diferentes, e uma rodada não junta o que outra separou.

Implementação

No projeto de referência, cada rodada começa assim:

05_determinizacao.cpp

// A assinatura de um estado é o bloco em que ele está e o bloco para
// onde cada símbolo o leva. Estados com a mesma assinatura ficam no
// mesmo bloco novo; assinaturas diferentes separam.
std::map<std::vector<std::size_t>, std::size_t> blocoDaAssinatura;
std::vector<std::size_t> novoBloco(total, 0);
std::size_t novosBlocos = 0;

for (std::size_t estado = 0; estado < total; ++estado) {
    std::vector<std::size_t> assinatura;
    assinatura.push_back(bloco[estado]);
    for (const char simbolo : alfabeto) {
        assinatura.push_back(bloco[afd.transicao(estado, simbolo)]);
    }

blocoDaAssinatura é um std::map cuja chave é a assinatura, uma lista de números de bloco, e cujo valor é o número do bloco novo: é o recurso do catálogo, com outra chave. Dentro do for, o primeiro push_back põe na assinatura o bloco do próprio estado, e o for de dentro acrescenta o bloco do destino de cada símbolo do alfabeto. As linhas seguintes da função procuram a assinatura em blocoDaAssinatura e dão ao estado, em novoBloco, o bloco de uma assinatura igual ou, se não houver, um bloco novo.

1.4.2 Parar quando a partição não muda

A quarta rodada devolveu os cinco blocos da terceira. As três primeiras acharam o que separar, mas nenhuma delas dizia se ainda sobrava alguma coisa. A quarta mostra que não sobra: uma quinta, com a mesma partição, faria as mesmas contas e chegaria ao mesmo resultado.

ImportanteTeorema — Correção do refinamento de partições

A sequência P_0, P_1, P_2, \ldots do refinamento de partições é monótona — todo bloco de P_{i+1} está contido em algum bloco de P_i — e por isso o número de blocos nunca decresce; como ele é limitado por |Q|, existe k tal que P_{k+1} = P_k. Nesse ponto fixo, dois estados estão no mesmo bloco de P_k se e somente se são equivalentes segundo a definição de indistinguibilidade.

“Monótona” quer dizer que cada bloco novo é um pedaço de um bloco antigo: os blocos se dividem e não se juntam, por causa do primeiro item da assinatura. “Limitado por |Q|”: cada bloco tem pelo menos um estado, e não pode haver mais blocos do que estados. No exemplo, |Q| = 6, e as contagens foram 2, 3, 4, 5 e 5. Aqui a letra k conta rodadas, e não prefixos, e no exemplo k = 3. Uma conta repetida até o resultado parar de mudar chega a um ponto fixo, e P_k é o ponto fixo.

O teorema traz duas garantias. A primeira é que o procedimento para: alguma das |Q| primeiras rodadas não separa ninguém. A segunda é que o resultado é o da definição de estados equivalentes, e essa garantia tem dois lados. Estados em blocos diferentes são distinguíveis: cada separação veio de um símbolo que levava a blocos já separados, e, voltando de separação em separação até a partição inicial, monta-se a testemunha, como abb para o erro e o 0. Estados no mesmo bloco do ponto fixo são equivalentes: ali, cada símbolo leva os dois ao mesmo bloco, o símbolo seguinte também, e assim até o fim de qualquer cadeia. No fim, os dois estão no mesmo bloco, e nenhum bloco mistura estado de aceitação com estado que não é.

Daí sai o porquê da regra da soma dos estados menos 2, de Seção 1.3. Ponha numa tabela só as linhas de duas máquinas determinísticas sobre o mesmo alfabeto, uma de seis estados e outra de cinco. O refinamento não usa o estado inicial e serve a essa tabela de 11 estados. A contagem começa em 2 (com um bloco só, nenhuma rodada separa), aumenta a cada rodada que separa e não passa de 11: no máximo 11 - 2 = 9 rodadas separam. Como cada rodada alcança testemunhas com um símbolo a mais, nenhuma testemunha achada passa de nove símbolos. Uma cadeia que uma máquina aceita e a outra recusa é testemunha dos dois estados iniciais. Se as máquinas concordam em todas as cadeias de até nove símbolos, esses dois estados chegam ao ponto fixo no mesmo bloco: são equivalentes, e as máquinas concordam em todas as cadeias.

«Sei quantos blocos têm de sair. Posso parar quando a contagem chegar a esse número?» Dá certo num caso só: quando o número esperado é o do ponto fixo. Mas esse número só se conhece rodando o refinamento até o fim, e com outro número a parada pela contagem e a parada pelo ponto fixo se separam. Em (a|b)*abb, com a máquina montada da partição em que o refinamento parou, um estado para cada bloco, como em Seção 1.5:

Número esperado	Contagens até parar	O que sai
2 ou 3	2, ou 2 e 3	o estado inicial fica no bloco do erro, de onde nenhuma seta sai para outro bloco, e a máquina não aceita cadeia nenhuma
4	2, 3 e 4	uma máquina de quatro estados que aceita as cadeias certas, com o estado inicial no lugar do estado de erro
5	2, 3, 4 e 5	a máquina certa, porque 5 é o número do ponto fixo
6 ou mais	a contagem não chega lá	o procedimento não para

A máquina da primeira linha erra toda cadeia que termina em abb. Entre as cadeias de a e b com até dez símbolos, que são 1 + 2 + 4 + \cdots + 1024 = 2047, ela erra 255: uma de comprimento 3, duas de comprimento 4 e assim, dobrando, até as 128 de comprimento 10.

A linha do 4 é a que nenhum teste com cadeias acusa. Quem conhece o padrão espera quatro estados, um para cada começo que a máquina precisa separar: nada lido, a, ab e abb. O refinamento termina com o erro ainda no bloco \{0, 2, \text{erro}\}. Ao montar a máquina, o projeto de referência dá a cada bloco as transições do estado de menor número dele, que nesse bloco é o 0, e põe o bloco que contém o erro no lugar do erro. Esse bloco fica com as transições do 0 e passa a ser, ao mesmo tempo, o estado inicial e o estado de erro. A linguagem não muda: nas 2047 cadeias, a máquina responde como a determinizada, e para esse par, de quatro e de seis estados, a lista é prova, porque passa do comprimento 4 + 6 - 2 = 8 da regra.

O que se perde é o estado de erro como estado absorvente, porque, lendo a, o peão sai dele. Na cadeia babb, o programa que executa a tabela anota que o peão caiu no erro já na posição 0, a do primeiro símbolo, e três símbolos depois a cadeia é aceita. A regra do módulo dos autômatos determinísticos, de que toda queda no erro termina em recusa, deixa de valer para essa máquina, e quem usa o erro como sinal para parar de ler já não pode confiar nele.

A parada pelo ponto fixo deixa a sequência de contagens terminada em dois números iguais, como 2, 3, 4, 5 e 5. Em nenhuma linha do quadro a sequência termina assim, nem na do 5, e esse é o sinal de que o procedimento parou pela contagem. Nas duas primeiras linhas há um segundo sinal, que também não depende de cadeia nenhuma: o estado inicial é o próprio estado de erro, numa linguagem que não é vazia. O último 5 da sequência é a prova de que o procedimento parou porque não havia mais o que separar, e nenhum teste melhor economizaria essa rodada.

1.5 A menor máquina, e o que ela permite comparar

O ponto fixo entrega uma partição, e dela se monta a máquina nova: cada bloco vira um estado. A transição de um bloco com um símbolo vai para o bloco que contém o destino de qualquer estado dele, porque no ponto fixo todos os estados de um bloco levam ao mesmo bloco com cada símbolo. O bloco é de aceitação quando os estados dele são, e o estado inicial da máquina nova é o bloco que contém o estado inicial da determinizada. Para (a|b)*abb:

Bloco	Lendo a	Lendo b
\{0, 2\}, inicial	\{1\}	\{0, 2\}
\{1\}	\{1\}	\{3\}
\{3\}	\{1\}	\{4\}
\{4\}, de aceitação	\{1\}	\{0, 2\}
\{\text{erro}\}	\{\text{erro}\}	\{\text{erro}\}

O refinamento de partições seguido dessa montagem é a minimização inteira, e a máquina que ela devolve é a máquina reduzida, a da coluna “Reduzido”. O projeto de referência a monta sempre com o estado de erro. A de (a|b)*abb tem cinco estados, um a menos que a determinizada, porque os estados 0 e 2 viraram um só.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    B02("{0,2}, inicial") -->|a| B1("{1}")
    B02 -->|b| B02
    B1 -->|a| B1
    B1 -->|b| B3("{3}")
    B3 -->|a| B1
    B3 -->|b| B4["{4}, de aceitação"]
    B4 -->|a| B1
    B4 -->|b| B02

Figura 5: A máquina reduzida de (a|b)*abb sem o bloco do erro, a que nenhuma seta leva: quatro estados.

O desenho segue as convenções do desenho da determinizada, e o bloco do erro fica de fora, porque nenhuma seta leva a ele. Compare os dois: o 0 e o 2 viraram o bloco \{0, 2\}, e as setas que saíam deles com o mesmo símbolo, para o mesmo bloco, viraram uma só.

A máquina reduzida não é sempre menor. A determinizada de a.c tem cinco estados, e a reduzida também: refaça as rodadas sobre a tabela de a.c, em Seção 1.2.1, e cada uma das três primeiras separa um estado, até cada bloco ter um estado só. Isso não quer dizer que a minimização falhou: o refinamento calcula quais estados são equivalentes, e em a.c nenhum par é. A resposta certa é devolver a máquina como ela entrou, e um programa que juntasse dois estados só para diminuí-la mudaria a linguagem.

ImportanteTeorema — Unicidade do autômato mínimo

Seja D um autômato finito determinístico sem estados inacessíveis a partir de q_0. O autômato obtido fundindo, em D, cada classe de estados equivalentes segundo a definição de indistinguibilidade num único estado reconhece L(D), tem o menor número de estados entre todos os autômatos determinísticos que reconhecem L(D), e é único a menos de renomeação de estados.

Um estado inacessível é aquele a que nenhuma cadeia leva, saindo do estado inicial. A classe de estados equivalentes é um grupo de estados equivalentes entre si, o bloco do ponto fixo, e não a classe do módulo das expressões regulares, que era um conjunto de linguagens. Fundir a classe num único estado é a montagem do quadro. O teorema afirma três coisas sobre o autômato fundido. O autômato fundido reconhece L(D): a linguagem não muda, porque estados equivalentes dão a mesma resposta a toda continuação. Ele tem o menor número de estados entre todos os autômatos determinísticos da mesma linguagem, construídos por qualquer método. E é único a menos de renomeação: dois autômatos com esse menor número só diferem nos nomes dos estados.

Esse é o autômato mínimo da linguagem, ou máquina mínima. A primeira afirmação vem argumentada logo acima, e a segunda se confere num caso, o de (a|b)*abb, adiante. A prova da segunda e da terceira está no livro de Hopcroft, Motwani e Ullman, citado na caixa “Onde o assunto continua”.

A condição “sem estados inacessíveis” faz diferença. O refinamento não tira estado inacessível: ele só divide blocos, e o estado a que nada leva fica no bloco dele até o fim. Numa máquina escrita à mão, os inacessíveis se tiram antes de minimizar. A construção de subconjuntos cumpre a condição, porque só dá número a conjuntos alcançados a partir do inicial. No projeto de referência, a exceção é o estado de erro, criado sempre. Quando alguma conta da construção dá o conjunto vazio, alguma seta leva ao erro, e a máquina reduzida é a mínima; quando nenhuma dá, o erro é inacessível, e a reduzida tem um estado a mais que a mínima.

Padrão	Thompson	Determinizado	Reduzido	Alguma seta leva ao erro?	Mínima
(a|b)*abb	14	6	5	não	4
a(b|c)*d	12	6	4	sim	4
-?[0-9]+	84	23	4	sim	4
a.c	6	5	5	sim	5

O segundo padrão, a(b|c)*d, descreve um a, depois qualquer cadeia de b e c, inclusive a vazia, e um d no fim. Refaça a linha dele do começo, pela tabela de custos, pela construção de subconjuntos e pelo refinamento.

Na linha de -?[0-9]+, sumiram 80 estados: 61 na determinização e 19 na minimização. Em proporção, a minimização fez mais: dividiu o número por 23 \div 4 = 5{,}75, e a determinização, por 84 \div 23, pouco menos de 3,7. As duas etapas eliminam estados por razões diferentes. A determinização junta num estado só os estados da máquina de Thompson que são ocupados ao mesmo tempo, e não cria os conjuntos que nenhuma cadeia alcança. A minimização junta estados que se comportam igual, embora alcançados por cadeias diferentes. Nenhuma das duas faz o trabalho da outra.

A linha de a.c serve de teste. Um programa que informasse alguma redução para todo padrão estaria errado nesse, e um teste que sempre exigisse redução acusaria um defeito que não existe. Guarde entre os seus casos um padrão em que a minimização não muda nada. Na linha de (a|b)*abb, o 4 da última coluna bate com o piso. Os prefixos vazio, a, ab e abb são distinguíveis dois a dois (confira os seis pares com as testemunhas bb, b e a cadeia vazia): nenhuma máquina determinística dessa linguagem tem menos de quatro estados, e a mínima tem quatro.

A unicidade resolve uma pergunta que o módulo das expressões regulares deixou sem procedimento: decidir, em todos os casos, se duas expressões descrevem a mesma linguagem, o que ali se chamou equivalência plena. A comparação de árvores não resolvia (a|b)* contra (a*b*)*. Com o teorema da unicidade, a pergunta se responde assim:

1. Converta cada expressão em máquina pela construção de Thompson.
2. Determinize as duas máquinas sobre o mesmo alfabeto.
3. Minimize as duas determinizadas.
4. Compare as duas máquinas mínimas.

Se elas são a mesma a menos dos nomes dos estados, as expressões são equivalentes; se não são, as expressões descrevem linguagens diferentes. A pergunta era sobre dois conjuntos de cadeias, que podem ser infinitos, e passa a ser a comparação de duas tabelas. Os padrões a.c e aac|acc, sobre o alfabeto de a e c, são um caso medido: as determinizadas deles diferem, com cinco e sete estados, e, minimizadas, dão a mesma máquina, de cinco estados.

O “a menos de renomeação” pesa na hora de comparar. Dois programas podem numerar os estados da mesma máquina mínima de jeitos diferentes, porque o número de cada bloco depende da ordem em que os blocos aparecem. O teorema garante que os estados de uma correspondem um a um aos da outra, com as mesmas transições e os mesmos estados de aceitação. Uma comparação célula por célula, sem achar essa correspondência antes, pode separar duas máquinas que são a mesma.

O teorema fala do número de estados, e só dele. O tempo por símbolo é uma consulta de tabela em qualquer máquina determinística, mínima ou não, e a memória da tabela depende também do número de colunas. O tamanho do padrão não acompanha o da máquina: o padrão da explosão de estados para n = 8 tem 7 + 7 \times 5 = 42 caracteres, e a máquina mínima dele tem 256 estados.

A construção de Thompson cumpriu o que o teorema do tamanho linear, no módulo dela, garantia: a árvore de -?[0-9]+ tem 22 + 19 + 1 + 2 = 44 nós, o teto é de 2 \times 44 = 88 estados, e a máquina tem 84. Mas aquele teorema não dizia que 84 fosse o menor número possível. A garantia é da classe; a entrega é da implementação. A classe é a das linguagens regulares, as que algum autômato finito reconhece, e o teorema da unicidade acrescenta ao que ela garante uma máquina mínima para cada linguagem. A implementação é cada programa concreto, e o que ele entrega é a máquina que de fato constrói: com 84, 23 ou 4 estados, conforme os procedimentos pelos quais ela passou.

O refinamento de partições recalcula a assinatura de todos os estados a cada rodada, e cada linha de um programa que o implementa se confere contra a definição. Há outro algoritmo para o mesmo problema, o de Hopcroft, que não é usado aqui.

DicaOnde o assunto continua

Hopcroft, Motwani e Ullman, na Introdução à teoria de autômatos, linguagens e computação, tratam a unicidade do autômato mínimo como resultado da teoria de autômatos, sem depender de compiladores. Aho, em Compiladores: princípios, técnicas e ferramentas, apresenta a construção de subconjuntos e a minimização dentro da análise léxica, e Menezes, em Linguagens formais e autômatos, dentro do estudo de autômatos.

1.6 Conferir o programa com outra máquina

Para cada padrão há agora três máquinas: a de Thompson, a determinizada e a reduzida. Os teoremas garantem que as definições não mudam a linguagem de uma para a outra; falta conferir o programa que copiou as definições. Desenhar as três máquinas e olhar não confere, porque o desenho sai da mesma tabela que o programa montou. Se a construção tem um erro de cópia, o desenho traz o erro, e quem procura nele o que espera encontrar passa pelo erro como passou ao escrever o programa. A conferência precisa de alguma coisa que não venha da máquina conferida, e aqui é a outra máquina: as duas recebem as mesmas cadeias e têm de dar as mesmas respostas. Uma lista de cadeias executada inteira de cada vez é uma bateria. A do módulo da construção de Thompson trazia, para cada cadeia, o veredito, a resposta esperada escrita à mão. A daqui não tem veredito: compara a resposta de uma máquina com a da outra. Para não confundir as duas baterias, esta se chama sempre bateria de cadeias.

«Por que não sortear mil cadeias?» Mil cadeias sorteadas conferem mil cadeias, e qualquer outra pode ter ficado de fora. A alternativa é não escolher: usar todas as cadeias sobre o alfabeto fechado, da vazia até um comprimento máximo. Assim as cadeias curtas entram todas, a começar pela vazia. E uma lista assim pode chegar a ser prova, porque a regra da soma dos estados menos 2 pede a concordância em todas as cadeias até um comprimento, e não numa amostra delas.

Padrão	Símbolos do alfabeto	Comprimento máximo	Conta	Cadeias
(a|b)*abb	2	6	1 + 2 + 4 + 8 + 16 + 32 + 64	127
a(b|c)*d	4	5	1 + 4 + 16 + 64 + 256 + 1024	1365
a.c	2	4	1 + 2 + 4 + 8 + 16	31

Em cada conta, a primeira parcela é a cadeia vazia, e cada parcela seguinte é a anterior multiplicada pelo número de símbolos. Nos três padrões, as três máquinas concordam em toda a bateria de cadeias. O crescimento das parcelas é o que limita o comprimento: em a(b|c)*d, ir do comprimento 5 ao 8 acrescenta 4096 + 16.384 + 65.536 cadeias, e o total vai a 87.381.

Essas baterias de cadeias conferem um número finito de cadeias e não provam que as máquinas aceitam as mesmas cadeias. Elas seriam prova, para as duas máquinas determinísticas, se chegassem ao comprimento da soma dos estados menos 2, e nenhuma das três chega. Em a(b|c)*d, a determinizada tem seis estados e a reduzida, quatro: o comprimento seria 6 + 4 - 2 = 8, e o máximo testado foi 5. Nos outros dois padrões, a conta dá 9 e 8, e os máximos testados foram 6 e 4. E há o que a bateria de cadeias não vê por construção: as cadeias dela têm só os símbolos do alfabeto fechado, e uma cadeia com outro símbolo, como abc para a.c, não entra.

Implementação

A comparação entre a máquina de Thompson e uma máquina determinística, no projeto de referência, é esta função:

05_determinizacao.cpp

Discordancia compararSobre(const Afn& afn, const Afd& afd,
                           const std::vector<std::string>& cadeias) {
    Discordancia discordancia;
    for (const std::string& cadeia : cadeias) {
        const bool a = afn.aceita(cadeia);
        const bool b = afd.aceita(cadeia);
        if (a != b) {
            discordancia.houve = true;
            discordancia.cadeia = cadeia;
            discordancia.primeiraAceitou = a;
            discordancia.segundaAceitou = b;
            return discordancia;
        }
    }
    return discordancia;
}

Para cada cadeia, a função pergunta às duas máquinas se aceitam. Na primeira diferença, devolve uma Discordancia com houve verdadeiro, a cadeia e a resposta de cada máquina, em primeiraAceitou e segundaAceitou; sem diferença, devolve a Discordancia sem marcar houve. O houve existe porque a cadeia da discordância pode ser a vazia, e sem ele uma discordância na cadeia vazia se confundiria com nenhuma. A função não faz mais nada, porque uma comparação mais elaborada teria, ela mesma, de ser conferida. E, como a bateria de cadeias só tem os símbolos do alfabeto fechado, o programa de exemplo não acusa a diferença de resposta das duas máquinas de a.c para abc, vista em Seção 1.2.1.

O que prova a igualdade para todas as cadeias sobre o alfabeto são os teoremas. O da equivalência por construção vale na passagem da máquina de Thompson à determinizada, e os da correção do refinamento e da unicidade, na passagem da determinizada à reduzida. A bateria de cadeias confere se o programa copiou as definições sem erro, e quando ela falha, o defeito está no programa.

Vamos chamar de salto cada passagem de uma máquina à seguinte: o primeiro vai da máquina de Thompson à determinizada, e o segundo, da determinizada à reduzida. A igualdade que interessa no fim é a das pontas, a de Thompson contra a reduzida, e comparar só essas duas parece suficiente. Mas considere um erro na determinização que acrescente cadeias à linguagem e um erro na minimização que tire as mesmas cadeias. Nas pontas a linguagem sai certa, a comparação aprova, e os dois erros ficam no programa. Comparar nos dois saltos custa rodar a mesma lista uma vez a mais e, quando há falha, já diz em qual das duas etapas procurar.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    T("máquina de Thompson") -->|"1º salto<br/>prova: equivalência por construção<br/>confere a cópia: bateria de cadeias"| D("máquina determinizada")
    D -->|"2º salto<br/>prova: correção do refinamento e unicidade<br/>confere a cópia: bateria de cadeias"| R("máquina reduzida")
    T -.->|"só as pontas: dois erros podem se cancelar"| R

Figura 6: Os dois saltos: em cada um, o teorema que prova a igualdade e a bateria de cadeias que confere a cópia; a seta tracejada é a comparação só das pontas.

No desenho, cada salto traz o teorema que o prova e a conferência da cópia, e a seta tracejada é a comparação só das pontas, que deixaria passar os dois erros que se cancelam. A investigação de uma falha tem ordem:

1. Olhe a sequência de contagens do refinamento. Se ela não termina com dois números iguais, o defeito está na parada, e o resto fica para depois.
2. Veja em qual dos dois saltos a discordância apareceu.
3. Se foi no primeiro, os suspeitos são os três erros de cópia da construção de subconjuntos: o fecho vazio do estado inicial esquecido, a ordem trocada entre \text{mover} e o fecho vazio, e a seta do coringa que não serve a todos os símbolos do alfabeto fechado.
4. Se foi no segundo, os suspeitos são a montagem da máquina a partir dos blocos e a assinatura sem o primeiro item, defeito que a primeira conferência desta lista não acusa: em (a|b)*abb, a sequência de contagens sai 2 e 2.

A chave sem ordenação não entra na lista: ela não muda resposta nenhuma, e aparece na contagem de estados. A comparação tem de devolver a primeira cadeia em que as máquinas discordaram e a resposta de cada uma, e não só o aviso de que houve discordância. Com a cadeia na mão, você a acompanha pelas duas máquinas, estado por estado, até a transição em que elas se separam.

A bateria de cadeias começa pela vazia, a parcela 1 de cada conta, e essa cadeia confere uma coisa que nenhuma outra confere sozinha: se o estado inicial é de aceitação. No padrão a*, o fecho vazio do estado inicial contém o estado de aceitação, e a cadeia vazia é aceita. Com o fecho vazio esquecido, o conjunto de partida tem só o estado inicial, e a determinizada recusa a cadeia vazia. O desenho continua útil para mostrar uma máquina a outra pessoa e para conferir à mão um caso pequeno, como o de (a|b)*abb, mas não decide se duas máquinas grandes aceitam as mesmas cadeias.

Toda linguagem regular tem um menor número de estados, o do autômato mínimo dela, e para as outras linguagens esse número não existe. A dos parênteses balanceados, no módulo dos autômatos determinísticos, pede mais estados do que qualquer máquina tem, e nem determinizar nem minimizar muda isso. Provar que uma linguagem está nesse caso é o assunto do módulo do lema do bombeamento.

ImportanteDo padrão à menor máquina

Um padrão vira, por três procedimentos de regras fixas, a menor máquina determinística que o reconhece, mais o estado de erro quando nenhuma seta leva a ele. A máquina não determinística sai da construção de Thompson, a construção de subconjuntos a determiniza, e o refinamento de partições, seguido da montagem dos blocos, a minimiza.

O número de estados da máquina mínima é uma propriedade da linguagem. Para saber se uma máquina grande é efeito do programa ou do padrão, compara-se a determinizada com a reduzida: números próximos apontam o padrão, e a reduzida várias vezes menor ainda pede conferir o programa.

A igualdade entre as três máquinas, para as cadeias sobre o alfabeto fechado, se prova pelos teoremas da equivalência por construção, da correção do refinamento e da unicidade, e se confere, no programa, pela bateria de cadeias nos dois saltos.

1.7 A teoria em execução: as duas transformações no sistema de referência

As duas transformações do título são a determinização e a minimização. A parte dfa da Peneira ocupa dois arquivos do projeto de referência. O primeiro, 05_determinizacao.h, lista o que cada etapa devolve e as funções que a parte oferece. O segundo, 05_determinizacao.cpp, traz o código de cada função.

1.7.1 As duas transformações, lado a lado

Os principais nomes dos dois arquivos são estes:

No código	O que é
Afn, Afd	o autômato finito não determinístico e o determinístico, no código
Estado	o número de um estado
alfabetoDoAfn	calcula o alfabeto fechado: os símbolos escritos nas transições, sem repetição e em ordem
avancar	de um conjunto e um símbolo, o conjunto seguinte, já ordenado e sem repetição
determinizar	a construção de subconjuntos
ResultadoDaDeterminizacao	o que determinizar devolve: a máquina, em afd; o número de estados antes e depois, em estadosDoAfn e estadosDoAfd; e subconjuntos, o conjunto que cada estado da máquina nova representa
minimizar	o refinamento de partições e a montagem da máquina reduzida
ResultadoDaMinimizacao	o que minimizar devolve: a máquina; o número de estados dela, em estadosDepois; e blocosPorRodada, a quantidade de blocos da partição inicial e de cada rodada
todasAsCadeias	todas as cadeias sobre um alfabeto, da vazia até um comprimento máximo
compararSobre	a comparação de duas máquinas sobre uma lista de cadeias; há duas funções com esse nome
Discordancia	o que a comparação devolve

Os comentários do código usam palavras que pedem explicação:

• “Estado útil” é o que não é o de erro. A lista subconjuntos tem um conjunto para cada estado útil.
• O código chama de minimo a máquina reduzida, e o programa de exemplo imprime essa palavra. Quando nenhuma transição leva ao estado de erro, a máquina reduzida tem um estado a mais que a máquina mínima do teorema da unicidade.
• Das duas compararSobre, a “sobrecarga” do comentário, uma compara a máquina de Thompson com uma determinística e confere a determinização. A outra compara duas determinísticas e confere a minimização.
• “Reconstrução” é a montagem da máquina reduzida, um estado por bloco.
• “Veredito”, no comentário de Discordancia, é a resposta de cada máquina, e não a resposta esperada de um caso de teste.
• “Enumeração exaustiva, e não amostra” quer dizer todas as cadeias até o comprimento máximo, e não algumas delas.
• As linhas que começam por // recorte: são anotações de ferramenta, e não fazem parte do programa.

Interface

05_determinizacao.h

// 05_determinizacao.h — construção de subconjuntos, minimização por refinamento
// de partições e comparação de duas máquinas sobre uma lista de cadeias.
//
// O alfabeto da determinização chega como parâmetro, e não sai da árvore: o
// coringa passa a valer por cada símbolo desse alfabeto. Cada estado do AFD tem
// uma coluna por símbolo, e a transição do coringa preenche todas elas sem
// acrescentar coluna nem estado.

#ifndef PENEIRA_05_DETERMINIZACAO_H
#define PENEIRA_05_DETERMINIZACAO_H

#include <cstddef>
#include <string>
#include <vector>

#include "03_afd.h"
#include "04_afn.h"

namespace peneira {

struct ResultadoDaDeterminizacao {
    Afd afd;
    std::size_t estadosDoAfn = 0;
    std::size_t estadosDoAfd = 0;
    // Para cada estado útil do AFD (os que não são o de erro), o subconjunto de
    // estados do AFN que ele representa. O reconhecimento não o consulta; fica
    // guardado para que a correspondência entre estado e subconjunto possa ser
    // impressa.
    std::vector<std::vector<Estado>> subconjuntos;
};

struct ResultadoDaMinimizacao {
    Afd afd;
    std::size_t estadosDepois = 0;
    // Número de blocos da partição inicial e de cada rodada de refinamento. Os
    // dois últimos valores são iguais: a rodada que não separou nenhum estado é
    // a condição de parada.
    std::vector<std::size_t> blocosPorRodada;
};

// Os símbolos que aparecem nas transições do AFN, sem repetição e ordenados. A
// transição vazia e o coringa ficam de fora: nenhum dos dois é símbolo da
// entrada.
std::string alfabetoDoAfn(const Afn& afn);

ResultadoDaDeterminizacao determinizar(const Afn& afn, const std::string& alfabeto);
ResultadoDaMinimizacao minimizar(const Afd& afd);

// A primeira cadeia em que duas máquinas discordam e o veredito de cada uma.
// `houve` separa a discordância na cadeia vazia do caso em que as duas
// concordaram em todas, que deixam `cadeia` igualmente vazia.
struct Discordancia {
    bool houve = false;
    std::string cadeia;
    bool primeiraAceitou = false;
    bool segundaAceitou = false;
};

// As duas param na primeira discordância. A sobrecarga AFN com AFD confere a
// determinização; a de AFD com AFD, a minimização.
Discordancia compararSobre(const Afd& primeira, const Afd& segunda,
                           const std::vector<std::string>& cadeias);
Discordancia compararSobre(const Afn& afn, const Afd& afd,
                           const std::vector<std::string>& cadeias);

// Todas as cadeias sobre o alfabeto, da vazia até `comprimentoMaximo`, em ordem
// de comprimento. É enumeração exaustiva, e não amostra. O número de cadeias de
// cada comprimento é o do comprimento anterior vezes o tamanho do alfabeto, e
// por isso o comprimento fica pequeno.
std::vector<std::string> todasAsCadeias(const std::string& alfabeto,
                                        std::size_t comprimentoMaximo);

}  // namespace peneira

#endif  // PENEIRA_05_DETERMINIZACAO_H

Implementação

05_determinizacao.cpp

#include "05_determinizacao.h"

#include <algorithm>
#include <map>

namespace peneira {

std::string alfabetoDoAfn(const Afn& afn) {
    std::vector<char> vistos(256, 0);
    std::string alfabeto;
    for (Estado estado = 0; estado < afn.quantidadeDeEstados(); ++estado) {
        for (const TransicaoAfn& transicao : afn.transicoesDe(estado)) {
            if (transicao.simbolo == kEpsilon || transicao.simbolo == kQualquer) {
                continue;
            }
            const std::size_t byte = static_cast<unsigned char>(transicao.simbolo);
            if (!vistos[byte]) {
                vistos[byte] = 1;
                alfabeto += transicao.simbolo;
            }
        }
    }
    std::sort(alfabeto.begin(), alfabeto.end());
    return alfabeto;
}

namespace {

// Os estados alcançáveis a partir de `conjunto` consumindo `simbolo`, com o
// fecho vazio já aplicado. Devolve o conjunto ordenado e sem repetição: só nessa
// forma ele serve de chave do mapa e um subconjunto já visto é reconhecido.
// recorte:inicio avancar-e-expandir-o-coringa
std::vector<Estado> avancar(const Afn& afn, const std::vector<Estado>& conjunto,
                            const char simbolo) {
    std::vector<Estado> alcancados;
    for (const Estado estado : conjunto) {
        for (const TransicaoAfn& transicao : afn.transicoesDe(estado)) {
            // O coringa casa qualquer símbolo do alfabeto recebido. Expandido
            // aqui, ele não acrescenta coluna nem estado; na árvore, seriam
            // quase cem folhas por ocorrência.
            const bool casa = transicao.simbolo == simbolo || transicao.simbolo == kQualquer;
            if (casa) {
                alcancados.push_back(transicao.destino);
            }
        }
    }
    std::vector<Estado> resultado = afn.fechoVazio(alcancados);
    std::sort(resultado.begin(), resultado.end());
    resultado.erase(std::unique(resultado.begin(), resultado.end()), resultado.end());
    return resultado;
}
// recorte:fim avancar-e-expandir-o-coringa

}  // namespace

ResultadoDaDeterminizacao determinizar(const Afn& afn, const std::string& alfabeto) {
    ResultadoDaDeterminizacao resultado;
    resultado.estadosDoAfn = afn.quantidadeDeEstados();

// recorte:inicio subconjunto-vira-estado
    // Cada estado do AFD é um subconjunto de estados do AFN. O mapa liga cada
    // subconjunto já visto ao seu índice; reencontrá-lo não cria estado, e a
    // construção termina porque os subconjuntos distintos são finitos, ainda
    // que muitos.
    std::map<std::vector<Estado>, Estado> indiceDoSubconjunto;
    std::vector<std::vector<Estado>> subconjuntos;
    std::vector<std::vector<Estado>> pendentes;

    std::vector<Estado> inicialDoAfn = afn.fechoVazio({afn.inicial()});
    std::sort(inicialDoAfn.begin(), inicialDoAfn.end());
    indiceDoSubconjunto[inicialDoAfn] = 0;
    subconjuntos.push_back(inicialDoAfn);
    pendentes.push_back(inicialDoAfn);
    // recorte:fim subconjunto-vira-estado

    // Tabela de destinos, montada antes de o Afd existir: o construtor do Afd
    // exige o número de estados, que só se conhece no fim.
    std::vector<std::vector<Estado>> destinos;
    // Marca de "sem destino", distinta do estado zero, que é um destino válido.
    constexpr Estado kSemDestino = static_cast<Estado>(-1);

    while (!pendentes.empty()) {
        const std::vector<Estado> atual = pendentes.back();
        pendentes.pop_back();
        const Estado origem = indiceDoSubconjunto[atual];
        if (destinos.size() <= origem) {
            destinos.resize(origem + 1, std::vector<Estado>(alfabeto.size(), kSemDestino));
        }

        for (std::size_t coluna = 0; coluna < alfabeto.size(); ++coluna) {
            const std::vector<Estado> proximo = avancar(afn, atual, alfabeto[coluna]);
// recorte:inicio conjunto-vazio-e-o-erro
            if (proximo.empty()) {
                // Conjunto vazio: é o estado de erro, que o construtor do Afd
                // já cria. A posição fica sem destino e continua apontando
                // para ele na tabela final.
                continue;
            }
            // recorte:fim conjunto-vazio-e-o-erro
            auto encontrado = indiceDoSubconjunto.find(proximo);
            Estado indice = 0;
            if (encontrado == indiceDoSubconjunto.end()) {
                indice = subconjuntos.size();
                indiceDoSubconjunto[proximo] = indice;
                subconjuntos.push_back(proximo);
                pendentes.push_back(proximo);
            } else {
                indice = encontrado->second;
            }
            if (destinos.size() <= origem) {
                destinos.resize(origem + 1, std::vector<Estado>(alfabeto.size(), kSemDestino));
            }
            destinos[origem][coluna] = indice;
        }
    }

    destinos.resize(subconjuntos.size(), std::vector<Estado>(alfabeto.size(), kSemDestino));

    Afd afd(alfabeto, subconjuntos.size(), 0);
    for (std::size_t origem = 0; origem < subconjuntos.size(); ++origem) {
        for (std::size_t coluna = 0; coluna < alfabeto.size(); ++coluna) {
            if (destinos[origem][coluna] != kSemDestino) {
                afd.definirTransicao(origem, alfabeto[coluna], destinos[origem][coluna]);
            }
        }
        // Um estado do AFD aceita quando o seu subconjunto contém o estado de
        // aceitação do AFN, isto é, quando algum caminho do AFN termina nele.
        for (const Estado estadoDoAfn : subconjuntos[origem]) {
            if (estadoDoAfn == afn.aceitacao()) {
                afd.marcarAceitacao(origem);
                break;
            }
        }
        std::string nome = "{";
        for (std::size_t i = 0; i < subconjuntos[origem].size(); ++i) {
            if (i > 0) {
                nome += ",";
            }
            nome += std::to_string(subconjuntos[origem][i]);
        }
        nome += "}";
        afd.nomearEstado(origem, nome);
    }

    resultado.afd = afd;
    // Conta o estado de erro, como a minimização conta os blocos. Com os
    // subconjuntos (sem o erro) de um lado e os blocos (com ele) do outro, uma
    // máquina que a minimização não reduz pareceria crescer ao ser minimizada.
    resultado.estadosDoAfd = afd.quantidadeDeEstados();
    resultado.subconjuntos = subconjuntos;
    return resultado;
}

ResultadoDaMinimizacao minimizar(const Afd& afd) {
    ResultadoDaMinimizacao resultado;
    const std::size_t total = afd.quantidadeDeEstados();  // já inclui o de erro
    const std::string& alfabeto = afd.alfabeto();

// recorte:inicio particao-inicial-aceita-ou-nao
    // Refinamento de partições. A partição inicial põe os estados de aceitação
    // no bloco 1 e os demais no bloco 0: é a única diferença visível sem
    // consumir símbolo. Dois estados no mesmo bloco ainda não foram
    // distinguidos; cada rodada testa se algum símbolo os separa.
    std::vector<std::size_t> bloco(total, 0);
    std::size_t aceitantes = 0;
    for (std::size_t estado = 0; estado < total; ++estado) {
        bloco[estado] = afd.ehDeAceitacao(estado) ? 1 : 0;
        aceitantes += bloco[estado];
    }
    // Conta só os blocos com estado dentro. Sem estado de aceitação, ou só com
    // eles, a partição começa com um bloco: contar dois incluiria um vazio, e
    // a contagem cairia de 2 para 1 na primeira rodada sem bloco algum se
    // fundir.
    std::size_t quantidadeDeBlocos = 2;
    if (aceitantes == 0 || aceitantes == total) {
        quantidadeDeBlocos = 1;
        bloco.assign(total, 0);
    }
    resultado.blocosPorRodada.push_back(quantidadeDeBlocos);
    // recorte:fim particao-inicial-aceita-ou-nao

    while (true) {
// recorte:inicio assinatura-refina-a-particao
        // A assinatura de um estado é o bloco em que ele está e o bloco para
        // onde cada símbolo o leva. Estados com a mesma assinatura ficam no
        // mesmo bloco novo; assinaturas diferentes separam.
        std::map<std::vector<std::size_t>, std::size_t> blocoDaAssinatura;
        std::vector<std::size_t> novoBloco(total, 0);
        std::size_t novosBlocos = 0;

        for (std::size_t estado = 0; estado < total; ++estado) {
            std::vector<std::size_t> assinatura;
            assinatura.push_back(bloco[estado]);
            for (const char simbolo : alfabeto) {
                assinatura.push_back(bloco[afd.transicao(estado, simbolo)]);
            }
        // recorte:fim assinatura-refina-a-particao
            auto encontrado = blocoDaAssinatura.find(assinatura);
            if (encontrado == blocoDaAssinatura.end()) {
                blocoDaAssinatura[assinatura] = novosBlocos;
                novoBloco[estado] = novosBlocos;
                ++novosBlocos;
            } else {
                novoBloco[estado] = encontrado->second;
            }
        }

        resultado.blocosPorRodada.push_back(novosBlocos);
        if (novosBlocos == quantidadeDeBlocos) {
            // Ponto fixo: nenhum símbolo distingue dois estados do mesmo bloco.
            // Comparar só a contagem basta, porque a assinatura começa pelo
            // bloco atual e um bloco nunca se funde com outro, só se divide.
            break;
        }
        bloco = novoBloco;
        quantidadeDeBlocos = novosBlocos;
    }

    // Reconstrução: um estado por bloco. O construtor do Afd põe o erro no
    // último índice, e por isso os blocos são renumerados para que o que contém
    // o antigo estado de erro fique por último. As transições para ele não se
    // definem: a tabela já nasce apontando para o erro.
    const std::size_t blocoDoErro = bloco[afd.estadoDeErro()];
    std::vector<std::size_t> novoIndice(quantidadeDeBlocos, 0);
    std::size_t proximo = 0;
    for (std::size_t b = 0; b < quantidadeDeBlocos; ++b) {
        if (b != blocoDoErro) {
            novoIndice[b] = proximo++;
        }
    }
    novoIndice[blocoDoErro] = quantidadeDeBlocos - 1;

    Afd minimo(alfabeto, quantidadeDeBlocos - 1, novoIndice[bloco[afd.estadoInicial()]]);
    std::vector<char> jaTratado(quantidadeDeBlocos, 0);
    for (std::size_t estado = 0; estado < total; ++estado) {
        const std::size_t destinoDoBloco = novoIndice[bloco[estado]];
        if (jaTratado[bloco[estado]]) {
            continue;
        }
        jaTratado[bloco[estado]] = 1;
        for (const char simbolo : alfabeto) {
            const Estado alvo = afd.transicao(estado, simbolo);
            if (bloco[alvo] != blocoDoErro) {
                minimo.definirTransicao(destinoDoBloco, simbolo, novoIndice[bloco[alvo]]);
            }
        }
        if (afd.ehDeAceitacao(estado)) {
            minimo.marcarAceitacao(destinoDoBloco);
        }
        // O bloco do erro fica com o nome que o construtor já deu ao erro;
        // chamado de bN, a tabela o mostraria como um estado comum.
        if (bloco[estado] != blocoDoErro) {
            minimo.nomearEstado(destinoDoBloco, "b" + std::to_string(destinoDoBloco));
        }
    }

    resultado.afd = minimo;
    resultado.estadosDepois = quantidadeDeBlocos;
    return resultado;
}

std::vector<std::string> todasAsCadeias(const std::string& alfabeto,
                                        const std::size_t comprimentoMaximo) {
    std::vector<std::string> cadeias{std::string{}};
    std::vector<std::string> nivel{std::string{}};
    for (std::size_t comprimento = 0; comprimento < comprimentoMaximo; ++comprimento) {
        std::vector<std::string> proximo;
        for (const std::string& base : nivel) {
            for (const char simbolo : alfabeto) {
                proximo.push_back(base + simbolo);
            }
        }
        cadeias.insert(cadeias.end(), proximo.begin(), proximo.end());
        nivel = proximo;
    }
    return cadeias;
}

Discordancia compararSobre(const Afd& primeira, const Afd& segunda,
                           const std::vector<std::string>& cadeias) {
    Discordancia discordancia;
    for (const std::string& cadeia : cadeias) {
        const bool a = primeira.aceita(cadeia);
        const bool b = segunda.aceita(cadeia);
        if (a != b) {
            discordancia.houve = true;
            discordancia.cadeia = cadeia;
            discordancia.primeiraAceitou = a;
            discordancia.segundaAceitou = b;
            return discordancia;
        }
    }
    return discordancia;
}

// recorte:inicio comparar-maquina-com-maquina
Discordancia compararSobre(const Afn& afn, const Afd& afd,
                           const std::vector<std::string>& cadeias) {
    Discordancia discordancia;
    for (const std::string& cadeia : cadeias) {
        const bool a = afn.aceita(cadeia);
        const bool b = afd.aceita(cadeia);
        if (a != b) {
            discordancia.houve = true;
            discordancia.cadeia = cadeia;
            discordancia.primeiraAceitou = a;
            discordancia.segundaAceitou = b;
            return discordancia;
        }
    }
    return discordancia;
}
// recorte:fim comparar-maquina-com-maquina

}  // namespace peneira

Com o arquivo 05_determinizacao.cpp inteiro, aparece o que os trechos isolados não mostram:

• Em determinizar, o conjunto tirado dos pendentes é o último que entrou: pendentes.back() o lê, e pop_back() o tira.
• A lista destinos guarda as transições enquanto a máquina não existe. Um Afd precisa do número de estados para ser criado, e esse número só se conhece no fim. kSemDestino marca a célula que ficou sem transição, e ela continua apontando para o estado de erro.
• Cada estado da máquina nova recebe como nome o conjunto dele, escrito entre { e }. É esse nome que o programa de exemplo imprime.
• estadosDoAfd conta o estado de erro, e o comentário logo acima dele diz por quê. A primeira versão desta parte informava, para uma expressão, 4 estados na máquina determinizada e 5 na reduzida, como se a minimização aumentasse a máquina. O algoritmo estava certo. A determinização contava os conjuntos, sem o estado de erro, e a minimização contava os blocos, com ele.
• Em minimizar, o laço das rodadas termina quando a quantidade de blocos da rodada é igual à da partição anterior. Comparar só as quantidades é suficiente porque uma rodada só divide blocos: com a mesma quantidade, a partição é a mesma. Essa parada compara duas contagens do próprio procedimento, e não uma contagem com um número esperado, vindo de fora.
• Na montagem, um laço percorre os estados em ordem e usa, para cada bloco, o primeiro estado dele que encontra. Os blocos são renumerados para que o bloco do estado de erro fique por último, que é o lugar do erro num Afd. Os outros estados ganham os nomes b0, b1 e assim por diante.

1.7.2 O que os números do ciclo completo mostram

O programa de exemplo conta os estados das três máquinas de quatro padrões, compara as três sobre uma bateria de cadeias em três desses padrões e monta a linguagem da explosão de estados para n de 1 a 8. O que ele imprime vem sem acento:

O ciclo completo, com a contagem em cada etapa.
As contagens de AFD e minimo INCLUEM o estado de erro; o AFN nao tem
estado de erro, porque num automato nao deterministico a ausencia de
transicao ja significa caminho morto.

  /(a|b)*abb/  AFN 14 -> AFD 6 -> minimo 5  (alfabeto: 2)
    subconjuntos que viraram estados do AFD:
      0 = {0,2,4,6,7,8}
      1 = {0,1,2,4,5,7,8,9,10}
      2 = {0,2,3,4,5,7,8}
      3 = {0,2,3,4,5,7,8,11,12}
      4 = {0,2,3,4,5,7,8,13}
    refinamento da particao, rodada a rodada: 2 -> 3 -> 4 -> 5 -> 5 (a ultima repete a anterior: e o ponto fixo)

  /a(b|c)*d/  AFN 12 -> AFD 6 -> minimo 4  (alfabeto: 4)
  /-?[0-9]+/  AFN 84 -> AFD 23 -> minimo 4  (alfabeto: 11)
  /a.c/  AFN 6 -> AFD 5 -> minimo 5  (alfabeto: 2)

Equivalencia por comparacao exaustiva sobre cadeias curtas:
  /(a|b)*abb/  127 cadeias ate comprimento 6: as tres maquinas concordam em todas
  /a(b|c)*d/  1365 cadeias ate comprimento 5: as tres maquinas concordam em todas
  /a.c/  31 cadeias ate comprimento 4: as tres maquinas concordam em todas

A explosao de estados, construida de proposito:
  linguagem: o n-esimo simbolo contado do fim e um 'a'

  n = 1  AFN 10 estados  ->  AFD 4  ->  minimo 3
  n = 2  AFN 16 estados  ->  AFD 6  ->  minimo 5
  n = 3  AFN 22 estados  ->  AFD 10  ->  minimo 9
  n = 4  AFN 28 estados  ->  AFD 18  ->  minimo 17
  n = 5  AFN 34 estados  ->  AFD 34  ->  minimo 33
  n = 6  AFN 40 estados  ->  AFD 66  ->  minimo 65
  n = 7  AFN 46 estados  ->  AFD 130  ->  minimo 129
  n = 8  AFN 52 estados  ->  AFD 258  ->  minimo 257

  o minimo acompanha o AFD: a explosao e da LINGUAGEM, nao do algoritmo.

O programa imprime	O que é
O ciclo completo	as três máquinas de cada padrão, uma depois da outra
As contagens de AFD e minimo INCLUEM o estado de erro	a regra de contagem: a determinizada, que o programa chama de AFD, e a reduzida, que ele chama de minimo, são contadas com o estado de erro; a máquina de Thompson, o AFN, não tem um
caminho morto	o peão que fica sem catraca para o símbolo lido e sai do tabuleiro
/(a|b)*abb/ AFN 14 -> AFD 6 -> minimo 5 (alfabeto: 2)	o padrão, entre barras; os estados da máquina de Thompson, da determinizada e da reduzida; e o número de símbolos do alfabeto fechado
0 = {0,2,4,6,7,8}	o número de um estado da determinizada e o conjunto que ele é
2 -> 3 -> 4 -> 5 -> 5	as quantidades de blocos, da partição inicial em diante
Equivalencia por comparacao exaustiva sobre cadeias curtas	o título das baterias de cadeias; exaustiva quer dizer com todas as cadeias até o comprimento máximo, e a comparação confere essas cadeias, sem provar a equivalência
127 cadeias ate comprimento 6: as tres maquinas concordam em todas	a bateria de cadeias do padrão, com as duas comparações: a máquina de Thompson contra a determinizada, e a determinizada contra a reduzida
n = 8 AFN 52 estados -> AFD 258 -> minimo 257	uma linha da explosão de estados

Só o primeiro padrão vem com os conjuntos e com as quantidades de blocos. Na linha dele, o 5 conta o estado de erro, a que nenhuma transição leva; a máquina mínima desse padrão tem 4 estados.

A última linha do que o programa imprime aplica à explosão o critério dos dois números.

1.7.3 A verificação, e por que ela compara nos dois saltos

Cada bateria de cadeias vem de todasAsCadeias, que recebe um alfabeto e um comprimento máximo. No programa de exemplo, o alfabeto entregue é o fechado de cada padrão, e daí saem as 127, as 1365 e as 31 cadeias.

Quando há discordância, compararSobre devolve a primeira cadeia em que ela apareceu e a resposta de cada máquina. Como há uma comparação para cada salto, já se sabe em qual das duas etapas a discordância está.

A Peneira com o motor pronto

A parte dfa completa o motor da Peneira, que é o conjunto das partes que testam um texto contra um padrão: o padrão vira a tabela de transição da máquina reduzida, e é essa tabela que o executor de autômatos determinísticos roda. A parte nfa e esse executor, que não se falavam, ficaram ligados. Os 42 vereditos escritos à mão, do arquivo de casos da parte nfa, continuam conferindo só a máquina de Thompson. Quem leva essa conferência à máquina determinizada e à reduzida é a bateria de cadeias, nos dois saltos.

O que vem a seguir na Peneira não aumenta o que o executor reconhece. Mostra o limite dele: uma linguagem em que as estruturas se abrem uma dentro da outra, como a dos parênteses balanceados, não tem tabela de transição que a reconheça, por maior que seja a tabela. É desse limite que vem, mais adiante, o analisador sintático, a parte que confere a estrutura de um programa inteiro.

Faça agora a conta para o seu projeto, o que você constrói enquanto lê:

1. Escolha o padrão mais complicado que o seu projeto precisa transformar em máquina.
2. Converta-o em máquina com o seu programa e anote três números: os estados da máquina não determinística, os da determinizada e os da reduzida.
3. Compare o segundo com o terceiro. Se ficam próximos e são grandes, o tamanho vem da linguagem que esse padrão descreve, e o que há para rever é o padrão. Se o terceiro é várias vezes menor que o segundo, confira a chave do catálogo e o ponto em que o coringa é desfeito antes de concluir que não há defeito.

Fora desses dois casos, a comparação não diz de quem é o tamanho.

As três tarefas abaixo pedem, no seu projeto, as duas etapas, o número de estados antes e depois da minimização, a conferência entre as máquinas e um caso de explosão de estados construído de propósito. Nelas, os símbolos da própria linguagem são as unidades que a análise léxica separa no texto de um programa, e não os símbolos de um alfabeto. No fecho, na primeira, quer dizer nos módulos do fim, e não tem relação com o fecho que repete. A redução ao número mínimo de estados é a minimização, e a máquina que ela devolve é a reduzida; a contagem de estados antes e depois da redução é a dos estados da determinizada e a dos da reduzida. A original, na terceira tarefa, é a máquina de Thompson, e a bateria de casos é a lista de cadeias com veredito do módulo da construção de Thompson, e as cadeias dessa bateria que usam só símbolos do alfabeto fechado podem entrar na comparação, junto com as da bateria de cadeias. O crescimento acentuado no número de estados é a explosão de estados.

Tarefa 1: Converter a máquina para a forma determinística

Implemente a conversão da máquina não determinística em uma máquina determinística equivalente. Esta é a peça mais reaproveitada de todo o sistema, e a razão é estrutural: o mesmo componente serve ao reconhecimento dos símbolos da própria linguagem, mais adiante, e à compilação dos padrões que o usuário escreve nela, no fecho. Uma peça, dois níveis — o que torna cada defeito deixado aqui um defeito que aparece duas vezes, em contextos que parecem não ter relação um com o outro.

Tarefa 2: Reduzir a máquina ao número mínimo de estados

Implemente a redução ao número mínimo de estados. É o que transforma um reconhecedor correto porém caro em algo utilizável, e é também o primeiro momento em que o sistema devolve um número que mede o efeito de uma decisão sua.

Faça o próprio sistema reportar a contagem de estados antes e depois da redução. Um número que só existe quando alguém se lembra de contá-lo à mão vale como impressão, e nunca como medida: ele deixa de ser produzido exatamente nas ocasiões em que seria mais interessante, que são aquelas em que o resultado surpreende.

Tarefa 3: Evidenciar a equivalência e o crescimento de estados

Demonstre que a máquina reduzida aceita exatamente a mesma linguagem que a original, por comparação sobre um conjunto de cadeias — nunca por inspeção visual do diagrama, que só mostra o que quem o desenhou já esperava ver. A bateria de casos montada no módulo anterior serve diretamente a isso. Registre o que a comparação prova e o que não prova: uma cadeia em que as duas máquinas discordam é defeito certo, mas concordar em todas as testadas é evidência, e não prova. A garantia de que as duas reconhecem a mesma linguagem vem da própria construção, que o módulo demonstra.

Construa também, de propósito, um caso de crescimento acentuado no número de estados, e observe-o acontecer. O fenômeno é conhecido em teoria; construir o caso e ver o número subir é o que separa saber que a explosão existe de saber quando ela ameaça o seu próprio sistema.