%%{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
1 Determinização e minimização — Resumo
Revisão do módulo, para quem já o leu. As explicações, as contas passo a passo e as tabelas de (a|b)*abb estão na versão completa deste módulo e no capítulo do livro. Deixe papel e lápis por perto: as tabelas se refazem à mão, linha a linha.
Para -?[0-9]+, o padrão de um inteiro com sinal de menos opcional, a máquina de Thompson tem 84 estados. 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. Os 84 saem da tabela de custos (dois estados por folha, por alternância e por fecho, nenhum por concatenação): 22 folhas, 19 alternâncias, um fecho e duas concatenações dão 22 \times 2 + 19 \times 2 + 1 \times 2 = 84. Os termos dos módulos anteriores voltam sem nova explicação.
Cada estado da máquina determinizada, a determinística que sai da construção de subconjuntos, é um conjunto de estados da 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 determinizada 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á na linguagem com um número n à escolha, montada de propósito em Seção 1.3, a máquina de Thompson vai de 10 a 52 estados com n de 1 a 8, e a determinizada, de 4 a 258, também com o estado de erro na conta. O procedimento é o mesmo; muda a linguagem pedida. Separar os dois casos serve para decidir, diante de uma máquina que ficou grande, se o defeito está no seu programa ou se o tamanho vem do padrão.
1.1 Do conjunto ativo à tabela de consulta
Na máquina de Thompson de (a|b)*abb, de 14 estados, a simulação sobre abb passa por conjuntos ativos de 9, 9 e 8 estados. 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 e pode ser feita uma vez e guardada numa tabela: é determinizar.
A construção de subconjuntos usa as duas contas da simulação (a das catracas e a dos corredores) e duas listas: o catálogo, dos conjuntos que já receberam número, e os pendentes, dos conjuntos do catálogo cujas transições ainda falta calcular.
- Calcule o conjunto de partida da simulação. Dê a ele o número 0 e ponha-o no catálogo e nos pendentes.
- 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.
- 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.
- Volte ao passo 2 enquanto houver pendentes.
Em (a|b)*abb, o catálogo acaba com cinco conjuntos, número que ninguém escolheu. O 4 é o único 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 pode mudar os números que eles recebem, e não os conjuntos.
O desenho omite o estado de erro, 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; do 0 sai a transição que lê a, e do 2, a que lê b, e por isso nenhuma conta deu conjunto sem estados. O projeto de referência cria o estado de erro em toda máquina determinística e o conta, e por isso a determinizada de (a|b)*abb tem seis estados, contra os 14 de Thompson. Na tabela da determinizada, abb custa três consultas, do 0 ao 1, ao 3 e ao 4, onde a simulação passou por conjuntos de 9, 9 e 8 estados.
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).
E(S) é a conta dos corredores e \text{mover}(S, a), a das catracas. “Fechado por \delta'” quer dizer que nenhuma transição leva para fora de Q', e “o menor”, que só entram conjuntos alcançados a partir de q_0': dos 2^{14} = 16.384 subconjuntos dos 14 estados da máquina de Thompson de (a|b)*abb, a construção chegou a cinco.
Os pendentes acabam porque os conjuntos acabam: com |Q| estados há no máximo 2^{|Q|} subconjuntos, cada um entra nos pendentes uma vez só, e 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: 4, 0, 2 e 0, 2, 4 são listas diferentes para quem compara elemento por elemento, e, se o catálogo comparar assim, o mesmo conjunto recebe número novo a cada ordem em que chegar. Dez elementos vêm em 10 \times 9 \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 ainda aceita as cadeias certas, porque as cópias de um conjunto levam aos mesmos conjuntos, e por isso nenhum teste com cadeias acusa o defeito. Ele aparece na contagem, com dois estados para o mesmo subconjunto, o que a definição não admite, porque Q' é um conjunto de subconjuntos. A minimização junta as cópias, e a máquina final não guarda sinal delas. O conserto é pôr a lista em ordem crescente e tirar as repetições (0, 2, 2, 4 difere de 0, 2, 4). A lista ordenada e sem repetições é a chave, o que o catálogo usa para procurar. Quem aprendeu que uma lista ordenada se consulta mais depressa pode ler a ordenação como ganho de velocidade, mas ela serve para o programa tratar como iguais dois conjuntos iguais.
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);
Este é o começo de determinizar, no projeto de referência: o passo 1. 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á nele, o “índice” é o número, e AFN e AFD são o autômato finito não determinístico e o determinístico. O std::sort vem antes de o conjunto receber o número 0. O trecho ordena e não tira repetições, e 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. Assim, o programa acerta por coincidência, e uma cópia apareceria no primeiro conjunto que chegasse por dois caminhos em ordens diferentes; com ela, acerta porque a chave representa um conjunto. No projeto, o conjunto tirado dos pendentes é sempre o último que entrou, e o 2 sai antes do 1. Os números continuam os da figura de Figura 1, porque o 3 só aparece quando o 1 é tirado, e o 4, quando o 3 é tirado.
1.2 O que a definição deixa ao programa: o conjunto vazio e o alfabeto
Na máquina de ab, com o alfabeto de a e b, a construção de subconjuntos dá \{0\}, \{1, 2\} e \{3\}, e em quatro das seis células (três conjuntos, dois símbolos) 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 que não aceita, porque não contém estado de F: um estado 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á dois jeitos de montar a máquina: o conjunto vazio recebe número e vira mais um estado, ou as células que o dariam apontam para o estado de erro que a determinizada 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 quatro estados.
05_determinizacao.cpp
O projeto segue o segundo jeito: com proximo 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 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, uma cópia que a minimização juntaria.
A tabela da máquina nova tem uma coluna para cada símbolo do alfabeto. Na definição, o alfabeto vem junto com a máquina; num programa, alguém tem de calculá-lo. Em -?[0-9]+ são 11 símbolos, o sinal de menos e os dez dígitos, e a determinizada de 23 estados tem 23 \times 11 = 253 células; com os 256 valores de um caractere seriam 23 \times 256 = 5.888, e 245 colunas só repetiriam o estado de erro. A máquina de Thompson de a.c tem seis estados 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 leva 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, e os símbolos concretos são os que aparecem escritos em alguma delas: a e c em a.c. O alfabeto é fechado quando a lista fica completa e para de mudar, antes de a construção começar; esse fechado não tem relação com o fecho, que repete, nem com o fecho vazio, nem com o “fechado por \delta'”. Ficam fora de \Sigma o \varepsilon, rótulo das transições vazias, que o fecho vazio já percorre, e a marca do coringa, porque a entrada, o texto que a máquina recebe para ler, traz um caractere determinado, e não um “qualquer”. Sobre o alfabeto fechado, a.c dá quatro conjuntos, numerados de 0 a 3: \{0\}, \{1, 2\}, \{3, 4\} e \{5\}. O conjunto 1 vai ao conjunto 2 com a e com c, porque a seta do coringa sai do estado 2 da máquina de Thompson, um dos dois estados do conjunto 1, e serve às duas colunas. Com o estado de erro são cinco estados, e a máquina 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}"]
Como no desenho 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 conjunto 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 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. Montada com a, c e consultada com c, a, a tabela de a.c manda o a do estado 0 para a coluna do c, que leva ao erro, e recusa aac. Sem coluna para o b, abc é recusada: o programa que executa a tabela traduz cada caractere da entrada no número da coluna dele e responde com o estado de erro quando o caractere não tem coluna.
O leitor de padrões guarda o coringa num nó só, e a construção de Thompson lhe dá uma seta só. Trocá-lo por alternâncias daria uma folha para cada caractere que a tela mostra, quase uma centena por ocorrência, e cada folha e cada alternância custam dois estados: perto de 400 estados 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.
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 função avancar faz as duas contas do passo 2. 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, e 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. Depois vem o fecho vazio dos destinos, na ordem da definição: primeiro \text{mover}, depois E. 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. O programa de exemplo entrega à construção o alfabeto fechado.
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, como o arquivo de casos daquele módulo traz. 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: para o coringa valer também pelo b, a máquina tem de ser construída sobre um alfabeto que contenha o b. 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.
1.3 O que a construção garante, e o que ela não promete
Kleene mostrou que a tradução entre expressões e máquinas de estados finitos existe nos dois sentidos. A construção de Thompson, no módulo dela, e a de subconjuntos, neste, fazem o sentido que vai da expressão à máquina, e o outro sentido fica de fora dos dois módulos. Falta garantir que a construção de subconjuntos não muda a linguagem: sobre o alfabeto fechado, a determinizada tem de aceitar exatamente as cadeias que a de Thompson aceita. A analogia «as duas máquinas fazem a mesma coisa, cada uma do seu jeito» não diz por quê, e uma lista de cadeias em que as duas concordam também não garante, porque as cadeias sobre o alfabeto são infinitas.
%%{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")
As caixas mostram, depois de cada prefixo de abb (os começos da cadeia, do vazio à cadeia inteira), o conjunto ativo da máquina de Thompson e o estado da determinizada: se a correspondência vale depois de cada prefixo, vale depois do último, e as duas máquinas dão a mesma resposta.
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'.
As cadeias do teorema 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, o teorema não diz nada. A afirmação provada é a das caixas do desenho, e vamos chamá-la de invariante. O argumento não cita cadeia, padrão nem comprimento, e por isso vale para todos, mas garante a construção como a definição a descreve, e nada diz de um programa que a tenha copiado com erro. Três erros de cópia 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 é 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. Para uma máquina de seis estados e outra de cinco, é 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: para todo padrão, quem garante a construção é o teorema.
O invariante também acha um erro de cópia: passe pela simulação uma cadeia que leve a determinizada a um conjunto que já tem número, e o conjunto ativo no fim tem de ser o próprio conjunto; se não for, a construção se afastou da definição ali. 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 reconhecem exatamente as mesmas linguagens: num sentido, a determinística já é um caso particular da não determinística; 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.
O único teto que a construção dá para a determinizada é o dos 2^{|Q|} subconjuntos de Q, 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, e nos padrões vistos poucos subconjuntos entram no catálogo, só os que alguma cadeia alcança.
Tome, sobre a e b, as cadeias em que o n-ésimo símbolo contado do fim é um a: com n = 3, aabb pertence, e abab não. O padrão é (a|b)*a seguido de n - 1 cópias de (a|b). Na máquina de Thompson, a cada a lido, um peão a mais entra na fila das cópias de (a|b), e os peões da fila marcam, juntos, quais dos últimos símbolos foram a. A 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: dois prefixos são distinguíveis quando alguma continuação, a testemunha, põe exatamente um deles na linguagem, e k prefixos distinguíveis dois a dois obrigam toda máquina determinística da linguagem a ter pelo menos k estados, o piso. As 2^n cadeias de comprimento n são distinguíveis duas a duas. Se duas delas diferem no i-ésimo símbolo contado do começo, uma com a e a outra com b, colar nas duas i - 1 símbolos quaisquer faz esse símbolo virar o n-ésimo do fim, e só uma das duas pertence (com n = 3, aab e abb diferem no segundo, e a continuação a dá aaba, que pertence, e abba, que não). 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; “Reduzido” é a máquina reduzida, a que sai da minimização (Seção 1.5). Pela tabela de custos, (a|b)*a dá 10 estados, e cada (a|b) a mais dá 6.
| 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 |
| fórmula | 6n + 4 | 2^n + 2, o piso e mais dois | 2^n + 1, o piso e mais um |
O estado que a reduzida tem acima do piso é o de erro, 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: 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, mas se comportam igual, e a minimização os junta, como junta os conjuntos 0 e 2 de (a|b)*abb (Seção 1.4).
Em n = 5, Thompson e determinizada 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. A coluna “Reduzido” mostra de quem é o crescimento: se fosse desperdício do algoritmo, a minimização o desfaria, e 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.
- Os dois números ficam próximos, como 258 e 257. O crescimento é da linguagem, e nenhum programa o evita.
- 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. - 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; -?[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, 1 + 1 + 10 + 10 (o de partida; o que espera o primeiro dígito; dez para um dígito lido, com ou sem sinal antes; e dez para dois dígitos ou mais, um para cada último dígito lido). Os vinte das duas últimas parcelas se comportam igual: de qualquer um deles, mais um dígito leva a um dos dez da última parcela, o sinal de menos leva ao erro, e a cadeia que acabar ali é aceita. Com os outros três (o de partida, o que espera o primeiro dígito e o de erro), são quatro comportamentos, o 4 da máquina reduzida. A construção de Thompson cria estados próprios para cada folha sem verificar se outra já faz o mesmo papel, e a de subconjuntos herda essas cópias, porque junta os estados ocupados ao mesmo tempo, e não os que se comportam igual.
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 \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 w inteira; q não é o estado inicial, que continua sendo q_0, e “para toda cadeia w” inclui a vazia. Equivalentes eram duas máquinas, ou duas expressões, com a mesma linguagem; aqui são dois estados de uma mesma máquina, e a testemunha é a cadeia que leva um deles à aceitação e o outro não. 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 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.
A cadeia vazia separa um estado de aceitação de um que não é, e isso dá a partição inicial: na determinizada de (a|b)*abb, \{4\} e \{0, 1, 2, 3, \text{erro}\}; com nenhum estado de aceitação, ou com todos, ela tem um bloco só. Dois estados no mesmo bloco ainda não foram separados, o que não quer dizer que sejam equivalentes, seja no bloco dos que não aceitam, seja no dos que aceitam. O 1 e o 3 estão no mesmo bloco, e a cadeia b é testemunha, porque do 3 leva ao 4, de aceitação, e 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 ba são ambos de aceitação, e um b a mais os separa (abb é aceita, bab não). Se um símbolo leva p e q a blocos diferentes, eles são distinguíveis, com a testemunha formada por esse símbolo seguido da que separava os destinos.
A assinatura de um estado é a lista formada pelo bloco dele e, para cada símbolo do alfabeto, pelo bloco do estado a que esse símbolo leva; cada lugar da lista é um item. Estados com a mesma assinatura ficam no mesmo bloco da partição nova. Cada cálculo de uma partição nova a partir da anterior é uma rodada, e a partição inicial não conta como rodada. Com A o bloco \{0, 1, 2, 3, \text{erro}\} e B o bloco \{4\}, o 3 tem assinatura A, A, B e os outros quatro de A têm A, A, A, e por isso a primeira rodada o separa. O estado de erro entra nas contas como os outros, mesmo sem seta que leve a ele. As rodadas de (a|b)*abb vão de 2 blocos a 3, a 4, a 5 e a 5 (a quarta rodada não separa nada):
%%{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")
Cada seta traz a testemunha da rodada, e cada rodada alcança testemunhas com um símbolo a mais: b, bb e abb. A partição inicial, que não é rodada, usou a cadeia vazia. 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 número embaixo do P conta as rodadas feitas, Q \setminus F são os estados que não são de aceitação, 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.
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 função minimizar começa pela partição inicial. 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.
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. 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.
A quarta rodada devolveu os cinco blocos da terceira: 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. No exemplo, |Q| = 6, as contagens foram 2, 3, 4, 5 e 5, e a letra k conta rodadas, e não prefixos: k = 3, porque a quarta rodada devolveu P_3 sem mudança, e P_3 é o ponto fixo. O teorema traz duas garantias. O procedimento para, porque alguma das |Q| primeiras rodadas não separa ninguém. E o resultado é o da definição, nos dois lados. Estados em blocos diferentes são distinguíveis, 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, porque 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. 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 estados chegam ao ponto fixo no mesmo bloco, são equivalentes, e as máquinas concordam em todas.
«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, 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, e 4 é o número que espera quem conta um estado para cada começo que a máquina precisa separar (nada lido, a, ab e abb). Parado no 4, o refinamento deixa o erro 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, aqui o 0, e põe o bloco que contém o erro no lugar do erro. Por isso esse bloco 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 erro como estado absorvente: lendo a, o peão sai dele, e em 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, contra a regra do módulo dos autômatos determinísticos de que toda queda no erro termina em recusa. 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á outro 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.
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 inicial é o bloco que contém o estado inicial da determinizada. Essa montagem, depois do refinamento de partições, é a minimização inteira, e a máquina que ela devolve é a máquina reduzida, sempre com o estado de erro no projeto de referência. 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
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ó; como no desenho da determinizada, o bloco do erro fica de fora.
A máquina reduzida não é sempre menor. A determinizada de a.c tem cinco estados, e a reduzida também: cada uma das três primeiras rodadas separa um estado, até cada bloco ter um estado só, porque em a.c nenhum par é equivalente. A resposta certa é devolver a máquina como 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 é o bloco do ponto fixo, e não a classe do módulo das expressões regulares, que era um conjunto de linguagens. O autômato fundido é o autômato mínimo, ou máquina mínima: reconhece L(D) porque estados equivalentes dão a mesma resposta a toda continuação, tem o menor número de estados entre os determinísticos da linguagem, construídos por qualquer método, e é único a menos de renomeação, isto é, só os nomes dos estados podem diferir. A prova das duas últimas afirmações está no livro de Hopcroft, Motwani e Ullman. A condição “sem estados inacessíveis” faz diferença: o refinamento não tira estado inacessível, porque 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 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 |
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. A determinização junta os estados da máquina de Thompson ocupados ao mesmo tempo, e a minimização, os que se comportam igual, embora alcançados por cadeias diferentes; nenhuma das duas faz o trabalho da outra. 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, com as testemunhas bb, b e a cadeia vazia.
A minimização sempre reduz o número de estados?
NotaConfira
Não: em a.c nenhum par de estados é equivalente, a reduzida tem os mesmos cinco estados da determinizada, e um teste que exigisse redução em todo padrã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.
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:
- Converta cada expressão em máquina pela construção de Thompson.
- Determinize as duas máquinas sobre o mesmo alfabeto.
- Minimize as duas determinizadas.
- 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, descrevem linguagens diferentes. Os padrões a.c e aac|acc, sobre a e c, são um caso medido: as determinizadas diferem, com cinco e sete estados, e, minimizadas, dão a mesma máquina, de cinco estados. O “a menos de renomeação” pesa: 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, e uma comparação célula por célula, sem achar antes a correspondência entre os estados, 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, e a memória 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. Há outro algoritmo para calcular os estados equivalentes, o de Hopcroft, que não é usado aqui. Aho trata a construção de subconjuntos e a minimização na análise léxica, e Menezes, no estudo de autômatos.
1.6 Conferir o programa com outra máquina
Os teoremas garantem que as definições não mudam a linguagem de uma máquina para a seguinte; falta conferir o programa que as copiou. Desenhar as três máquinas e olhar não confere, porque o desenho sai da mesma tabela que o programa montou, e um erro de cópia aparece nele também. A conferência precisa de algo 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, mas qualquer outra pode ter ficado de fora. A alternativa é usar todas as cadeias sobre o alfabeto fechado, da vazia até um comprimento máximo: as curtas entram todas, a começar pela vazia. 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.
| Padrão | Símbolos do alfabeto | Comprimento máximo | Cadeias |
|---|---|---|---|
(a|b)*abb |
2 | 6 | 127 |
a(b|c)*d |
4 | 5 | 1365 |
a.c |
2 | 4 | 31 |
Cada contagem soma as cadeias de cada comprimento, da vazia em diante (em (a|b)*abb, 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127). Nos três padrões, as três máquinas concordam em toda a bateria de cadeias, mas isso não prova que aceitam as mesmas cadeias: as baterias de cadeias seriam prova, para as duas 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, a conta dá 9 e 8, e os máximos foram 6 e 4. 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. Também há o que a bateria de cadeias não vê por construção: ela só tem símbolos do alfabeto fechado, e uma cadeia com outro símbolo, como abc para a.c, não entra.
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;
}
Esta é a comparação entre a máquina de Thompson e uma determinística, no projeto de referência. Para cada cadeia, a função pergunta às duas máquinas se aceitam e, 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.
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 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. Comparar só as pontas, a de Thompson contra a reduzida, parece suficiente, mas um erro na determinização que acrescente cadeias à linguagem e um erro na minimização que tire as mesmas cadeias deixam as pontas certas: 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
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:
- 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.
- Veja em qual dos dois saltos a discordância apareceu.
- 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.
- 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, que confere o que nenhuma outra cadeia confere sozinha: se o estado inicial é de aceitação. Em a*, o fecho vazio do estado inicial contém o estado de aceitação, e a cadeia vazia é aceita; com o fecho vazio esquecido, a determinizada a recusa. O desenho serve para mostrar uma máquina a outra pessoa e conferir à mão um caso pequeno, mas não decide se duas máquinas grandes aceitam as mesmas cadeias. Toda linguagem regular tem um menor número de estados, e para as outras esse número não existe. A dos parênteses balanceados 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 Peneira determiniza e minimiza padrões
A parte dfa da Peneira, a que troca a máquina da parte nfa por uma determinística e depois junta os estados que se comportam igual, ocupa dois arquivos do projeto de referência: 05_determinizacao.h, que lista o que cada etapa devolve e as funções da parte, e 05_determinizacao.cpp, que traz o código de cada função. Nos comentários, “estado útil” é o que não é o de erro, e subconjuntos tem um conjunto para cada um. O código chama de minimo a máquina reduzida, que, quando nenhuma transição leva ao erro, tem um estado a mais que a 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, e a outra compara duas determinísticas e confere a minimização. “Reconstrução” é a montagem da máquina reduzida, um estado por bloco. “Veredito”, em Discordancia, é a resposta de cada máquina, e não a esperada de um caso de teste. “Enumeração exaustiva, e não amostra” quer dizer todas as cadeias até o comprimento máximo. As linhas // recorte: são anotações de ferramenta, e não fazem parte do programa.
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
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
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.Na saída, as contagens de AFD e minimo incluem o estado de erro, e a máquina de Thompson, o AFN, não tem um, porque o peão que fica sem catraca para o símbolo lido sai do tabuleiro (o “caminho morto”). Só o primeiro padrão vem com os conjuntos e com as quantidades de blocos; o 5 dele conta o estado de erro, e a máquina mínima desse padrão tem 4 estados. Sob o título Equivalencia por comparacao exaustiva, a comparação confere as cadeias até o comprimento máximo, sem provar a equivalência. estadosDoAfd conta o estado de erro, e o comentário acima dele diz por quê. A primeira versão desta parte informava, para uma expressão, 4 estados na determinizada e 5 na reduzida, como se a minimização aumentasse a máquina: o algoritmo estava certo, mas 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 basta porque uma rodada só divide blocos, e essa parada compara duas contagens do próprio procedimento, e não uma contagem com um número esperado, vindo de fora.
A parte dfa completa o motor da Peneira, 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. Os 42 vereditos escritos à mão, do arquivo de casos da parte nfa, continuam conferindo só a máquina de Thompson, e quem leva a conferência à determinizada e à reduzida é a bateria de cadeias, nos dois saltos. O limite do executor aparece na linguagem em que as estruturas se abrem uma dentro da outra, como a dos parênteses balanceados, que nenhuma tabela de transição reconhece; é 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:
- Escolha o padrão mais complicado que o seu projeto precisa transformar em máquina.
- 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.
- 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.