%%{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 — Resumo
Versão de revisão. Ela recompõe o percurso inteiro depressa e não substitui a primeira leitura. As definições aparecem aqui na forma mais curta que ainda é correta. As demonstrações passo a passo e as três tabelas contadas byte a byte ficam na versão completa deste capítulo e no capítulo do livro.
Um campo de formulário aceita nomes de variável. Você digita valor_2 e ele responde sim; digita 2valor e a resposta vem já no primeiro caractere. Por trás das duas respostas há uma consulta a uma tabela por caractere, e 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.
O capítulo anterior deixou uma árvore de operadores e 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, 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 — não há ali uma linha sobre reconhecer texto. A proposta trata cada neurônio como elemento de dois estados, com disparo tudo-ou-nada. O tecido contínuo vira um sistema discreto, com uma configuração por combinação de células ativas, e o que é finito cabe numa tabela: linha por configuração, coluna por estímulo, célula seguinte a cada cruzamento. Do artigo de 1943 fica só isso — o elemento de dois estados.
Em dezembro de 1951, Stephen Cole Kleene escreveu na RAND Corporation o memorando RM-704, Representation of events in nerve nets and finite automata, publicado em 1956 nas páginas 3 a 41 de Automata Studies, organizado por Claude E. Shannon e John McCarthy. Kleene mostrou que sua notação regular descreve os mesmos comportamentos daquelas redes. Dois formalismos de tradições diferentes coincidindo sugere uma classe natural, não um recorte de conveniência — mas a tradução ainda está por construir nos dois sentidos: da expressão para a máquina, e de 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 perguntas, e a definição escreve cinco respostas.
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. A especificação em português não fala de estado, tabela ou erro — o trabalho mora na tradução. A definição também decide pelo que cala: não exige estados alcançáveis, aceita F vazio ou igual a Q, mas fixa um único estado inicial. 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. Todo par de estado e símbolo tem destino. Um desenho em que nada sai de inicio pelos dígitos não descreve uma máquina que “trava” — descreve, de forma abreviada, um dígito que leva a um estado sem volta.
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).
%%{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
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, uma cadeia caída no erro poderia terminar em F, e o completamento mudaria a linguagem. Nem todo absorvente é erro: na linguagem das cadeias que contêm ab, o estado alcançado depois do ab absorve e aceita ao mesmo tempo.
No código de referência da Peneira, a totalidade nasce por construção: a tabela inteira começa apontando para o erro, e definir uma transição é abrir exceção a essa regra.
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
A estrutura guarda cinco campos que são a quíntupla escrita em C++, mais o campo do erro que o completamento exige e o vetor de nomes que só serve à apresentação do traço.
03_afd.cpp
DicaNo código
A tabela nasce apontando inteira para o estado de erro, e o construtor sobrescreve célula a célula só as transições declaradas — a totalidade sai de graça, sem checagem em tempo de consulta.
Confira sempre nos dois sentidos, quando uma definição virar estrutura. Componente sem campo é implementação faltando; campo sem componente ou é acessório de apresentação — como o vetor de nomes, que serve só para o traço dizer inicio -2-> erro em vez de 0 -2-> 2 — ou a estrutura reconhece outra coisa. O que a definição não faz, o código faz por ela — e cobra.
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. Esse par 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, e o estado deixa de mudar depois do primeiro. Falta no par o que já foi lido: o prefixo some ao ser consumido, e dele só o estado sobrevive. Guardar o já-lido tornaria a máquina outra coisa, de outra classe, sem finitude. Na implementação, copiar o sufixo a cada passo tornaria quadrático um reconhecimento linear; guarde a posição, que carrega a mesma informação sem copiar nada a cada volta do laço.
%%{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, ε)"]
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.
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. Essa terceira propriedade separa esta máquina dos motores de busca com retrocesso do capítulo anterior — sem caminho na conta, não há por onde voltar. E sobre n símbolos são exatamente n passos: o tempo é linear desde que consultar \delta custe tempo constante.
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). Vale \hat{\delta}(q,w) = p se e somente se (q, w) \vdash_M^{*} (p, \varepsilon).
O caso base dá um critério de meio segundo: a cadeia vazia pertence à linguagem se e somente se q_0 \in F. É por isso que a máquina de nomes recusa a cadeia vazia sem regra especial.
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, nunca os intermediários. Aí está o atalho tentador que a máquina não deveria tomar: guardar um sinalizador — “já passei por aceitação” — e responder sim no fim se ele estiver ligado. Rode o atalho sobre 42. na máquina de números: os dois dígitos passam por inteiro, que aceita, e o ponto leva a apos_ponto, que não aceita. A máquina correta recusa; a do sinalizador aceita, como o fiscal que aprova a obra porque um dia ela esteve de pé. A versão defeituosa reconhece outra linguagem, a das cadeias com algum prefixo aceito, e as duas só divergem quando uma cadeia válida pode ser continuada até ficar inválida — o caso de números e nomes qualificados.
03_afd.cpp
DicaNo código
Repare no lugar do teste de aceitação: fora do laço, feito uma vez. Perguntar por F a cada volta responderia à pergunta do sinalizador, que é a defeituosa.
O laço do projeto só troca o estado corrente e testa a aceitação uma vez, com a entrada acabada. Fica uma dívida de vocabulário: “regular” ganhou aqui uma segunda definição, por máquina, além da que o capítulo anterior deu por expressão. As duas descrevem as mesmas linguagens, mas a prova ainda está por fazer, e tratá-las como sinônimo antecipa 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ó. Se u e v chegam ao mesmo estado, \hat{\delta}(q_0,u) = \hat{\delta}(q_0,v), então qualquer continuação z leva ao mesmo lugar: \hat{\delta}(q_0,uz) = \hat{\delta}(q_0,vz). 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, e a máquina esqueceu que uma tinha um caractere e a outra, cinco.
Na máquina de números — sinal opcional, ao menos um dígito, opcionalmente ponto seguido de ao menos um dígito — são quatro estados úteis. Três aparecem sem esforço: inicio, onde falta tudo; inteiro, com dígito lido; fracao, com dígito depois do ponto. O quarto é apos_ponto: ponto lido, nenhum dígito ainda, cadeia inválida e ainda podendo vir a ser válida.
%%{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
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; sem esse estado, a máquina aceita a cadeia cortada no meio.
Antes de seguir. Uma especificação pede cadeias de a e b com quantidade par de a. Que distinção do passado o resto da entrada ainda pode cobrar, e quantos estados úteis ela exige?
Esse teste informal tem versão exata, e ela olha a linguagem, não uma máquina em particular.
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.
Na máquina de números, 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. Acontece que a testemunha certa quase nunca é a primeira que você tenta: aqui é +5, número sozinho, enquanto 4.+5 fica de fora. Os prefixos são cadeias quaisquer, válidas ou não: 2x conta, porque leva ao erro, e o erro conta.
AvisoDistinguir não é transitivo
Se u se separa de v e v se separa de w, nada se conclui sobre u e w. 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 é a casa dos pombos: numa máquina com menos de k estados, dois dos k prefixos caem no mesmo estado; sendo distinguíveis, existe z com resposta diferente para uz e vz, mas a máquina, partindo do mesmo estado, responde igual — contradição. Com os parênteses balanceados, (, ((, ((( e assim por diante se separam dois a dois pela testemunha de fechamentos, e nenhuma quantidade finita de estados basta: a linguagem fica fora da classe.
%%{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"]
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. Não prova que a sua máquina seja mínima — falta o algoritmo de minimização, que chega com a determinização. E exibir uma quantidade finita de prefixos distinguíveis não tira a linguagem da classe; a impossibilidade pede família infinita.
Esse resultado é a metade fraca do teorema de Myhill–Nerode, publicado por Anil Nerode em 1958 (Proceedings of the American Mathematical Society, v. 9, n. 4, p. 541–544) e por Michael O. Rabin e Dana Scott em 1959 (IBM Journal of Research and Development, v. 3, n. 2, p. 114–125). A contribuição de John Myhill está num relatório técnico de 1957, de circulação restrita.
Os parênteses tornam isso concreto: nenhuma quantidade finita de estados guarda a profundidade de abertura já vista, porque quem só sabe em que estado está não sabe quantas vezes já entrou nele.
1.4 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: uma linha por estado, uma coluna por símbolo, e o destino de (q,a) na posição q \cdot k + c. Cada consulta é uma multiplicação, uma soma e uma leitura de vetor — sem busca, sem comparação, custo igual em toda posição.
%%{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
03_afd.cpp
DicaNo código
A aritmética de índice é a função de transição escrita em vetor. O teste anterior a ela trata do que a matemática ignora: caractere fora do alfabeto, que num arquivo real sempre pode aparecer.
A alternativa — tabela de dispersão de pares (q,a) para destino, com o erro implícito na ausência de chave — ganha em memória, e de longe: as três máquinas daqui definem entre um quarto e dois terços das posições. O descarte, porém, tem duas razões, e nenhuma é memória. A consulta acontece uma vez por caractere da entrada, a operação mais frequente de quem processa texto, e trocar vetor por dispersão multiplica esse custo. E a matriz densa é também o formato do que o sistema emite no fim — grava-se sem tradução.
A coluna de um símbolo vem de um vetor montado no construtor:
03_afd.cpp
DicaNo código
Esse vetor traduz byte em coluna uma única vez, no construtor, e é essa tradução que evita indexar a tabela pelos 256 valores possíveis de um byte.
Indexar direto pelo byte daria 256 colunas por estado; na máquina de números, quase vinte vezes a memória necessária para 13 símbolos reais. O mapeamento custa 256 entradas por autômato, não por estado, e traz um efeito colateral: byte fora do alfabeto não tem coluna, e a consulta precisa devolver o erro antes de calcular o índice.
B(n,k,b) = n \cdot k \cdot b
São n estados, k símbolos e b bytes por destino. Dobrar o alfabeto dobra a tabela; um estado a mais acrescenta uma linha inteira.
AvisoCom ou sem o estado de erro
Aqui n inclui o estado de erro. O registro de decisão do projeto usa (n+1) \times m, com n contando só os estados úteis. As contas batem: (2{+}1)\times 37 = 111, (4{+}1)\times 13 = 65, (3{+}1)\times 28 = 112.
Com destinos de 8 bytes, as três máquinas do projeto de referência 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 |
A de comentário tem um estado útil a menos que a de números, e ainda assim gasta mais bytes, porque ali pesa o alfabeto — o fator que quem projeta olha por último. Nenhum desses números foi copiado à mão para esta tabela: eles saem do programa de referência, que os calcula e os imprime a cada execução, e é assim que a conta se confere sem depender de ninguém somar de novo:
03_afd.cpp
DicaNo código
O que a função conta é convenção de implementação, não propriedade matemática: célula “definida” quer dizer destino diferente de erro_, escolha de quem programou, não da quíntupla.
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 fração depende de quão largo é o alfabeto diante do que a máquina usa, então percentual desses vem sempre com o nome da máquina ao lado. Dos três fatores, só b está na mão de quem implementa: destinos de 2 bytes dividem a tabela por quatro, com teto de 65.536 estados. Fica registrada uma saída adiada — estados de linhas idênticas podem compartilhar uma linha só —, útil porque a determinização pode gerar estados em número exponencial no da máquina de partida.
1.5 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 diferente. Uma máquina completa recusa de três maneiras.
%%{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. 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. As duas têm culpado com endereço. A terceira nunca passa pelo erro: 42. consome os três símbolos e para em apos_ponto, que não aceita — o culpado é o que ninguém escreveu. Toda queda no erro leva à recusa, mas nem toda recusa passa pelo erro. E a máquina de comentário aceita // sozinho: passa por inicio e uma_barra, para em no_comentario, que é de aceitação, porque “qualquer coisa até o fim da linha” inclui coisa nenhuma.
Uma pergunta antes de seguir
Cada recusa se reconhece por uma pergunta com resposta pronta na estrutura: o símbolo tem coluna? A célula aponta para o erro? Consumida a cadeia, o estado está em F? Qual dessas três perguntas o seu sistema deixa de fazer hoje, respondendo com uma mensagem só, “entrada inválida”?
Diante da recusa, o reconhecedor pode devolver a informação, com o que sabe sobre o ponto da falha, ou lançar exceção e encerrar ali. Num sistema que testa vários padrões na mesma posição — o caso da Peneira —, abortar no primeiro símbolo estranho derruba a consulta inteira; devolver a recusa como valor concentra a decisão em quem tem contexto. Compare encontrado '.' com esperava-se um dígito após o ponto decimal: as duas são verdadeiras, só a segunda é acionável, e o lado esperado 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.
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 consumindo depois da queda é escolha da versão instrumentada, feita para deixar o traço completo. A versão de produção responde e para ali, com a mesma tabela por trás.
A execução instrumentada do projeto registra a primeira queda, com posição e se o símbolo estava fora do alfabeto, e continua consumindo a cadeia — escolha da versão de demonstração; a de produção responde e encerra, com a mesma tabela e a mesma resposta. 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.
1.6 Uma tabela que diz não e não sabe contar até dois
%%{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"]
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 — símbolo sem transição, símbolo fora do alfabeto, ou fim de cadeia num estado que nunca aceitou.
Três coisas ficam em aberto, todas com endereço. Construir a máquina a partir da expressão regular 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 do teorema anterior em algoritmo. E existe uma segunda rota para mostrar que uma linguagem escapa da classe regular, sem depender do limite inferior por prefixos distinguíveis. Guarde também os três limites que este percurso deixou escritos, porque eles voltam como pergunta antes de voltar como algoritmo: nenhuma máquina para uma linguagem tem menos estados do que o número de prefixos dois a dois distinguíveis que ela admite; nenhuma quantidade finita de estados alcança os parênteses balanceados; e nenhuma mensagem de erro adivinha a intenção de quem digitou.
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 — e o seu próprio projeto carrega a mesma pergunta: quantas situações a sua especificação obriga a distinguir, e quantos bytes elas custam?