%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
Q["Q — estados"] --> PQ["em que situação estou?"]
S["Σ — alfabeto"] --> PS["que símbolos posso ler?"]
D["δ — transição"] --> PD["para onde vou com este símbolo?"]
I["q0 — inicial"] --> PI["por onde começo?"]
F["F — aceitação"] --> PF["parar aqui quer dizer sim?"]
1 Autômatos finitos determinísticos
Sete caracteres, sete consultas a uma tabela e um número inteiro guardado entre elas — o resto é saber quantos bytes isso ocupa.
Tenha papel por perto. Você vai trabalhar com três máquinas pequenas: uma para nomes de variável, uma para números com sinal e uma para comentários de linha. Toda tabela delas se confere com uma multiplicação feita à mão. Os números que você obtiver são os mesmos que o programa imprime.
Um campo de formulário aceita nomes de variável. Você digita valor_2 e ele responde sim; digita 2valor e a resposta é não, decidida já no primeiro caractere. Por trás das duas respostas há uma consulta a uma tabela por caractere. Entre uma consulta e a seguinte, o programa guarda um único número inteiro. Nenhuma lista do que já foi digitado, nenhum contador, nenhuma volta atrás.
A tabela dessa máquina ocupa 888 bytes. Ela distingue duas situações úteis (a primeira letra já veio, ou ainda não veio). Um terceiro estado recebe tudo o que não presta. Pois é: são 111 vagas de estacionamento para guardar um sim ou um não. E 48 delas servem só para avisar “aqui, não”. Ninguém chutou esse tamanho, que sai da definição matemática linha por linha.
O capítulo anterior terminou com uma árvore de três operadores e duas folhas, que descreve um conjunto de cadeias e não lê entrada nenhuma. Descrição não decide. Falta o objeto que percorre o texto da esquerda para a direita e devolve sim ou não. Ele cabe em cinco componentes e tem um limite que engenharia nenhuma contorna. E foi descrito, pela primeira vez, para explicar tecido nervoso.
1.1 Um elemento de dois estados vira uma quíntupla
O artigo de 1943 falava de neurônios; o que chegou até o compilador foi uma tabela.
Em dezembro de 1943, o Bulletin of Mathematical Biophysics publicou A logical calculus of the ideas immanent in nervous activity, de Warren S. McCulloch e Walter Pitts. McCulloch era neurofisiologista, e o alvo do trabalho era o sistema nervoso. O artigo não fala em reconhecer texto nem usa a expressão “autômato finito”. Ele trata cada neurônio como elemento de dois estados, com disparo tudo-ou-nada.
A simplificação troca fisiologia por contabilidade. O tecido contínuo vira um sistema discreto, com uma configuração por combinação de células ativas. Sendo finitas as configurações, o comportamento cabe numa tabela: linha por configuração, coluna por estímulo, e em cada célula a configuração seguinte. Nada depende de história, e é a estrutura que viaja das células para o reconhecedor de texto. Quem ouve “rede de neurônios” hoje pensa em camadas e parâmetros ajustados. Do artigo de 1943 fica só o elemento de dois estados. O modelo nasceu descrevendo neurônios; a máquina de estados é o que sobrou dele.
Em dezembro de 1951, Stephen Cole Kleene escreveu na RAND Corporation o memorando RM-704, Representation of events in nerve nets and finite automata. O texto saiu impresso em 1956. Ocupa as páginas 3 a 41 de Automata Studies, organizado por Claude E. Shannon e John McCarthy. Kleene criou ali a notação regular e mostrou que ela descreve os mesmos comportamentos daquelas redes. Nenhum dos dois textos fala de linguagem de programação. Dois formalismos de tradições diferentes coincidindo sugerem uma classe natural, e não um recorte de conveniência. A descrição e a máquina dizem o mesmo; o que existe entre elas é uma tradução de mão dupla. A tradução, porém, ainda está por construir. Falta a ida, da expressão para a máquina, e falta a volta, pela determinização.
O que é preciso saber para executar a máquina sem consultar mais nada? Onde ela pode estar, que símbolos lê, para onde ir com cada símbolo, onde começar e onde parar quer dizer sim. São cinco. Qualquer sexta informação seria enfeite, porque nada mais é consultado durante a execução.
NotaDefinição — Autômato finito determinístico
Um autômato finito determinístico é uma quíntupla M = (Q, \Sigma, \delta, q_0, F). Nela, Q é um conjunto finito e não vazio de estados e \Sigma é um alfabeto finito. A função de transição é \delta : Q \times \Sigma \to Q. O estado inicial é q_0 \in Q, e F \subseteq Q é o conjunto de estados de aceitação.
Na máquina de nomes de variável, Q = \{\texttt{inicio}, \texttt{corpo}, \texttt{erro}\}, e o alfabeto tem 37 símbolos: 26 letras minúsculas, dez dígitos e o sublinhado. De inicio, letra leva a corpo. De corpo, letra, dígito e sublinhado mantêm corpo. O resto vai para erro, o inicial é inicio e F = \{\texttt{corpo}\}. A especificação (“uma letra minúscula seguida de letras, dígitos ou sublinhados”) não fala de estado nem de erro. Nem de tabela. O trabalho mora justamente na tradução de uma coisa para a outra.
A menor máquina possível tem um estado: Q = \{q_0\}, \Sigma = \{a\}, \delta(q_0,a) = q_0 e F = \{q_0\}, que aceita toda cadeia de a, inclusive a vazia. Com F = \emptyset, ela recusa tudo, e as duas reaparecem como resultado intermediário de construções automáticas. A definição também decide pelo que cala. Não exige estados alcançáveis, aceita F vazio ou igual a Q, ignora bolinha e seta. Mas fixa um estado inicial, no singular. O objeto é a função, e dois desenhos com a mesma \delta são a mesma máquina.
A seta de \delta : Q \times \Sigma \to Q esconde uma exigência: a função é total, e todo par de estado e símbolo tem destino. E o desenho em que nada sai de inicio pelos dígitos? Quem lê ali “o dígito trava a máquina” descreve um comportamento que ela não tem. Nada trava. O dígito leva a um estado que não aceita e do qual não se sai, e o desenho só deixou de escrever isso.
NotaTeorema — Completamento
Para todo autômato com função de transição parcial \delta' : Q \times \Sigma \rightharpoonup Q existe um autômato com função de transição total que reconhece exatamente a mesma linguagem. Constrói-se M = (Q \cup \{q_e\}, \Sigma, \delta, q_0, F), com q_e \notin Q. Define-se \delta(q, a) = \delta'(q, a) onde \delta' estiver definida e \delta(q, a) = q_e nos demais casos, inclusive para todo par (q_e, a).
Por que a linguagem não muda? Na máquina parcial, a cadeia que esbarra num par sem destino é recusada. Na completa, ela cai em q_e, que está fora de F e só leva a si mesmo, e termina recusada também. As cadeias que nunca esbarram fazem o mesmo percurso nas duas. O desenho com setas faltando é um autômato completo escrito em abreviatura, e não outra espécie de objeto.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
I["inicio"] -->|"26 letras"| C["corpo<br/>aceita"]
C -->|"letra, dígito, _"| C
I -.->|"dígito ou _<br/>(seta que o desenho omitia)"| E["erro<br/>não aceita"]
E -->|"os 37 símbolos"| E
O completamento acrescenta um estado, com as \lvert\Sigma\rvert transições que saem dele, e dá destino a cada par vazio. A matemática diz isso numa frase (“as transições não desenhadas rejeitam”); o código diz com memória. No projeto de referência, a tabela nasce apontando inteira para o erro, e declarar uma transição é abrir exceção:
DicaNo código
Inverter o padrão custa uma linha e tira um teste da operação mais frequente do sistema. Com a tabela nascendo vazia, cada consulta perguntaria se há transição. Cada ponto de chamada decidiria sozinho o que fazer com a ausência, e bastaria um esquecer para o defeito surgir longe da causa.
O estado acrescentado tem nome e uma propriedade que a construção exige.
NotaDefinição — Estado absorvente
Um estado q \in Q é absorvente quando \delta(q, a) = q para todo a \in \Sigma. Um estado absorvente que não pertence a F chama-se estado de erro ou sumidouro; um estado absorvente que pertence a F é um estado de aceitação irreversível.
Se de q_e saísse transição para um estado útil, a cadeia caída no erro poderia terminar em F, e o completamento mudaria a linguagem. Na máquina de nomes, a linha do erro tem 37 colunas, e as 37 apontam para a própria linha. É um buraco negro com endereço de tabela. Nem todo absorvente é erro, porém: nas cadeias que contêm ab, achado o ab, nada muda a resposta, e aquele estado absorve e aceita.
A absorção serve também no papel. Deixar transições fora do desenho é declarar que todas vão ao mesmo lugar, sem volta. Se algum par devia levar a um estado útil, o desenho mente até alguém executar a cadeia certa. Escreva a tabela inteira uma vez e confira a linha do erro: coluna apontando para fora dela denuncia desenho errado.
Sobre 2valor, a queda acontece na posição 0. O traço do projeto continua consumindo o resto: inicio -2-> erro -v-> erro -a-> erro -l-> erro -o-> erro -r-> erro. Parar ali daria a mesma resposta e esconderia a propriedade. Na estrutura de dados, o erro é um campo ao lado do inicial e das marcas de aceitação:
03_afd.h
std::string alfabeto_;
std::vector<std::size_t> colunaDoByte_; // 256 entradas: byte -> coluna
std::vector<Estado> tabela_; // (estados+1) x |alfabeto|
// `char`, e não `bool`: vector<bool> empacota bits e não devolve referência
// de verdade.
std::vector<char> aceitacao_;
std::vector<std::string> nomes_;
Estado inicial_ = 0;
Estado erro_ = 0;
DicaNo código
Os estados são índices, e o alfabeto é a cadeia declarada no construtor. A função de transição é a tabela, o inicial é um campo e a aceitação é um vetor de marcas. Sobram dois campos que a quíntupla não pede. erro_ está ali porque o completamento o exige. nomes_ não vem de teorema nenhum e serve para o traço dizer inicio -2-> erro em vez de 0 -2-> 2.
A conferência vale nos dois sentidos. Componente sem campo é implementação faltando. Campo sem componente ou é acessório de apresentação, como os nomes, ou a estrutura reconhece outra coisa.
1.1.1 O executor que o sistema deste livro ainda não tinha
A Peneira, a linguagem de reconhecimento de padrões que acompanha estas páginas, chegou até aqui sem executar nada. O capítulo anterior entregou a primeira peça de código dela: um leitor da mini-notação de padrões que devolve a árvore correspondente, reduzida a três operadores e duas folhas. Aquela árvore descreve conjuntos de cadeias e não lê texto de entrada. Descrições não decidem, e é o executor que falta.
Este é o ponto do percurso em que ele aparece. A classe do autômato traz a quíntupla virada estrutura de dados, com a tabela densa, o mapeamento de símbolo para coluna, o estado de erro absorvente e o reconhecimento escrito duas vezes — a versão simples, que o resto do sistema usa, e a instrumentada, que guarda o traço para a demonstração. Junto dela vem o primeiro documento de decisão do percurso que traz uma conta em vez de uma preferência.
Há uma razão de arquitetura para o autômato aparecer tão cedo, e ela se colhe até o último arco. Os padrões que quem usa a linguagem declara viram autômatos finitos. Os símbolos da própria Peneira — as palavras reservadas, os parênteses, os identificadores — também são reconhecidos por autômatos finitos, construídos pelo mesmo maquinário. A mesma peça serve os dois níveis, e é essa dupla aparição que impede a teoria de autômatos de virar preâmbulo de uma caixa fechada.
Uma decisão registrada desde a especificação inicial ganha aqui a sua segunda metade. A Peneira recusa padrões com retrovisor, e o motivo escrito naquele documento era que o produto do compilador é um vetor de autômatos finitos. Por dentro, esse vetor é feito de linhas de inteiros, uma por estado, com o custo em bytes calculado pela própria implementação. O que não cabe numa tabela dessas não cabe na linguagem.
1.2 Sete passos para valor_2, e nenhum de volta
Entre duas leituras, a execução carrega o estado em que está e o que falta ler. Guardar menos impede continuar, e guardar mais é guardar o que nenhuma decisão consulta. Esse par de informações tem nome técnico, configuração, e a execução inteira é uma fila delas.
NotaDefinição — Configuração
Uma configuração de M sobre uma cadeia é um par (q, w) \in Q \times \Sigma^*. Nele, q é o estado corrente e w é o sufixo da entrada ainda não consumido. A configuração inicial da máquina sobre a cadeia w é (q_0, w).
Sobre valor_2, a máquina de nomes atravessa oito configurações para sete símbolos:
| Passo | Símbolo lido | Estado | Falta ler |
|---|---|---|---|
| 0 | — | inicio |
valor_2 |
| 1 | v |
corpo |
alor_2 |
| 2 | a |
corpo |
lor_2 |
| 3 | l |
corpo |
or_2 |
| 4 | o |
corpo |
r_2 |
| 5 | r |
corpo |
_2 |
| 6 | _ |
corpo |
2 |
| 7 | 2 |
corpo |
\varepsilon |
A coluna da direita encolhe um símbolo por linha até acabar. A do meio muda uma vez só. Depois do v, letras, sublinhado e dígito levam todos a corpo, que a especificação não pede para distinguir. Essas duas colunas são a configuração, e as outras duas existem para quem lê.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
C0["(inicio, valor_2)"] -->|"v"| C1["(corpo, alor_2)"]
C1 -->|"a"| C2["(corpo, lor_2)"]
C2 -->|"l o r _"| C6["(corpo, 2)"]
C6 -->|"2"| C7["(corpo, ε)"]
Falta no par o que já foi lido. O prefixo some ao ser consumido, e dele só o estado sobrevive. Com o já-lido dentro do par, a máquina teria o passado inteiro à mão e deixaria de ser finita. O sufixo, por sua vez, não entra em decisão nenhuma. O próximo estado sai do estado corrente e do próximo símbolo. O sufixo só marca quando parar. Na implementação, copiá-lo a cada passo tornaria quadrático um reconhecimento linear (e o defeito só apareceria em entradas grandes). Guarde a posição, que carrega a mesma informação sem copiar nada a cada volta do laço.
NotaDefinição — Passo de computação
A relação de passo \vdash_M entre configurações é definida por (q, aw) \vdash_M (\delta(q,a), w) para todo q \in Q, a \in \Sigma e w \in \Sigma^*. Denota-se por \vdash_M^{*} o fecho reflexivo e transitivo de \vdash_M, isto é, a relação que vale entre duas configurações ligadas por zero ou mais passos.
Três propriedades saem da regra sem estar escritas nela. Cada passo consome exatamente um símbolo. De cada configuração sai no máximo uma seguinte, e exatamente uma enquanto houver símbolo, porque \delta é total. E o passo consulta só q e a, nunca o caminho até ali.
Da terceira vem a diferença para os motores de busca com retrocesso do capítulo anterior. Eles guardam por onde passaram para desfazer escolhas. Esta máquina tem um caminho só saindo de cada ponto e não guarda nada, então não tem por onde voltar. O “determinístico” do nome é essa ausência de escolha. E há a conta de custo: sobre n símbolos são exatamente n passos, cada um com uma consulta e uma atribuição. O tempo é linear desde que consultar \delta custe tempo constante, o que depende de como a tabela mora na memória.
Escrever cada execução como corrente de passos cansa depressa, e uma segunda notação consome a cadeia de uma vez.
NotaDefinição — Função de transição estendida
A função \hat{\delta} : Q \times \Sigma^* \to Q é definida por indução sobre a cadeia. O caso base é \hat{\delta}(q, \varepsilon) = q. O passo é \hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a), para todo w \in \Sigma^* e a \in \Sigma. Vale \hat{\delta}(q,w) = p se e somente se (q, w) \vdash_M^{*} (p, \varepsilon).
Na tabela de valor_2, a linha zero é o caso base e cada linha seguinte aplica o passo. O caso base dá um critério de meio segundo. Vale \varepsilon \in L(M) se e somente se q_0 \in F, ou seja, contorno duplo na bolinha de partida. Por isso a máquina de nomes recusa a cadeia vazia sem regra especial. A definição decompõe a cadeia pelo fim, como os textos clássicos, e o programa consome pelo começo; uma indução curta mostra que dão o mesmo resultado. E \hat{\delta}(q_0, w) devolve um estado, o de chegada, sem registro do trajeto.
NotaDefinição — Linguagem reconhecida
A linguagem reconhecida por M é L(M) = \{ w \in \Sigma^* : \hat{\delta}(q_0, w) \in F \}. Uma linguagem L é dita regular quando existe um autômato finito determinístico M tal que L = L(M).
A condição olha o estado depois da cadeia inteira, e dos intermediários não diz nada. Soa como detalhe até alguém propor o atalho: “basta guardar que já passei por aceitação e responder sim no fim”. Rode o atalho sobre 42. na máquina de números. O 4 e o 2 passam por inteiro, que aceita. O ponto leva a apos_ponto, que não aceita, e a cadeia acaba. A máquina correta recusa. A do sinalizador aceita, como o fiscal que aprova a obra porque um dia ela esteve de pé.
Acontece que a versão defeituosa reconhece outra linguagem: a das cadeias com algum prefixo em L(M). Em muitas linguagens as duas coincidem, e o defeito passa em teste raso. Elas se separam quando uma cadeia válida pode ser continuada até ficar inválida. É o caso dos números e dos nomes qualificados. E de quase tudo o que um tradutor lê. Quando o defeito aparece, o valor inválido já entrou no sistema.
O laço do projeto só troca o estado corrente, e testa a aceitação uma vez, com a entrada acabada:
DicaNo código
O laço não pergunta nada sobre F; a pergunta vem uma vez, depois dele. A definição fala do estado final e cala sobre o momento de conferir, já que matemática não tem relógio. Código tem. Conferir dentro do laço custaria igual e responderia à pergunta do sinalizador.
Com isso, “regular” ganha uma segunda definição. No capítulo anterior, dependia de existir uma expressão que denotasse a linguagem; aqui, de existir uma máquina que a reconheça. As duas descrevem as mesmas linguagens, mas a prova ainda está por fazer, e tratá-las como sinônimos antecipa o resultado. A expressão denota; a máquina reconhece.
1.3 O que a máquina precisa lembrar
Projetar um autômato é decidir quais distinções do passado o resto da entrada ainda pode cobrar.
O sinal de um número não pede estado próprio. Com ou sem o - na frente, a máquina continua esperando um dígito, e duas situações com a mesma resposta para qualquer continuação são, para ela, uma só. Simular um autômato pronto é trabalho de uma tarde. Projetar um a partir de uma frase em português exige responder outra coisa: o que do passado precisa viajar junto?
A resposta começa numa conta de uma linha. Se u e v chegam ao mesmo estado, \hat{\delta}(q_0,u) = \hat{\delta}(q_0,v), então qualquer continuação z lida dali leva ao mesmo lugar: \hat{\delta}(q_0,uz) = \hat{\delta}(q_0,vz). As duas cadeias recebem a mesma resposta para toda continuação, e nada na configuração desfaz a fusão. Um estado é o nome de uma classe de passados que a máquina não distingue mais.
Na máquina de nomes, a e abc9_ chegam ambas a corpo. Dali em diante, recebem o mesmo veredito para qualquer coisa. A máquina esqueceu que uma tinha um caractere e a outra, cinco. Daí sai a regra de projeto. Cada distinção que o resto da entrada pode cobrar exige um estado, e a que nunca será cobrada não exige nenhum. Quem só sabe em que estado está não sabe quantas vezes já entrou nele. Contar passagens pediria um estado por contagem, e os estados são finitos.
Quantos estados pede a especificação de nomes? Dois úteis: ainda não li nada, já li a primeira letra. A quinta posição não merece estado, nem a décima. Um estado por posição descreve as entradas que alguém tinha na cabeça, e não a linguagem, e a máquina cresce com o exemplo.
A de números tem armadilha: sinal opcional, ao menos um dígito e, opcionalmente, um ponto seguido de ao menos um dígito. Em inicio falta tudo. Em inteiro já há dígito e a cadeia vale. Em fracao há dígito depois do ponto, e a cadeia vale de novo. O quarto estado é apos_ponto, com o ponto lido e nenhum dígito ainda, onde a cadeia não é válida e ainda pode vir a ser.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
I["inicio"] -->|"+ -"| I
I -->|"dígito"| N["inteiro<br/>aceita"]
N -->|"dígito"| N
N -->|"."| P["apos_ponto<br/>não aceita"]
P -->|"dígito"| FR["fracao<br/>aceita"]
FR -->|"dígito"| FR
I -->|"."| E["erro"]
P -->|"+ - ."| E
E -->|"qualquer símbolo"| E
Como se descobre o quarto? Pergunte, em cada situação nomeada, se toda continuação recebe ali a mesma resposta que nas outras. Em inteiro, o fim da cadeia significa número válido; logo depois do ponto, número truncado. A continuação que separa as duas é a mais fácil de esquecer, o fim da entrada. Funda apos_ponto com inteiro e a máquina aceita 42., o defeito do sinalizador por outra porta.
AvisoOpcional, mas, se presente, obrigatório
Toda vez que a especificação trouxer um “opcional, mas, se aparecer, tem de vir completo”, conte um estado intermediário que nunca aceita. O ponto pede dígito depois dele. O @ pede domínio, e a primeira barra pede a segunda. Esse estado guarda uma promessa feita e ainda não cumprida, e sem ele a máquina aceita a cadeia cortada no meio.
A terceira máquina reconhece duas barras seguidas de qualquer coisa até o fim da linha. Tem três estados úteis (inicio, uma_barra e no_comentario), e o do meio repete a armadilha: uma barra sozinha ainda pode virar comentário. O alfabeto declarado é estreito, com barra, espaço e as 26 letras minúsculas. Ela tem um estado útil a menos que a de números. Mesmo assim, a tabela dela tem 112 posições contra 65, porque são 28 símbolos contra 13, e o alfabeto entra na conta por um eixo separado.
Nenhuma das três especificações menciona estado. O trabalho foi caçar compromissos, o que, uma vez lido, muda o que ainda pode vir. Nos nomes, a primeira letra. No comentário, a primeira barra promete e a segunda cumpre. Nos números, o primeiro dígito valida, o ponto invalida, o dígito seguinte valida de novo, e o sinal não compromete nada. Some a situação inicial e saem os dois, três e quatro estados úteis. No traço de -240.75, o sinal aparece como inicio ---> inicio. Prefiro esse desenho ao de um estado “já li o sinal”, que nenhuma continuação consultaria e que ocuparia uma linha de tabela.
Antes de seguir. Uma especificação pede cadeias de letras a e b com uma quantidade par de letras a. Que distinção do passado o resto da entrada ainda pode cobrar, e quantos estados úteis ela exige?
Às vezes o projeto não fecha: um estado novo resolve um caso, e o seguinte pede outro. Espere antes do terceiro remendo. Escreva duas entradas que a máquina deveria tratar de modo diferente e veja se chegam ao mesmo estado. Se chegam, falta uma distinção, e o estado novo já tem nome; se não chegam, o defeito está nas transições. Por escrito, o método tem quatro gestos. Listar as situações a distinguir, nomear cada uma pelo que ela lembra, dar destino a cada par e marcar onde parar quer dizer sim. Nessa ordem. O que sobrar sem nome, no fim, é o estado de erro da máquina.
Os nomes denunciam o projeto antes de ele travar. “Li dois caracteres” e “li três caracteres” são nomes de máquina que descreve entradas e vai crescer sem parar. Nomes bons falam de compromisso, como “abri aspas e não fechei” ou “já vi um ponto”. Eles trocam a pergunta “quantos caracteres li?” por “o que ainda falta?”.
E há máquina que não fecha nunca. Nos parênteses balanceados a profundidade arbitrária, (, (( e ((( pedem números diferentes de fechamentos, e as distinções não acabam. Resolver isso com estados é contar ovelhas nos dedos de uma mão: a sexta ovelha cai num dedo já usado. Existe alguma quantidade finita de coisas que a máquina precise lembrar? Quando não existe, acrescentar estados não resolve, porque o obstáculo é de classe.
1.4 Uma testemunha por par, e um piso que ninguém fura
Quatro prefixos provam que nenhuma máquina de números com sinal, escrita por quem for, tem menos de quatro estados úteis. A prova olha para a linguagem, e não para uma máquina, e por isso vale para todas.
NotaDefinição — Prefixos distinguíveis
Dois prefixos u, v \in \Sigma^* são distinguíveis com respeito a uma linguagem L quando existe uma cadeia z \in \Sigma^* tal que exatamente uma das cadeias uz e vz pertence a L. Tal cadeia z chama-se testemunha da distinção.
Pense comigo em dois gêmeos idênticos. Só dá para separá-los se existir uma pergunta a que respondam diferente, e a testemunha é essa pergunta, feita à linguagem. Na máquina de nomes, tome u = \varepsilon, v = \texttt{a} e z = \varepsilon: a cadeia vazia não é nome válido, e a é. A testemunha vazia equivale a perguntar “e se acabar aqui?”. É o caso mais frequente e o mais esquecido.
Na máquina de números, o teste vira procedimento. 4 e 4. se separam pela testemunha vazia. Já o prefixo vazio e 4. resistem às tentativas óbvias: a testemunha vazia recusa os dois, e qualquer sequência de dígitos completa os dois. A que funciona é +5, número sozinho, enquanto 4.+5 fica fora. Falhar nas duas primeiras tentativas não prova nada sobre o par.
Os prefixos são cadeias quaisquer de \Sigma^*, válidas ou não. 2x fica fora de qualquer nome e, ainda assim, conta como prefixo: leva ao erro, e o erro conta. Quem só analisa entradas válidas acha o sumidouro supérfluo. A ponte com o projeto é direta. Dois prefixos distinguíveis não podem chegar ao mesmo estado, porque o estado é tudo o que sobrevive deles e a testemunha exige respostas diferentes. Antes se olhava o que a máquina esquece; aqui, o que a linguagem proíbe esquecer.
AvisoDistinguir não é transitivo
Se u se separa de v e v se separa de w, nada se conclui sobre u e w. Cada separação pode ter usado uma testemunha própria, e o terceiro par pode dividir estado sem contradição nenhuma. Por isso o teorema pede a família dois a dois, com uma testemunha para cada par.
NotaTeorema — Limite inferior de estados
Se existem k prefixos dois a dois distinguíveis com respeito a L, então todo autômato finito determinístico que reconhece L tem pelo menos k estados.
A demonstração é o princípio da casa dos pombos, em três passos. Suponha uma máquina com menos de k estados. Os k prefixos não cabem nela sem que dois, digamos u e v, cheguem ao mesmo estado. Como são distinguíveis, existe z com exatamente uma de uz e vz em L; mas a máquina, partindo do mesmo estado, responde igual às duas, o que contradiz a distinção.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
P1["prefixo com i aberturas"] --> Q["k+1 prefixos, k estados:<br/>dois caem no mesmo estado"]
P2["prefixo com j aberturas"] --> Q
Q --> T["testemunha: i fechamentos<br/>completa um, não completa o outro"]
T --> C["a máquina responde igual aos dois:<br/>contradição"]
Com os parênteses, a ovelha que sobrava vira prova. Tome (, ((, ((( e assim por diante. Dois prefixos com i \neq j aberturas se separam pela testemunha de i fechamentos, que completa um e não o outro. Fixado qualquer número k de estados, k+1 profundidades obrigam duas a dividir estado. Nenhuma quantidade finita basta, e a linguagem fica fora da classe. O princípio já apareceu no percurso, na hierarquia lida pela memória e no limite do fechamento sob operações. Agora ele volta com hipótese e conclusão, pronto para qualquer linguagem que alguém apresente.
No uso diário, o teorema troca “quantos estados preciso?” por uma pergunta sobre a linguagem, respondível sem escrever máquina. Liste prefixos, procure testemunhas, conte quantos separou dois a dois. O número é um piso contra qualquer implementação, inclusive a de amanhã com uma ideia melhor. Na máquina de números, o vazio, 4, 4. e 4.5 são dois a dois distinguíveis: são os quatro estados úteis do projeto, agora com prova de que nenhum sobra. Com quatro prefixos são seis pares a conferir, com cinco são dez, e pular um invalida a conta.
A recíproca não vale. Achar k prefixos distinguíveis não garante que k estados bastem, pois a lista pode ter deixado escapar uma distinção. O teorema dá o piso e cala sobre o teto; fechar a distância é o trabalho da minimização, que agrupa prefixos em classes até que agrupar mais mude a linguagem. Daí o gosto de quebra-cabeça de solução única. Se a especificação obriga k distinções, esperteza nenhuma produz k-1 estados. A habilidade decide só se você chega ao piso.
Na forma completa, que dá o número mínimo exato, o resultado é o teorema de Myhill–Nerode, e aqui está a metade fraca. As versões conferíveis são a de Anil Nerode, Linear automaton transformations, nos Proceedings of the American Mathematical Society, volume 9, número 4, páginas 541 a 544, de 1958, e a de Michael O. Rabin e Dana Scott, Finite automata and their decision problems, no IBM Journal of Research and Development, volume 3, número 2, páginas 114 a 125, de 1959. A contribuição de John Myhill está num relatório técnico de 1957, de circulação restrita, e por isso fica fora das referências que dá para conferir.
ImportanteO alcance exato do limite inferior
O teorema prova que nenhuma máquina para aquela linguagem tem menos estados que o número de prefixos exibidos. Ele não prova que a sua máquina seja mínima; para isso falta o algoritmo de minimização, que chega junto com a determinização. E exibir uma quantidade finita de prefixos distinguíveis não tira a linguagem da classe, só fixa um mínimo de estados. A impossibilidade pede uma família infinita, como a dos parênteses. Existe uma segunda rota para esse tipo de negativa, mais adiante no percurso, e esta não depende dela.
Sem esse instrumento, “não achei máquina para isto, logo ela não existe” ficaria no ar, porque não achar pode significar só que a busca falhou. A família infinita de prefixos é o árbitro entre “é impossível” e “eu não consegui”.
1.5 Uma letra lembrada em 888 bytes
Guardar a função de transição é a primeira decisão do percurso com custo medido em bytes.
Para n estados e k símbolos, \delta tem exatamente n \cdot k valores, e a definição cala sobre onde eles moram. O jeito mais direto é uma matriz, com uma linha para cada estado e uma coluna para cada símbolo declarado. O destino de (q,a) fica na posição q \cdot k + c, onde c é a coluna de a. Cada consulta é uma multiplicação, uma soma e uma leitura de vetor.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
subgraph densa["matriz densa"]
D1["consulta: uma multiplicação,<br/>uma soma, um acesso a vetor"]
D2["memória: (n+1) × m × 8 bytes,<br/>com o erro incluído"]
end
subgraph esparsa["mapa esparso"]
E1["consulta: cálculo de espalhamento<br/>e comparação de chave"]
E2["memória: só as transições<br/>que existem"]
end
Na máquina de números, com cinco estados contando o de erro e 13 colunas, o destino de apos_ponto (índice 2) pelo dígito 7, oitava coluna do alfabeto, mora na posição 2 \times 13 + 7 = 33. Sem busca, sem comparação, e o índice não depende de quantas transições existem. Com custo igual em toda posição, o tempo se calcula sem medir: comprimento do texto vezes uma constante, prometido até a entradas que ainda não existem. Estrutura de custo variável pede medição por perfil de entrada, válida só para o perfil medido.
O bloco é contíguo. As posições visitadas em sequência ficam próximas na memória, o que tende a ajudar a máquina física (nada foi medido aqui a respeito), e o bloco se grava e se recarrega como está. Só que a matriz guarda todas as n \cdot k posições, inclusive as que apenas apontam para o erro.
A alternativa é uma tabela de dispersão de pares (q,a) para destinos, com o erro implícito na ausência de chave. A vantagem dela vem primeiro, que justificativa aberta pelas qualidades da vencedora é propaganda. Ela ganha em memória, e de longe. As três máquinas daqui definem entre um quarto e dois terços das posições, e o resto ocupa espaço para repetir o mesmo valor, proporção que piora em máquinas geradas automaticamente.
O descarte tem duas razões, e nenhuma é memória. A consulta de transição acontece uma vez por caractere da entrada, a operação mais frequente de quem processa texto. Trocar acesso a vetor por dispersão e comparação de chave multiplica esse custo por uma constante nada pequena, e a linearidade deixa de ser previsível. A outra razão é de arquitetura: a tabela costuma ser a forma do que o sistema emite no fim. A matriz densa se grava sem tradução, e o mapa exigiria um formato de serialização, decisão que voltaria na geração de código, quando refazer já não é opção.
A consulta escrita é o argumento inteiro:
DicaNo código
Cabem duas responsabilidades na mesma função, e só uma está na quíntupla. A aritmética de índice é a função de transição escrita em vetor. O teste que vem antes trata de algo que a matemática ignora: para ela, caractere fora do alfabeto não existe. Para o programa existe, porque a entrada é um arquivo, e um arquivo contém qualquer byte.
A comparação não elegeu a matriz densa para funções de transição em geral, nem para este sistema em qualquer escala. Pesou dois critérios nesta escala e deixou escrita a condição para refazer a conta. E a coluna, de onde vem? De um vetor montado no construtor, que leva cada byte à posição dele no alfabeto:
DicaNo código
Indexar a tabela direto pelo código do caractere daria 256 colunas por estado. Na máquina de números, seriam 256 no lugar de 13, quase vinte vezes a memória: um teclado de 256 teclas para digitar números, com 243 de enfeite. Na de nomes, com 37 símbolos, o desperdício seria de quase sete vezes a memória necessária.
O mapeamento custa 256 entradas por autômato, e não por estado, enquanto o que ele evita cresce com os estados. De quebra, ele traz um efeito colateral. Byte fora do alfabeto não tem coluna, e a consulta precisa devolver o erro antes de calcular o índice. Sem esse teste, o cálculo leria memória fora da tabela, com comportamento imprevisível e longe de qualquer recusa.
Dá para ir além e juntar numa coluna os símbolos que nenhuma transição distingue, a fusão de indistinguíveis aplicada ao outro eixo, justificada pela mesma falta de testemunha. Na máquina de nomes, as 26 letras se comportam igual em todos os estados, e os dez dígitos mais o sublinhado também: duas colunas no lugar de 37. As máquinas daqui não fazem isso, porque as faixas já são contíguas no alfabeto. Mas o ganho cresce com o alfabeto, que é para onde as máquinas vão.
1.5.1 Três fatores e uma multiplicação
O consumo da matriz densa tem fórmula exata, que devolve o número de bytes contado:
B(n,k,b) = n \cdot k \cdot b
São n estados, k símbolos no alfabeto declarado e b bytes por destino. Dobrar o alfabeto dobra a tabela, e um estado a mais acrescenta uma linha inteira.
AvisoCom ou sem o estado de erro
Nesta fórmula, n inclui o estado de erro. O registro de decisão do projeto usa outra escrita, (n+1) \times m, em que n conta só os estados úteis e m é o tamanho do alfabeto. As contas batem nos três casos: (2{+}1)\times 37 = 111, (4{+}1)\times 13 = 65 e (3{+}1)\times 28 = 112. Pôr o rótulo de uma na fórmula da outra erra por um estado inteiro.
Com destinos de 8 bytes nesta plataforma, as três máquinas ocupam:
| Máquina | Estados úteis | Alfabeto | Posições | Bytes | Transições não-erro |
|---|---|---|---|---|---|
| nome de variável | 2 | 37 | 111 | 888 | 63 |
| número com sinal | 4 | 13 | 65 | 520 | 43 |
| comentário de linha | 3 | 28 | 112 | 896 | 30 |
Na de números, são 5 \times 13 = 65 posições e 65 \times 8 = 520 bytes. A de comentário, com um estado útil a menos, chega a 4 \times 28 = 112 posições e 896 bytes, porque ali pesa o alfabeto, o fator que quem projeta olha por último. Os números saem do programa, que os calcula e imprime. Tabela copiada à mão que divergisse do código pareceria verificada, e seria pior que nenhuma.
DicaNo código
Depois do completamento, nenhuma célula fica sem destino, e “definida” deixa de ser propriedade matemática para virar convenção de quem implementa: destino diferente de erro_. A contagem só faz sentido porque alguém escolheu um estado para significar “nenhum lugar útil”, e a quíntupla não registra essa escolha.
Dos três fatores, só b está na mão de quem implementa. Destinos de 2 bytes dividem a tabela por quatro e impõem um teto de 65.536 estados, o que 2 bytes endereçam. Esse teto se verifica na construção da máquina, e não na execução, porque quem descobre o estouro no meio de um reconhecimento já perdeu a construção que o causou.
As duas últimas colunas da tabela mostram o desperdício. Na máquina de comentário, 82 das 112 células guardam o mesmo valor: três quartos da tabela daquela máquina dizem só não. A de nomes gasta 43% das posições assim, e a de números, 34%. A fração depende de quão largo é o alfabeto diante do que a máquina usa (o comentário declara 26 letras e trata quase todas igual), então percentual desses sempre vem com o nome da máquina.
Tabela bem aproveitada seria a de uma linguagem permissiva, que aceita quase tudo e decide pouco; nas três medidas, a fração de erro acompanha o quanto a especificação recusa. As 82 células existem porque a função é total. A matemática resolveu a totalidade com uma frase, e a implementação, com um estado e uma célula por par que faltava. O que a definição não faz, o código faz por ela — e cobra. Aqui, 896 bytes por uma máquina de três situações.
O gasto se aceita por três razões: o custo por consulta, o formato do que se emite e a escala, já que 896 bytes por máquina não pesam. Vale o hábito da conta. A unidade muda ao longo do percurso (nós de árvore antes, bytes de tabela agora, instruções emitidas no fim), e em todas o número sai antes da implementação.
A fórmula também prevê. A transformação de máquina não determinística em determinística pode gerar estados em número exponencial no da máquina de partida, no pior caso, que não descreve a média. Com B(n,k,b) escrita de antemão, a pergunta na hora vira “a conta previa isto?”. E o alfabeto cresce sem aviso: texto acentuado, ou alfabeto declarado por conveniência, multiplica cada linha. Fica adiada, com endereço, uma saída intermediária: estados de linhas idênticas podem dividir uma linha só, com acesso constante e boa parte da memória recuperada. A conta dela se refaz com as máquinas maiores. Decisão registrada como adiada é revisitada; a não registrada vira “sempre foi assim”.
1.6 Três jeitos de dizer não
Submeta 2valor, //OK e 42. às máquinas certas e as três voltam recusadas, cada uma por um motivo. Chamado sobre texto arbitrário, um reconhecedor passa a maior parte do tempo recusando. Uma máquina completa recusa de três maneiras, e cada uma informa uma coisa diferente.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
R["recusa"] --> A["símbolo fora do alfabeto declarado<br/>quem escreveu precisa da posição"]
R --> B["símbolo válido, transição inexistente<br/>precisa da posição e do que se esperava"]
R --> C["cadeia inteira consumida em estado não final<br/>precisa saber o que faltou no fim"]
A primeira é o símbolo válido sem transição prevista. Em 2valor, o dígito pertence ao alfabeto, mas de inicio não sai transição por dígito, e a queda é na posição 0. Na máquina de comentário, /x cai na posição 1: x é letra do alfabeto, e de uma_barra só se sai pela segunda barra. A segunda é o símbolo fora do alfabeto. Em //OK, a queda é na posição 2, no O maiúsculo, que a máquina de comentário nem sabe ler. Maiúscula não entra. O alfabeto dela deixa as maiúsculas de fora justamente para expor essa diferença.
As duas primeiras têm um culpado com endereço, um caractere que dá para sublinhar na tela. Uma pede a quem digitou que troque o caractere; a outra avisa que ele está fora do vocabulário da máquina, às vezes porque a máquina errada foi chamada. A terceira nunca passa pelo erro. 42. consome os três símbolos e para em apos_ponto, que não aceita, e o culpado é o que ninguém escreveu. É a forma que quem implementa esquece. Toda queda no erro leva à recusa, mas nem toda recusa passa pelo erro.
Cada recusa se reconhece por uma pergunta, com a resposta pronta na estrutura. O símbolo tem coluna? Responde o mapeamento do construtor. A célula aponta para o erro? Responde a tabela. Consumida a cadeia, o estado está em F? Responde o vetor de marcas.
Decida antes do próximo parágrafo. A máquina de comentário aceita a cadeia formada por duas barras e nada mais?
Aceita. A cadeia passa por inicio e uma_barra e para em no_comentario, que é de aceitação: “qualquer coisa até o fim da linha” inclui coisa nenhuma. Quem errou leu a especificação pela metade. A execução resolve isso em um segundo, e o desenho esconde por meia hora.
Diante da cadeia que não pertence, o reconhecedor pode devolver essa informação, com o que sabe sobre o ponto da falha, ou lançar exceção e encerrar ali. A primeira saída entrega ao chamador algo com que decidir; a segunda entrega o controle, e nada mais. Imagine um sistema que testa vários padrões na mesma posição do texto (números, nomes, operadores), em que o candidato que falha cede a vez ao seguinte. Um reconhecedor que aborta no primeiro símbolo estranho derruba a consulta inteira. É o porteiro que, diante de alguém sem crachá, aciona o alarme de incêndio em vez de dizer “por esta porta, não”.
E quem arca com o desvio? A exceção obriga todo chamador a se preparar, mesmo quem sabe que a recusa é frequente e inofensiva. O tratamento se espalha pelo sistema por um evento nada excepcional. Devolver a recusa como valor concentra a decisão em quem tem contexto: o reconhecedor relata, e o chamador decide se aquilo é erro de sintaxe, fim de token (a unidade que o analisador léxico entrega) ou só o padrão errado.
Compare duas mensagens sobre 42.: encontrado '.' e esperava-se um dígito após o ponto decimal. As duas são verdadeiras, mas só a segunda é acionável. A primeira informa o que a máquina viu, que quem digitou já sabe, feito GPS que anuncia “você está aqui” sem rota nenhuma. A segunda informa o que se esperava, e isso sai de graça da tabela: as colunas do estado corrente que não vão para o erro são a lista dos símbolos aceitáveis ali. E coluna 47 não é posição que se veja; a mensagem mostra o trecho e o símbolo, para ninguém contar caracteres com o dedo.
ImportanteO que a estrutura já sabe antes de alguém perguntar
Fundir as três recusas numa mensagem só descarta informação que a estrutura entregou de graça. O O de //OK já chega sem coluna no mapeamento, e isso diz que ele está fora do alfabeto. A cadeia 42. já termina num estado que não aceita, e isso diz que faltou alguma coisa no fim.
A execução instrumentada do projeto registra a primeira queda, com a posição e se o símbolo estava fora do alfabeto, e continua consumindo a cadeia:
03_afd.cpp
Execucao Afd::executar(const std::string& cadeia) const {
Execucao execucao;
Estado atual = inicial_;
execucao.passos.push_back(Configuracao{atual, 0, '\0'});
for (std::size_t i = 0; i < cadeia.size(); ++i) {
const char simbolo = cadeia[i];
const bool foraDoAlfabeto = colunaDe(simbolo) == kSemColuna;
const Estado proximo = transicao(atual, simbolo);
execucao.passos.push_back(Configuracao{proximo, i + 1, simbolo});
// Registra só a primeira queda e segue lendo. Parar daria a mesma
// resposta, mas o traço terminaria antes da cadeia e não mostraria o erro
// absorvendo o resto dela.
if (proximo == erro_ && execucao.posicaoDaQueda == std::string::npos) {
execucao.posicaoDaQueda = i;
execucao.simboloForaDoAlfabeto = foraDoAlfabeto;
}
atual = proximo;
}
execucao.aceitou = ehDeAceitacao(atual);
return execucao;
}
DicaNo código
Seguir lendo depois da queda é escolha da versão instrumentada, feita para a demonstração. A versão de produção responde sim ou não e encerra. Mesma tabela, mesma resposta.
Duas implementações do mesmo reconhecimento parecem excesso até a máquina responder algo inesperado. Aí o traço mostra a sequência de estados, e em segundos se vê quem errou, a máquina ou a expectativa. Sem ele, sobra imprimir variáveis dentro do laço. E a função extra fica fora do trecho que roda uma vez por caractere. Um limite, porém, nenhuma mensagem contorna. A máquina sabe que a cadeia não pertence e onde isso se decidiu, mas não sabe o que quem digitou queria escrever, informação que nunca esteve na entrada.
1.7 A teoria em execução: a máquina do sistema deste livro
A Peneira ganha aqui a máquina, e com ela o primeiro documento de decisão do percurso que traz uma conta em vez de uma preferência. São duas peças. O registro da escolha de representação traz a alternativa descartada e os números. O autômato propriamente dito traz a execução instrumentada e três máquinas projetadas à mão a partir de especificações em prosa.
1.7.1 A decisão de representação, com a conta escrita
A escolha foi a matriz densa, e o documento registra o que foi descartado, por quê, e sob que condições a decisão deve ser reexaminada. Ele começa reconhecendo a vantagem do que se descartou. Sem essa linha, seria propaganda com aparência de justificativa.
docs/03_representacao_transicao.md
# A representação da função de transição — decisão e a conta
Guardar a função de transição é a primeira escolha da Peneira cujo custo se mede
em bytes. Ela vem com a conta escrita, e não com uma preferência.
## O que foi escolhido
**Matriz densa**, indexada por estado e por coluna de símbolo. A coluna sai de um
mapeamento byte → coluna, calculado uma vez no construtor, e consultar uma
transição custa uma multiplicação, uma soma e um acesso a vetor.
A função é **total**. Existe um estado de erro absorvente, e toda posição da
tabela nasce apontando para ele. Quem monta a máquina declara só as transições que
existem, cada uma sobrescrevendo uma posição, e nunca precisa preencher o resto.
## A conta
Seja `n` o número de estados úteis e `m` o tamanho do alfabeto declarado. A
tabela tem `(n + 1) × m` posições, cada uma de `sizeof(Estado)` bytes:
bytes = (n + 1) × m × sizeof(Estado)
O `+ 1` é o estado de erro. Com `Estado` de 8 bytes nesta plataforma, os três
autômatos projetados à mão ocupam:
| Autômato | Estados úteis | Alfabeto | Posições | Bytes | Transições não-erro |
| ----------------- | ------------: | -------: | -------: | ----: | ------------------: |
| identificador | 2 | 37 | 111 | 888 | 63 |
| número com sinal | 4 | 13 | 65 | 520 | 43 |
| comentário | 3 | 28 | 112 | 896 | 30 |
Os números saem da própria demonstração, que chama `bytesDaTabela()` e
`transicoesDefinidas()` para cada máquina e imprime o resultado. Copiada à mão, a
tabela poderia divergir do código sem que nada acusasse, e uma conta errada com
cara de medida engana mais do que conta nenhuma.
**A coluna não é o byte.** Indexar a tabela pelo código do caractere daria 256
colunas por estado. Para o autômato de número, seriam 256 colunas em vez de 13,
quase vinte vezes mais memória para a mesma máquina. O mapeamento byte → coluna
custa um vetor de 256 entradas **por autômato**, e não por estado, e deixa de
pesar assim que a máquina passa de um punhado de estados.
## A alternativa descartada
**Mapa esparso**: uma tabela de dispersão que leva `(estado, símbolo)` ao destino
e guarda só as transições que existem.
Em memória, ele ganha, e a última coluna da tabela acima diz por quanto. O
autômato de comentário tem 112 posições e só 30 transições que não vão para o
erro: três quartos da tabela guardam o mesmo valor. O de número é o menos
desperdiçado dos três, com 43 de 65, e ainda assim um terço das posições dele vai
para o erro. As máquinas que a determinização vai produzir, dois módulos adiante,
são maiores, e nelas a proporção piora.
Descartamos o mapa mesmo assim, por duas razões que a memória não mede.
A primeira é o custo por símbolo consumido. O reconhecimento faz **uma** consulta
de transição para cada símbolo do texto de entrada, e a Peneira processa texto
inteiro. Trocar o acesso a vetor por um cálculo de hash multiplica o custo da
operação mais frequente do sistema por uma constante que não é pequena, e o
reconhecimento deixa de ser previsivelmente linear.
A segunda é a que o enunciado da tarefa antecipa, e pesa mais: **a tabela de
transição não é só estrutura interna do reconhecedor**. É também a forma do que o
sistema emite no fim, quando o objeto produzido tiver de carregar as máquinas
construídas a partir da descrição lida. Uma matriz densa é um bloco contíguo de
inteiros, que se grava e se carrega como está. Um mapa esparso teria de ser
serializado, e a escolha do formato voltaria no módulo de geração de código,
quando já não há tempo de refazer.
## O que fica em aberto, e onde volta
A escolha vale para as máquinas de agora. Quando a determinização produzir
máquinas com muitos estados sobre alfabetos largos, o desperdício da matriz densa
fica visível, e há uma saída intermediária conhecida: a **compressão por linhas
equivalentes**, em que estados com linhas de transição idênticas passam a
compartilhar uma linha só. O acesso continua em tempo constante, e boa parte da
memória volta.
A decisão fica adiada, com lugar marcado, e não esquecida. A conta se refaz no
módulo da minimização, com os números daquelas máquinas, e não com os destas três.
Dois pontos merecem sua atenção ao ler. Os números da tabela são impressos pelo programa, não copiados à mão. Uma tabela que divergisse do que o código reporta seria pior do que documento nenhum: teria a aparência de verificada. Resta a decisão adiada registrada no fim, com o ponto exato do percurso em que a conta deve ser refeita.
1.7.2 O autômato, campo a campo
A classe é a quíntupla virada estrutura de dados. Leia o cabeçalho ao lado da Definição 3.1, campo a campo. Os estados são os índices e o alfabeto é a cadeia declarada no construtor. A função de transição é a tabela, o estado inicial é um campo, o conjunto de aceitação é um vetor de marcas. Nada no cabeçalho sobra em relação à definição, e nada na definição falta no cabeçalho.
03_afd.h
// 03_afd.h — o autômato finito determinístico: a quíntupla como classe, e a
// execução que guarda o traço de configurações.
//
// A função de transição é total: um estado de erro absorvente, criado no
// construtor, é o destino de todo par (estado, símbolo) que ninguém declarou, e
// a execução nunca pergunta se a transição existe. A tabela é uma matriz densa
// indexada por estado e coluna; a coluna vem de um mapeamento byte -> coluna, e
// não do código do caractere, que daria 256 colunas por estado. A conta que
// sustenta a matriz está em docs/03_representacao_transicao.md.
#ifndef PENEIRA_03_AFD_H
#define PENEIRA_03_AFD_H
#include <cstddef>
#include <string>
#include <vector>
namespace peneira {
using Estado = std::size_t;
// Uma configuração é o par (estado corrente, posição na cadeia). A execução
// guarda a sequência delas, que é como a definição descreve o reconhecimento.
struct Configuracao {
Estado estado = 0;
std::size_t posicao = 0;
char simboloLido = '\0'; // o símbolo que levou a esta configuração
};
struct Execucao {
bool aceitou = false;
std::vector<Configuracao> passos;
// Posição do primeiro símbolo que levou ao erro; `std::string::npos` quando
// a execução nunca caiu nele.
std::size_t posicaoDaQueda = std::string::npos;
bool simboloForaDoAlfabeto = false;
};
class Afd {
public:
// `quantidadeDeEstados` conta só os estados úteis; o de erro recebe o índice
// seguinte. Toda posição da tabela nasce apontando para ele, e definir uma
// transição é sobrescrever uma dessas posições.
Afd(std::string alfabeto, std::size_t quantidadeDeEstados, Estado inicial);
// Autômato degenerado: só o estado de erro, alfabeto vazio, recusa tudo.
// Permite que um Afd seja membro de uma struct de resultado e receba o valor
// depois; a alternativa seria ponteiro ou optional em quem o devolve.
Afd();
void definirTransicao(Estado origem, char simbolo, Estado destino);
void definirTransicoes(Estado origem, const std::string& simbolos, Estado destino);
void marcarAceitacao(Estado estado);
void nomearEstado(Estado estado, std::string nome);
Estado estadoDeErro() const;
// Usados pela determinização (módulo 05): construir um AFD a partir de outro
// exige percorrer o alfabeto e saber onde a execução começa.
Estado estadoInicial() const;
const std::string& alfabeto() const;
Estado transicao(Estado origem, char simbolo) const;
bool ehDeAceitacao(Estado estado) const;
const std::string& nomeDoEstado(Estado estado) const;
// Consome a cadeia inteira e diz se parou em estado de aceitação.
bool aceita(const std::string& cadeia) const;
// O mesmo reconhecimento, guardando a configuração alcançada a cada símbolo.
Execucao executar(const std::string& cadeia) const;
// (estados + 1) x |alfabeto| x sizeof(Estado).
std::size_t bytesDaTabela() const;
// Posições cujo destino não é o erro. O que falta para o total é o que a
// matriz densa guarda a mais que um mapa esparso.
std::size_t transicoesDefinidas() const;
std::size_t quantidadeDeEstados() const;
std::size_t tamanhoDoAlfabeto() const;
std::string formatarTabela() const;
std::string formatarExecucao(const std::string& cadeia, const Execucao& execucao) const;
private:
std::size_t colunaDe(char simbolo) const;
static constexpr std::size_t kSemColuna = static_cast<std::size_t>(-1);
// recorte:inicio quintupla-como-estrutura
std::string alfabeto_;
std::vector<std::size_t> colunaDoByte_; // 256 entradas: byte -> coluna
std::vector<Estado> tabela_; // (estados+1) x |alfabeto|
// `char`, e não `bool`: vector<bool> empacota bits e não devolve referência
// de verdade.
std::vector<char> aceitacao_;
std::vector<std::string> nomes_;
Estado inicial_ = 0;
Estado erro_ = 0;
// recorte:fim quintupla-como-estrutura
};
// Três autômatos projetados à mão, cada um a partir de uma especificação em
// prosa. O gerador só chega no módulo 04; um executor já testado contra máquinas
// conhecidas separa, ali, erro de construção de erro de execução.
Afd afdIdentificador();
Afd afdNumeroComSinal();
Afd afdComentarioDeLinha();
} // namespace peneira
#endif // PENEIRA_03_AFD_H
03_afd.cpp
#include "03_afd.h"
namespace peneira {
namespace {
std::string preencher(const std::string& texto, const std::size_t largura) {
std::string resultado = texto;
while (resultado.size() < largura) {
resultado += ' ';
}
return resultado;
}
// Os símbolos de `inicio` a `fim`, pelo código do caractere; monta os alfabetos
// das três máquinas.
std::string faixa(const char inicio, const char fim) {
std::string simbolos;
for (int codigo = static_cast<unsigned char>(inicio); codigo <= static_cast<unsigned char>(fim);
++codigo) {
simbolos += static_cast<char>(codigo);
}
return simbolos;
}
} // namespace
Afd::Afd(std::string alfabeto, const std::size_t quantidadeDeEstados, const Estado inicial)
: alfabeto_(std::move(alfabeto)),
colunaDoByte_(256, kSemColuna),
aceitacao_(quantidadeDeEstados + 1, 0),
nomes_(quantidadeDeEstados + 1),
inicial_(inicial),
erro_(quantidadeDeEstados) {
// recorte:inicio coluna-nao-e-o-byte
for (std::size_t coluna = 0; coluna < alfabeto_.size(); ++coluna) {
const std::size_t byte = static_cast<unsigned char>(alfabeto_[coluna]);
colunaDoByte_[byte] = coluna;
}
// recorte:fim coluna-nao-e-o-byte
// recorte:inicio transicao-total-por-construcao
// Toda posição nasce apontando para o erro: quem monta a máquina declara só
// as transições que existem, e a função já sai total.
tabela_.assign((quantidadeDeEstados + 1) * alfabeto_.size(), erro_);
// recorte:fim transicao-total-por-construcao
for (std::size_t estado = 0; estado <= quantidadeDeEstados; ++estado) {
nomes_[estado] = "q" + std::to_string(estado);
}
nomes_[erro_] = "erro";
}
Afd::Afd()
: colunaDoByte_(256, kSemColuna), aceitacao_(1, 0), nomes_(1, "erro"), inicial_(0), erro_(0) {}
std::size_t Afd::colunaDe(const char simbolo) const {
return colunaDoByte_[static_cast<unsigned char>(simbolo)];
}
void Afd::definirTransicao(const Estado origem, const char simbolo, const Estado destino) {
const std::size_t coluna = colunaDe(simbolo);
if (coluna == kSemColuna || origem >= aceitacao_.size()) {
// Símbolo fora do alfabeto ou estado inexistente: retorna sem escrever, e
// o par continua indo para o erro. Lançar pegaria o erro de digitação na
// hora, mas obrigaria cada chamada de construção a tratar a falha.
return;
}
tabela_[origem * alfabeto_.size() + coluna] = destino;
}
void Afd::definirTransicoes(const Estado origem, const std::string& simbolos,
const Estado destino) {
for (const char simbolo : simbolos) {
definirTransicao(origem, simbolo, destino);
}
}
void Afd::marcarAceitacao(const Estado estado) {
if (estado < aceitacao_.size()) {
aceitacao_[estado] = 1;
}
}
void Afd::nomearEstado(const Estado estado, std::string nome) {
if (estado < nomes_.size()) {
nomes_[estado] = std::move(nome);
}
}
Estado Afd::estadoDeErro() const { return erro_; }
Estado Afd::estadoInicial() const { return inicial_; }
const std::string& Afd::alfabeto() const { return alfabeto_; }
// recorte:inicio tabela-densa-indexada
Estado Afd::transicao(const Estado origem, const char simbolo) const {
const std::size_t coluna = colunaDe(simbolo);
if (coluna == kSemColuna) {
return erro_;
}
return tabela_[origem * alfabeto_.size() + coluna];
}
// recorte:fim tabela-densa-indexada
bool Afd::ehDeAceitacao(const Estado estado) const { return aceitacao_[estado] != 0; }
const std::string& Afd::nomeDoEstado(const Estado estado) const { return nomes_[estado]; }
// diagrama:adiado quem só precisa do sim ou não é a bateria do AFN (04), a equivalência da determinização (05) e o marco 06; o marco 03 percorre pela executar(), a mesma travessia com o traço registrado
// recorte:inicio aceita-em-quatro-linhas
bool Afd::aceita(const std::string& cadeia) const {
Estado atual = inicial_;
for (const char simbolo : cadeia) {
atual = transicao(atual, simbolo);
}
return ehDeAceitacao(atual);
}
// recorte:fim aceita-em-quatro-linhas
// recorte:inicio queda-registrada-sem-parar
Execucao Afd::executar(const std::string& cadeia) const {
Execucao execucao;
Estado atual = inicial_;
execucao.passos.push_back(Configuracao{atual, 0, '\0'});
for (std::size_t i = 0; i < cadeia.size(); ++i) {
const char simbolo = cadeia[i];
const bool foraDoAlfabeto = colunaDe(simbolo) == kSemColuna;
const Estado proximo = transicao(atual, simbolo);
execucao.passos.push_back(Configuracao{proximo, i + 1, simbolo});
// Registra só a primeira queda e segue lendo. Parar daria a mesma
// resposta, mas o traço terminaria antes da cadeia e não mostraria o erro
// absorvendo o resto dela.
if (proximo == erro_ && execucao.posicaoDaQueda == std::string::npos) {
execucao.posicaoDaQueda = i;
execucao.simboloForaDoAlfabeto = foraDoAlfabeto;
}
atual = proximo;
}
execucao.aceitou = ehDeAceitacao(atual);
return execucao;
}
// recorte:fim queda-registrada-sem-parar
// recorte:inicio bytes-da-tabela
std::size_t Afd::bytesDaTabela() const { return tabela_.size() * sizeof(Estado); }
std::size_t Afd::transicoesDefinidas() const {
std::size_t total = 0;
for (const Estado destino : tabela_) {
if (destino != erro_) {
++total;
}
}
return total;
}
// recorte:fim bytes-da-tabela
std::size_t Afd::quantidadeDeEstados() const { return aceitacao_.size(); }
std::size_t Afd::tamanhoDoAlfabeto() const { return alfabeto_.size(); }
std::string Afd::formatarTabela() const {
// Por faixa de colunas com o mesmo destino, e não coluna a coluna: o
// alfabeto do identificador daria trinta e sete colunas por linha. Cada
// estado lista os destinos que não são o erro e os símbolos que levam a eles.
std::string texto;
texto += preencher("ESTADO", 14) + preencher("ACEITA", 8) + "TRANSICOES\n";
for (std::size_t estado = 0; estado < aceitacao_.size(); ++estado) {
texto += preencher(nomes_[estado], 14);
texto += preencher(aceitacao_[estado] != 0 ? "sim" : "nao", 8);
bool primeiro = true;
for (std::size_t coluna = 0; coluna < alfabeto_.size(); ++coluna) {
const Estado destino = tabela_[estado * alfabeto_.size() + coluna];
if (destino == erro_) {
continue;
}
// Estende a faixa enquanto a coluna seguinte levar ao mesmo destino:
// os dez dígitos saem numa entrada só.
std::size_t fimDaFaixa = coluna;
while (fimDaFaixa + 1 < alfabeto_.size() &&
tabela_[estado * alfabeto_.size() + fimDaFaixa + 1] == destino) {
++fimDaFaixa;
}
if (!primeiro) {
texto += ", ";
}
const std::size_t quantidade = fimDaFaixa - coluna + 1;
if (quantidade <= 3) {
// Até três símbolos, um a um: `+ -` escrito como faixa sugeriria
// um intervalo de códigos que não existe.
for (std::size_t i = coluna; i <= fimDaFaixa; ++i) {
if (i > coluna) {
texto += ' ';
}
texto += alfabeto_[i];
}
} else {
// A faixa é por posição no alfabeto declarado, não por código do
// caractere. A contagem entre colchetes impede que `a.._ [37]`
// seja lido como intervalo ASCII.
texto += alfabeto_[coluna];
texto += "..";
texto += alfabeto_[fimDaFaixa];
texto += " [" + std::to_string(quantidade) + "]";
}
texto += " -> " + nomes_[destino];
primeiro = false;
coluna = fimDaFaixa;
}
if (primeiro) {
texto += "(todas para erro)";
}
texto += '\n';
}
return texto;
}
std::string Afd::formatarExecucao(const std::string& cadeia, const Execucao& execucao) const {
std::string texto = " cadeia: \"" + cadeia + "\"\n";
texto += " configuracoes: ";
for (std::size_t i = 0; i < execucao.passos.size(); ++i) {
const Configuracao& passo = execucao.passos[i];
if (i > 0) {
texto += " -";
texto += passo.simboloLido;
texto += "-> ";
}
texto += nomes_[passo.estado];
}
texto += '\n';
texto += std::string(" resultado: ") + (execucao.aceitou ? "ACEITA" : "RECUSA");
if (!execucao.aceitou && execucao.posicaoDaQueda != std::string::npos) {
texto += " — caiu no erro na posicao " + std::to_string(execucao.posicaoDaQueda);
texto += execucao.simboloForaDoAlfabeto ? " (simbolo fora do alfabeto declarado)"
: " (simbolo valido, transicao inexistente)";
} else if (!execucao.aceitou) {
texto += " — consumiu a cadeia inteira e parou em estado nao final";
}
texto += '\n';
return texto;
}
// --- os três autômatos projetados à mão --------------------------------------
// Especificação: uma letra minúscula seguida de qualquer número de letras
// minúsculas, dígitos ou sublinhados. Dois estados: nada lido ainda, e a
// primeira letra já lida.
Afd afdIdentificador() {
const std::string letras = faixa('a', 'z');
const std::string digitos = faixa('0', '9');
Afd afd(letras + digitos + "_", 2, 0);
afd.nomearEstado(0, "inicio");
afd.nomearEstado(1, "corpo");
afd.definirTransicoes(0, letras, 1);
afd.definirTransicoes(1, letras, 1);
afd.definirTransicoes(1, digitos, 1);
afd.definirTransicao(1, '_', 1);
afd.marcarAceitacao(1);
return afd;
}
// Especificação: sinal opcional, ao menos um dígito e, opcionalmente, um ponto
// seguido de ao menos um dígito. Cada estado é uma resposta diferente a "o que
// falta para a cadeia ser válida?". `apos_ponto` não aceita: um número não
// termina em ponto.
Afd afdNumeroComSinal() {
const std::string digitos = faixa('0', '9');
Afd afd(digitos + "+-.", 4, 0);
afd.nomearEstado(0, "inicio");
afd.nomearEstado(1, "inteiro");
afd.nomearEstado(2, "apos_ponto");
afd.nomearEstado(3, "fracao");
afd.definirTransicao(0, '+', 0);
afd.definirTransicao(0, '-', 0);
afd.definirTransicoes(0, digitos, 1);
afd.definirTransicoes(1, digitos, 1);
afd.definirTransicao(1, '.', 2);
afd.definirTransicoes(2, digitos, 3);
afd.definirTransicoes(3, digitos, 3);
afd.marcarAceitacao(1);
afd.marcarAceitacao(3);
return afd;
}
// Especificação: duas barras e qualquer coisa até o fim da linha. O alfabeto é
// estreito (barra, espaço e minúsculas) para que a demonstração possa recusar
// por símbolo fora dele, e não só por transição inexistente.
Afd afdComentarioDeLinha() {
const std::string letras = faixa('a', 'z');
Afd afd("/ " + letras, 3, 0);
afd.nomearEstado(0, "inicio");
afd.nomearEstado(1, "uma_barra");
afd.nomearEstado(2, "no_comentario");
afd.definirTransicao(0, '/', 1);
afd.definirTransicao(1, '/', 2);
afd.definirTransicao(2, '/', 2);
afd.definirTransicao(2, ' ', 2);
afd.definirTransicoes(2, letras, 2);
afd.marcarAceitacao(2);
return afd;
}
} // namespace peneira
DicaAs três máquinas e o que cada uma expõe
As três máquinas construídas à mão cobrem o tópico de projeto a partir de especificações dadas, e cada uma foi escolhida por expor uma coisa distinta. A do identificador é a mais curta. Ela mostra que a quinta letra não pede estado próprio: dois estados bastam, porque só há duas situações a distinguir.
A do número com sinal carrega a armadilha do corpo do capítulo. É o estado alcançado depois do ponto e antes de qualquer dígito, em que a cadeia não é válida e ainda pode vir a ser. Quem esquece esse estado obtém uma máquina que aceita uma cadeia terminada em ponto, e a demonstração executa justamente esse caso negativo. O sinal, por sua vez, não cria estado: a transição volta ao próprio estado inicial, porque ler um sinal não altera em nada o que ainda falta.
A do comentário de linha tem alfabeto propositalmente estreito, e existe menos pelo que reconhece do que pelo contraste que permite. Com poucos símbolos declarados, é fácil submeter uma cadeia contendo um caractere que nem consta do alfabeto. Aí acontece a segunda forma de recusa. Ela é distinta da recusa por falta de transição, que a mesma demonstração exibe sobre outra entrada.
As três formas de recusa aparecem lado a lado na saída, e é essa justaposição que ensina. Uma cadeia é recusada porque o dígito, embora pertença ao alfabeto, não tem transição a partir do estado inicial. Outra, porque o caractere nem consta do alfabeto daquela máquina. E a terceira? Consome-se inteira sem jamais cair no erro, e ainda assim é recusada, por parar em estado não final. É essa que quem implementa esquece, e a que produz o defeito de aceitar cadeias incompletas.
1.8 Uma tabela que diz não e não sabe contar até dois
Espera aí: e a árvore do capítulo anterior? Continua sem consumidor, mas o executor que vai recebê-la já existe. A máquina lê cada símbolo uma vez, gasta exatamente um passo por caractere e não volta atrás. A especificação em prosa vira quíntupla, a quíntupla vira tabela, a tabela executa, e o tamanho dela se calcula antes da primeira linha de código. O reconhecedor escrito assim recusa entrada inválida como trabalho normal, e diz por que recusou.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
A["a máquina, escrita à mão,<br/>com a tabela medida"] --> B["construir a máquina<br/>a partir da expressão"]
A --> C["determinizar e reduzir<br/>ao menor número de estados"]
A --> D["provar que a classe<br/>não alcança uma linguagem"]
Três coisas ficam em aberto, todas com endereço. Construir a máquina a partir da expressão cumpre a primeira metade da equivalência de Kleene. Determinizar e reduzir ao menor número de estados cumpre a segunda, e transforma a caça às testemunhas em algoritmo. E existe uma segunda rota para mostrar que uma linguagem escapa da classe, sem depender do limite inferior. Até a primeira chegar, “construir um autômato” significa decidir situações, dar nome a elas e preencher a tabela à mão. Nada aqui foi medido em escala. O que ficou foi a fórmula, válida em qualquer escala.
ImportanteO critério para qualquer função total guardada em memória
Antes de implementar qualquer estrutura que guarde uma função total, escreva três números: posições, bytes por posição e a fração delas que vai repetir o valor padrão. Fração alta com escala pequena, o gasto se aceita. Se a escala vai crescer por um procedimento automático, o número anotado agora é a referência que dirá, mais tarde, se o crescimento estava previsto.
Em 1943, McCulloch e Pitts queriam explicar neurônios, e do artigo sobrou um elemento de dois estados que não guarda nada além de si. Oitenta e poucos anos depois, o mesmo elemento virou uma tabela de 888 bytes. Ela sabe dizer não, e não sabe contar até dois.
1.8.1 A máquina que ainda precisa nascer de uma expressão
A Peneira tem agora um executor verificado e três máquinas escritas à mão. Nenhuma delas nasceu de um padrão declarado por quem usa a linguagem: as três foram digitadas estado a estado, e a árvore que o arco anterior produziu continua sem consumidor. Os dois arcos seguintes fecham essa lacuna pelos dois lados, e nessa ordem — primeiro a construção que transforma a árvore em máquina, depois o procedimento que torna essa máquina determinística e a reduz.
A conta desta parte do percurso é o que vai medir aquele crescimento. A fórmula do consumo já está escrita, e o número que ela devolve para as três máquinas de agora cabe em três casas decimais. Quando a construção automática produzir máquinas com dezenas de estados sobre alfabetos largos, a mesma fórmula continuará valendo, com números muito maiores — e a pergunta na hora será se o limite que você estabeleceu foi atingido.
Antes de virar a página, faça um exercício sobre o seu próprio sistema. Pegue o padrão mais complicado que a sua linguagem precisará aceitar e escreva, em prosa, todas as situações que uma máquina teria de distinguir para reconhecê-lo — sem desenhar nada, sem contar estados. Depois conte quantas situações você escreveu e multiplique pelo tamanho do alfabeto que elas exigem, e por 8 bytes. O resultado é o piso de memória do seu reconhecedor, e você o obteve antes de escrever uma linha de código.
O que construir no seu próprio projeto, com as três máquinas destas páginas como modelo, está nos enunciados a seguir.
Tarefa 1: Decidir a representação da função de transição
Escolha como armazenar a função de transição da máquina e justifique a escolha por escrito, dizendo quanto a representação ocupa em função do tamanho do alfabeto e do número de estados, e qual alternativa você descartou e por quê. Esta é a primeira decisão do percurso que cobra preço mensurável, e o hábito de registrar a conta será exigido de novo, em escala maior, no fecho do sistema.
A decisão tem alcance maior do que aparenta neste ponto. A tabela de transição é também a forma daquilo que o sistema vai produzir ao final, quando o objeto emitido precisar carregar as máquinas construídas a partir da descrição lida. Representá-la mal cobra duas vezes, e a segunda cobrança chega quando já não há tempo de refazer.
Tarefa 2: Executar uma máquina descrita à mão
Implemente a execução de uma máquina de estados, descrita à mão, sobre uma cadeia de entrada, reportando aceitação ou recusa. O gerador só existe no capítulo seguinte, e chegar lá com o executor já verificado separa dois erros que, juntos, são difíceis de distinguir: a máquina errada e a execução errada.
Trate explicitamente o símbolo para o qual não há transição prevista. É o caso que a definição formal costuma resolver com uma frase e que, no código, decide se o sistema recusa a cadeia ou termina de forma imprevisível diante de uma entrada que ninguém antecipou.