1 Determinização e minimização — Infográfico do código

O código deste módulo pega a máquina que o módulo 04 monta para um padrão (uma expressão regular: um molde curto, escrito em texto), troca-a por uma que nunca tem escolha e, a partir dessa, monta uma terceira, menor ou do mesmo tamanho, juntando as partes que se comportam igual. Depois confere, numa lista de cadeias curtas (fileiras de símbolos, como abb), que as três máquinas respondem igual a cada cadeia da lista: isso é evidência de que as três aceitam as mesmas cadeias, e não prova. O exemplo que a página segue é o padrão (a|b)*abb.

As palavras que vêm dos módulos anteriores e do código, com o sentido que têm aqui:

Palavra O que é
estado a cada símbolo lido, a máquina passa de uma situação a outra; cada situação é um estado
aceitar, recusar responder sim; responder não
transição, transição vazia a seta que leva ao estado seguinte; a seta que a máquina atravessa sem ler símbolo
estado inicial, estado de aceitação o estado em que a máquina começa; aquele em que a cadeia tem de terminar para ser aceita
alfabeto a lista dos símbolos que a máquina lê; cada símbolo é uma peça que pode aparecer num texto, como a
árvore do padrão, folhas um desenho do padrão em forma de organograma; as caixinhas de baixo do organograma
construção de Thompson a construção do módulo 04 que monta a máquina a partir da árvore do padrão; o que sai dela é a máquina de Thompson
não determinística depois de ler um símbolo, a máquina pode estar em vários estados ao mesmo tempo
fecho vazio os estados de um conjunto mais todos os que se alcançam a partir deles só por transições vazias
coringa escrito ., vale por um símbolo qualquer do alfabeto
determinística de cada estado, com cada símbolo, sai exatamente uma seta: a máquina nunca tem escolha
determinizar trocar a máquina não determinística por uma determinística que aceita as mesmas cadeias
tabela de transição, célula uma linha por estado e uma coluna por símbolo do alfabeto; o cruzamento de uma linha com uma coluna
estado de erro o destino de todo símbolo que não serve; dele a máquina não sai mais
linguagem de uma máquina o conjunto das cadeias que ela aceita
AFN, AFD os nomes que o código e a saída do programa dão à máquina não determinística e à determinística

1.1 O caminho

Do padrão à conferência, cada seta traz as funções que fazem aquela passagem, e cada número é o que o programa imprime para (a|b)*abb.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
    P["padrão (a|b)*abb"] -->|"'analisarExpressao', do módulo 02"| A["árvore do padrão"]
    A -->|"'construirThompson', do módulo 04"| N["máquina de Thompson: 14 estados"]
    N -->|"'alfabetoDoAfn'"| S["alfabeto: a, b"]
    S -->|"'determinizar', com a máquina de Thompson"| D["determinizada: 6 estados"]
    D -->|"'minimizar'"| M["reduzida: 5 estados"]
    M -->|"'todasAsCadeias' e 'compararSobre', com as três máquinas"| R["127 cadeias: as três concordam em todas"]

Figura 1: A construção de subconjuntos, feita por determinizar, troca a máquina de Thompson por uma determinística em que cada estado é um conjunto de estados da antiga: a máquina determinizada. A minimização, feita por minimizar, junta nela os estados que aceitam e recusam as mesmas cadeias lidas a partir deles e devolve a máquina reduzida, que o programa chama de minimo; os números de estados das duas, na saída, incluem o estado de erro.

1.2 Os arquivos

Três arquivos novos, e acréscimos a dois pares de arquivos dos módulos 03 e 04: funções de consulta, para as funções novas consultarem de fora o que só o código daqueles arquivos consultava, e um jeito de criar um Afd sem dados.

Arquivo O que declara De onde vem o que ele usa
05_determinizacao.h os tipos ResultadoDaDeterminizacao (com estadosDoAfd e subconjuntos), ResultadoDaMinimizacao (com blocosPorRodada) e Discordancia (com houve); as funções alfabetoDoAfn, determinizar, minimizar, compararSobre (duas, uma para cada par de máquinas) e todasAsCadeias Afd, do módulo 03; Afn, do módulo 04
05_determinizacao.cpp o corpo das funções acima e avancar, que só este arquivo enxerga; dentro de determinizar, a estrutura indiceDoSubconjunto e a tabela destinos, com a marca kSemDestino; dentro de minimizar, quantidadeDeBlocos, novosBlocos e blocoDoErro fechoVazio, do módulo 04
05_demo.cpp o programa de exemplo (o que se roda para ver o módulo funcionar): patternDaExplosao, medirCiclo, verificarEquivalencia, demonstrarDeterminizacao e main analisarExpressao, do módulo 02; construirThompson, do módulo 04
03_afd.h e 03_afd.cpp, acréscimos o construtor Afd() (o trecho do código que cria um Afd), sem dados, e as funções de consulta estadoInicial, estadoDeErro, alfabeto e nomeDoEstado os arquivos são do módulo 03
04_afn.h e 04_afn.cpp, acréscimos as funções de consulta inicial, aceitacao e transicoesDe os arquivos são do módulo 04

1.3 Os dados na memória

Os três tipos que o módulo define guardam o que determinizar, minimizar e compararSobre devolvem; cada tabela traz, campo a campo, o que o programa guarda depois de rodar (a|b)*abb.

ResultadoDaDeterminizacao, devolvido por determinizar:

Campo O que guarda No exemplo
afd a máquina determinizada, um Afd a tabela logo abaixo
estadosDoAfn quantos estados tem a máquina de Thompson 14
estadosDoAfd quantos estados tem a determinizada, contado o de erro 6
subconjuntos para cada estado útil (um que não é o de erro), o subconjunto que ele representa: um conjunto formado só por estados da máquina de Thompson os cinco da saída, de {0,2,4,6,7,8} a {0,2,3,4,5,7,8,13}

A determinizada, como o Afd a guarda: o nome de cada estado, a linha dele na tabela de transição e se ele é de aceitação.

Número Nome Lendo a Lendo b De aceitação
0, inicial {0,2,4,6,7,8} 1 2 não
1 {0,1,2,4,5,7,8,9,10} 1 3 não
2 {0,2,3,4,5,7,8} 1 2 não
3 {0,2,3,4,5,7,8,11,12} 1 4 não
4 {0,2,3,4,5,7,8,13} 1 2 sim
5 erro 5 5 não

Na memória, tabela_ é uma lista só, uma linha atrás da outra: 1 2 1 3 1 2 1 4 1 2 5 5.

ResultadoDaMinimizacao, devolvido por minimizar. A minimização divide os estados da determinizada em grupos, cada estado em exatamente um: a divisão é uma partição, e cada grupo, um bloco (no módulo 04, bloco era outra coisa: um pedaço de máquina com um estado de entrada e um de saída).

Campo O que guarda No exemplo
afd a máquina reduzida, um estado por bloco a tabela logo abaixo
estadosDepois quantos estados tem a reduzida, contado o de erro 5
blocosPorRodada as contagens: quantos blocos tem a partição inicial e quantos tem a de cada rodada, o cálculo de uma partição nova a partir da anterior 2, 3, 4, 5, 5

A reduzida, como o Afd a guarda:

Número Nome Estados da determinizada Lendo a Lendo b De aceitação
0, inicial b0 0 e 2 1 0 não
1 b1 1 1 2 não
2 b2 3 1 3 não
3 b3 4 1 0 sim
4 erro 5 4 4 não

Na memória, tabela_ é 1 0 1 2 1 3 1 0 4 4.

Discordancia, devolvida por compararSobre:

Campo O que guarda No exemplo, nas duas comparações
houve se alguma cadeia separou as duas máquinas falso
cadeia a primeira cadeia em que as duas respondem diferente vazia
primeiraAceitou, segundaAceitou a resposta de cada máquina nessa cadeia: aceita ou recusa falso, falso

1.4 As funções

Cada função que decide alguma coisa, com o que recebe, o que decide e o que devolve.

1.4.1 alfabetoDoAfn

  • recebe: a máquina de Thompson;
  • decide: transição a transição, se o símbolo dela entra na lista: a transição vazia e o coringa ficam de fora, e o símbolo que já entrou não se repete;
  • devolve: os símbolos em ordem, o alfabeto fechado (a lista dos símbolos, completa antes de a construção de subconjuntos começar; esse fechado não tem relação com o fecho vazio). No exemplo, "ab".

1.4.2 avancar

  • recebe: a máquina de Thompson, um conjunto de estados e um símbolo;
  • decide: transição a transição, se ela casa, isto é, se vale para o símbolo lido: o símbolo dela é o lido, ou ela é do coringa;
  • devolve: os destinos das que casam, com o fecho vazio aplicado, em ordem e sem repetição. Do conjunto 0 do exemplo, lendo a, as transições que casam levam aos estados 1 e 9 da máquina de Thompson, e o fecho vazio dá {0,1,2,4,5,7,8,9,10}.
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 coluna de que o comentário fala é a da tabela de transição. Na árvore, o coringa viraria uma folha para cada caractere que a tela do computador mostra: são as quase cem do comentário. std::sort põe a lista em ordem crescente, e std::unique com erase tiram as repetições, que depois da ordenação ficariam lado a lado.

1.4.3 determinizar

  • recebe: a máquina de Thompson e o alfabeto fechado;
  • decide: para cada conjunto que avancar devolve, um de três desfechos (o quadro abaixo); no fim, quais estados são de aceitação: os que contêm o estado de aceitação da máquina de Thompson, o 13;
  • devolve: um ResultadoDaDeterminizacao.
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 mapa de que o comentário fala, é o catálogo: a lista dos conjuntos que já receberam número. Um conjunto já visto está nele, e o índice é o número dele. Os pendentes são os conjuntos do catálogo cujas transições ainda falta calcular, e o laço de determinizar tira sempre o último que entrou.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
    C["o conjunto que 'avancar' devolve"] -->|"vazio"| V["'continue': a célula continua<br/>apontando para o erro"]
    C -->|"fora do catálogo"| N["recebe o número seguinte,<br/>entra no catálogo<br/>e nos pendentes"]
    C -->|"já no catálogo"| J["a célula recebe<br/>o número que ele já tem"]
    V --> V3["no exemplo: 0 vezes"]
    N --> N3["no exemplo: 4 vezes"]
    J --> J3["no exemplo: 6 vezes"]

Figura 2: Os três desfechos do conjunto que avancar devolve, com quantas vezes cada um acontece em (a|b)*abb: dez conjuntos, dois por estado útil, nenhum vazio. 
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;
}

No comentário, a posição que fica sem destino é uma célula da tabela. Em (a|b)*abb o desfecho do conjunto vazio não acontece; na mesma execução, ele acontece em a(b|c)*d, -?[0-9]+ e a.c.

1.4.4 minimizar

  • recebe: a máquina determinizada;
  • decide: a partição inicial, pela aceitação; em cada rodada, o bloco novo de cada estado, pela assinatura dele (o bloco do estado e, para cada símbolo do alfabeto, o bloco do destino); quando parar: na primeira rodada em que a contagem não muda, sinal de que a partição chegou ao ponto fixo (o resultado a que uma conta repetida chega quando para de mudar); e, ao montar a reduzida, que o bloco do estado de erro fica com o último número;
  • devolve: um ResultadoDaMinimizacao.
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);

Refinamento de partições é o nome do procedimento das rodadas, em que cada partição nova divide blocos da anterior. Consumir símbolo é ler um símbolo. Dois estados distinguidos, no primeiro comentário, são dois já postos em blocos diferentes; dois no mesmo bloco ainda podem ter uma cadeia que leva um à aceitação e o outro não. Um bloco que se funde, no segundo, é um bloco que se junta a outro. Em (a|b)*abb há estado de aceitação e estado que não é, e a partição começa com dois blocos.

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)]);
    }

O recorte termina antes da procura: o programa procura a assinatura em blocoDaAssinatura, como determinizar procura o conjunto no catálogo; a assinatura que ainda não está lá recebe o número de bloco seguinte, e cada estado fica no bloco da sua assinatura.

1.4.5 todasAsCadeias

  • recebe: o alfabeto fechado e um comprimento máximo;
  • decide: comprimento a comprimento, cada cadeia do comprimento anterior ganha no fim cada símbolo do alfabeto;
  • devolve: a bateria de cadeias, todas as cadeias sobre o alfabeto, da vazia (a fileira com zero símbolos) até o comprimento máximo, em ordem de comprimento. Com o alfabeto a, b e o comprimento máximo 6, são 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127.

1.4.6 compararSobre

  • recebe: duas máquinas e a bateria de cadeias. São duas funções com o mesmo nome: uma compara a máquina de Thompson com a determinizada, a outra, a determinizada com a reduzida. Cada passagem de uma máquina à seguinte é um salto;
  • decide: cadeia a cadeia, se as respostas das duas diferem; na primeira diferença, devolve;
  • devolve: uma Discordancia. Em (a|b)*abb, as duas comparações devolvem houve falso.
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;
}


%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    A["verificarEquivalencia(expressao, comprimento)"] --> B["todasAsCadeias(alfabeto, comprimento)"]
    B --> C["compararSobre(afn, determinizado.afd, cadeias)"]
    C --> F["compararSobre(determinizado.afd, minimizado.afd, cadeias)"]
    F --> D{"afnContraAfd.houve"}
    D -- "sim" --> E["AFN != AFD em cadeia"]
    D -- "nao" --> G{"afdContraMinimo.houve"}
    G -- "sim" --> H["AFD != minimo em cadeia"]
    G -- "nao" --> I["as tres maquinas concordam em todas"]

Figura 3: verificarEquivalencia roda as duas comparações sempre; só na escolha da linha a imprimir o primeiro salto vem antes do segundo. O desenho é o mesmo da explicação do projeto de referência deste módulo.

1.4.7 medirCiclo

  • recebe: um padrão e se deve detalhar;
  • decide: se o padrão foi lido sem erro, e se imprime também os subconjuntos e as contagens (no programa de exemplo, só com (a|b)*abb);
  • devolve: nada; imprime a linha com os estados das três máquinas e o tamanho do alfabeto.

1.4.8 verificarEquivalencia

  • recebe: um padrão e o comprimento máximo da bateria de cadeias;
  • decide: que linha imprimir: a diferença do primeiro salto, se houve; senão, a do segundo; senão, que as três concordam;
  • devolve: nada; imprime uma linha.

1.4.9 demonstrarDeterminizacao

  • recebe: nada;
  • decide: roda medirCiclo em quatro padrões e verificarEquivalencia em três; monta com patternDaExplosao, para cada n de 1 a 8, o padrão da linguagem em que o n-ésimo símbolo contado do fim é um a, e confere se a reduzida de n = 8 tem pelo menos 256 estados (o porquê está em Seção 1.7);
  • devolve: se tem. É isso que main devolve a quem rodou o programa, 0 para dizer que sim e 1 para dizer que não, e só essa conferência o decide.

1.5 Uma execução, passo a passo

Os onze quadros são o mesmo desenho, a determinizada pronta; em cada aba, o destaque mostra o que aquele trecho da execução fez: em amarelo e com borda tracejada, o conjunto tirado dos pendentes; em verde e com borda grossa, o estado que acaba de receber número ou de ficar num bloco à parte; em azul e com traço grosso, a transição escrita, ou a que separou.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D0 novo

Figura 4: O fecho vazio do estado inicial da máquina de Thompson, o 6, é {0,2,4,6,7,8}: esse conjunto recebe o número 0 e é o único dos pendentes. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D0 ativo
    class D1,D2 novo
    class e0,e1 usado

Figura 5: Sai dos pendentes o 0. Lendo a, as transições da máquina de Thompson que casam levam aos estados 1 e 9 dela, e o fecho vazio dá {0,1,2,4,5,7,8,9,10}, que recebe 1; lendo b, dá {0,2,3,4,5,7,8}, que recebe 2. Pendentes: 1 e 2. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D2 ativo
    class e4,e5 usado

Figura 6: Sai o 2, o último que entrou, e não o 1. Lendo a ele chega ao conjunto do 1, e lendo b, ao próprio 2: os dois já estão no catálogo, e nenhum estado nasce. Pendentes: só o 1. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D1 ativo
    class D3 novo
    class e2,e3 usado

Figura 7: Sai o 1. Lendo a, ele volta a si mesmo; lendo b, as transições da máquina de Thompson que casam levam aos estados 3 e 11 dela, e o fecho vazio dá {0,2,3,4,5,7,8,11,12}, que recebe 3. Pendentes: 3. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D3 ativo
    class D4 novo
    class e6,e7 usado

Figura 8: Sai o 3. Lendo a, ele vai ao 1; lendo b, a {0,2,3,4,5,7,8,13}, que recebe 4 e vai ser de aceitação, porque contém o 13, o estado de aceitação da máquina de Thompson. Pendentes: 4. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D4 ativo
    class DE novo
    class e8,e9 usado

Figura 9: Sai o 4: lendo a ele vai ao 1, e lendo b, ao 2, os dois já no catálogo, e os pendentes esvaziam. Só então nasce o Afd, com os cinco estados úteis e o de erro, número 5, a que nenhuma seta de outro estado chega. São os 6 da saída. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D4 novo

Figura 10: Os demais vão para o bloco 0, e o estado de aceitação, para o bloco 1: {0, 1, 2, 3, erro} e {4}. Contagem: 2. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D3 novo
    class e7 usado

Figura 11: Lendo b, o 3 vai ao 4, que está noutro bloco; com os dois símbolos, os outros do bloco 0 vão para o próprio bloco 0. O 3 se separa: {0, 1, 2, erro}, {3} e {4}. Contagem: 3. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class D1 novo
    class e3 usado

Figura 12: Lendo b, o 1 vai ao 3, que agora está num bloco só dele, e por isso o 1 se separa: {0, 2, erro}, {1}, {3} e {4}. Contagem: 4. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none
    class DE novo
    class e0,e4,e10 usado

Figura 13: Lendo a, o 0 e o 2 vão ao 1, que agora está num bloco só dele, e o erro fica no erro: o erro se separa, e o 0 e o 2 seguem juntos. {0, 2}, {erro}, {1}, {3} e {4}. Contagem: 5. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 40, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    D0("0, inicial<br/>{0,2,4,6,7,8}")
    D1("1<br/>{0,1,2,4,5,7,8,9,10}")
    D2("2<br/>{0,2,3,4,5,7,8}")
    D3("3<br/>{0,2,3,4,5,7,8,11,12}")
    D4["4, de aceitação<br/>{0,2,3,4,5,7,8,13}"]
    DE("5, erro")
    D0 e0@-->|a| D1
    D0 e1@-->|b| D2
    D1 e2@-->|a| D1
    D1 e3@-->|b| D3
    D2 e4@-->|a| D1
    D2 e5@-->|b| D2
    D3 e6@-->|a| D1
    D3 e7@-->|b| D4
    D4 e8@-->|a| D1
    D4 e9@-->|b| D2
    DE e10@-->|"a, b"| DE
    classDef ativo fill:#fde68a,stroke:#92400e,stroke-width:3px,stroke-dasharray:6 3,color:#000000
    classDef novo fill:#bbf7d0,stroke:#166534,stroke-width:3px,color:#000000
    classDef usado stroke:#1d4ed8,stroke-width:3px,fill:none

Figura 14: Nenhuma assinatura separa ninguém, e nada fica destacado: a contagem repete 5, e o laço termina no ponto fixo. A reduzida tem um estado por bloco, 5, e o de erro é um deles.

A saída do programa, inteira, como ele a imprime:

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, AFN é a máquina de Thompson, AFD é a determinizada e minimo é a reduzida; os 5 da reduzida de (a|b)*abb incluem o estado de erro, a que nenhuma seta de outro estado leva. O caminho morto do começo da saída é o caminho da máquina de Thompson que não tem seta para o símbolo lido e simplesmente acaba; o último bloco da saída se lê em Seção 1.7.

1.6 Por que o código é assim

As decisões que o próprio código registra, cada uma no identificador em que ela mora.

Notaavancar

O coringa vale por cada símbolo do alfabeto que determinizar recebe, e avancar o trata ao calcular cada coluna: a transição do coringa preenche todas as colunas sem acrescentar coluna nem estado. Trocado na árvore do padrão, cada coringa viraria as quase cem folhas do comentário.

NotaindiceDoSubconjunto

avancar devolve o conjunto em ordem e sem repetição porque o catálogo compara as listas elemento por elemento: sem a ordem, 4, 0, 2 e 0, 2, 4, o mesmo conjunto, seriam duas chaves (o que o catálogo usa para procurar), e o conjunto que chegasse na outra ordem não seria reconhecido. Com a chave em ordem, reencontrar um conjunto não cria estado, e a construção termina porque os conjuntos possíveis são finitos, ainda que muitos.

NotakSemDestino

A tabela destinos se monta antes de o Afd existir, porque o construtor do Afd com dados, que vem do módulo 03, exige o número de estados, e esse número só se conhece no fim. A célula sem destino leva a marca kSemDestino, e não o zero, porque o estado 0 é um destino válido.

NotaestadosDoAfd

O número de estados da determinizada inclui o estado de erro, como a contagem dos blocos inclui o bloco dele. Se a determinizada contasse só os conjuntos, sem o erro, e os blocos o contassem, uma máquina que a minimização não reduz pareceria crescer ao ser minimizada.

Notasubconjuntos

O reconhecimento das cadeias não consulta essa lista; ela fica guardada para que o programa possa imprimir que conjunto cada estado representa, como na saída.

NotaquantidadeDeBlocos

A partição inicial conta só os blocos com estado dentro. Quando nenhum estado é de aceitação, ou quando todos são, ela começa com um bloco: contar dois incluiria um vazio, e a contagem cairia de 2 para 1 na primeira rodada sem que bloco algum se juntasse a outro.

NotanovosBlocos

O ponto fixo se reconhece só pela contagem, novosBlocos == quantidadeDeBlocos, sem comparar estado a estado. A contagem é suficiente porque a assinatura começa pelo bloco atual: um bloco nunca se junta a outro, só se divide, e a contagem que não cresceu é a de uma rodada que não dividiu nenhum.

NotablocoDoErro

O construtor do Afd com dados põe o estado de erro no último número; por isso a montagem da reduzida renumera os blocos, e o que contém o antigo estado de erro fica por último. As transições para ele não se escrevem, porque a tabela já nasce apontando para o erro, e o bloco fica com o nome erro: chamado de b4, ele apareceria na tabela como um estado comum.

NotaAfd()

Sem dados, o construtor Afd() cria uma máquina só com o estado de erro, que recusa toda cadeia. Os dois tipos de resultado guardam um Afd, e esse campo precisa existir antes de receber a máquina pronta; sem este construtor, eles teriam de guardar a máquina de outro jeito, num ponteiro ou num optional.

NotatransicoesDe

As funções de consulta que o módulo acrescentou a Afn e a Afd não escrevem nada. A construção de subconjuntos roda fora de Afn e precisa ver o estado inicial, as transições de cada estado e o estado de aceitação; a lista que transicoesDe devolve é a da própria máquina, sem cópia.

NotacompararSobre

As duas sobrecargas devolvem na primeira cadeia em que as respostas diferem, em vez de juntar todas as diferenças, como rodarBateria faz no módulo 04. Uma diferença já mostra que as duas máquinas não aceitam as mesmas cadeias; seguir depois dela só gastaria tempo até a mesma resposta.

Notahouve

Separa a diferença na cadeia vazia do caso em que as duas máquinas concordaram em todas: nos dois, cadeia fica vazia.

1.7 Como o código se confere

O módulo não tem lista de casos com a resposta esperada escrita à mão, como a do módulo 04: o programa de exemplo se confere de dois jeitos.

O primeiro é a bateria de cadeias, nos dois saltos, em três padrões:

Padrão Alfabeto fechado Comprimento máximo Cadeias Resultado
(a\|b)*abb a, b 6 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 as três concordam em todas
a(b\|c)*d a, b, c, d 5 1 + 4 + 16 + 64 + 256 + 1024 = 1365 as três concordam em todas
a.c a, c 4 1 + 2 + 4 + 8 + 16 = 31 as três concordam em todas

Em (a|b)*abb, 15 das 127 cadeias terminam em abb: são abb com qualquer começo de até três símbolos antes, 1 + 2 + 4 + 8 = 15. As três máquinas aceitam essas 15 e recusam as outras. Se uma cadeia separasse duas máquinas, a linha terminaria em AFN != AFD em "…", no primeiro salto, ou em AFD != minimo em "…", no segundo, com a primeira cadeia em que as respostas diferem. Essa linha só se imprime: não muda o que main devolve.

Concordar em todas as cadeias da bateria é evidência, e não prova, de que as máquinas aceitam as mesmas cadeias. A bateria cobre só as cadeias até o comprimento máximo, e só as escritas com os símbolos do alfabeto fechado: uma cadeia como abc, para a.c, não entra.

O segundo usa a linguagem em que o n-ésimo símbolo contado do fim é um a: para cada n de 1 a 8, o programa monta (a|b)*a seguido de n − 1 cópias de (a|b).

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

Esse crescimento da determinizada tem nome: explosão de estados. O programa confere a reduzida, e não a determinizada, porque, se o crescimento viesse da construção de subconjuntos, a minimização o desfaria. Se a reduzida de n = 8 tivesse menos de 256 estados (o produto de oito fatores iguais a 2, o menor número de estados com que uma máquina determinística reconhece essa linguagem), main devolveria 1, o aviso de que algo saiu errado; ela tem 257, e main devolve 0.

O exemplo (a|b)*abb e a saída mostrada nesta página vêm de uma execução do programa do módulo em 29/10/2026.