Uma máquina que reconhece números com sinal recebe três cadeias, fileiras de símbolos: -240.75, 42. e ++5. Entre um símbolo e o seguinte, ela guarda só o estado, a situação em que está. Ela aceita a primeira e recusa as outras duas. Em ++5, o segundo símbolo a leva ao estado de erro. Dali ela não sai. Em 42., ela lê os três símbolos sem passar pelo erro, e recusa mesmo assim.
A regra da máquina, chamada especificação, cabe numa linha: sinal opcional, ao menos um dígito, parte fracionária opcional, que é um ponto com ao menos um dígito depois. Dela saem cinco estados úteis, fora o de erro, e dois deles são fáceis de esquecer. Executar a máquina pronta é trabalho mecânico: uma consulta a uma tabela por símbolo, só com o estado atual e o símbolo lido. Projetá-la é escrevê-la a partir da regra, e exige decidir o que do passado ainda fará diferença.
1.1 Três ideias que sustentam a máquina
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.
A definição chama a máquina pelo nome formal. Quíntupla é uma lista de cinco coisas, e o alfabeto, a dos símbolos permitidos. A primeira ideia está em \delta : Q \times \Sigma \to Q: lê-se “delta recebe um estado e um símbolo e devolve um estado”. A função é total: cada par tem destino. O que o desenho deixa sem seta vai para o erro. A cadeia é aceita quando o estado alcançado depois do último símbolo está em F.
A segunda ideia diz o que um estado significa. Se dois prefixos, pedaços iniciais de cadeia, chegam ao mesmo estado, qualquer continuação leva os dois ao mesmo estado e à mesma resposta. Cada estado nomeia um grupo de passados que a máquina já não distingue, e projetar é decidir quais distinções do passado a continuação ainda pode cobrar. Onde a especificação diz “opcional, mas, se presente, obrigatório”, existe um estado intermediário que nunca aceita: ele guarda um compromisso ainda não cumprido.
A terceira ideia dá um mínimo de estados, o limite inferior: vamos chamá-lo de piso. Dois prefixos são distinguíveis quando alguma continuação, a testemunha, põe exatamente um deles na linguagem, o conjunto das cadeias que valem. Com k prefixos dois a dois distinguíveis, nenhum divide estado com outro, e toda máquina que reconhece a linguagem tem pelo menos k estados. Nos parênteses balanceados, (, ((, ((( e assim por diante se separam dois a dois pela sequência de fechamentos de um deles. A família é infinita, nenhuma quantidade finita de estados basta, e nenhum autômato finito determinístico reconhece a linguagem.
1.2 A máquina de números com sinal, executada
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
I["inicio<br/>não aceita"] -->|"+ -"| S["sinal<br/>não aceita"]
I -->|"dígito"| N["inteiro<br/>aceita"]
S -->|"dígito"| N
N -->|"dígito"| N
N -->|"ponto (.)"| P["apos_ponto<br/>não aceita"]
P -->|"dígito"| FR["fracao<br/>aceita"]
FR -->|"dígito"| FR
Figura 1: A máquina de números com sinal: o sinal leva a sinal, estado próprio que só lê dígito, e apos_ponto espera o dígito depois do ponto. Cada seta de rótulo dígito vale por dez setas, uma para cada dígito, e a de rótulo + -, por duas. As setas omitidas vão todas ao estado de erro.
O alfabeto tem 13 símbolos: os dez dígitos, +, - e .. Os traços vêm de uma execução. Cada seta de configuracoes traz o símbolo lido, e em ---> ele é o -; a posição conta a partir de zero.
cadeia: "-240.75"configuracoes: inicio ---> sinal -2-> inteiro -4-> inteiro -0-> inteiro -.-> apos_ponto -7-> fracao -5-> fracaoresultado: ACEITAcadeia: "42."configuracoes: inicio -4-> inteiro -2-> inteiro -.-> apos_pontoresultado: RECUSA — consumiu a cadeia inteira e parou em estado nao finalcadeia: "++5"configuracoes: inicio -+-> sinal -+-> erro -5-> erroresultado: RECUSA — caiu no erro na posicao 1 (simbolo do alfabeto, transicao para o erro)
Em ++5, o segundo + é símbolo do alfabeto, mas de sinal a transição dele vai ao erro. É a seta que o desenho omite e que, na função total, existe. Antes e depois do sinal a máquina espera um dígito, e ainda assim sinal pede estado próprio. A continuação +5 separa as duas situações. Lida a partir de inicio, forma +5, que é número. Depois de um sinal, forma ++5, que não é. O prefixo vazio e + são distinguíveis, e por isso ocupam estados diferentes.
1.3 Onde a máquina contraria o palpite
O traço de 42. desmonta dois atalhos. O primeiro aceita a cadeia por ter passado por F. 42. atravessa inteiro, que aceita, e uma máquina com um sinalizador de “já passei por F” responderia sim, reconhecendo outra linguagem: a das cadeias com algum prefixo aceito. O segundo supõe que toda recusa passa pelo erro, e 42. é recusada sem tocar nele: falta um dígito que ninguém escreveu.
Quem conta três ou quatro estados úteis na máquina de números deixa de fora os de compromisso pendente. Funda apos_ponto com inteiro e a máquina aceita 42.. Devolva + e - a inicio e a tabela poupa uma linha, mas a máquina passa a aceitar ++5 e +-5.
A testemunha pode ser a cadeia vazia, \varepsilon, e é a primeira a tentar: ela separa 4 de 4., porque só 4 é número. A vazia também separa 4. de 45. Espere antes de encadear os dois pares e concluir que 4 e 45 se separam: os dois chegam a inteiro, e continuação nenhuma os distingue. O piso exige uma testemunha para cada par, e procurá-las é o primeiro passo do projeto: o desenho só mostra os estados já pensados, e a testemunha acha o que falta.
1.4 Três previsões para conferir
Responda antes de abrir cada bloco.
Primeiro, simular. Que sequência de estados a máquina de números percorre sobre 7.2., e qual é o veredito?
DicaResposta
inicio -7-> inteiro -.-> apos_ponto -2-> fracao -.-> erro. Recusa, com queda no erro na posição 3: o segundo . pertence ao alfabeto, mas de fracao só o dígito leva adiante. O diagrama omite essa seta; a totalidade de \delta a manda ao erro.
Depois, projetar. Sobre o alfabeto dos dez dígitos mais a letra e, uma especificação pede um ou mais dígitos seguidos, opcionalmente, de e e de um ou mais dígitos. Quantos estados úteis precisa ter uma máquina que a reconheça?
DicaResposta
Quatro. Os prefixos \varepsilon, 1, 1e e 1e1 são dois a dois distinguíveis. A testemunha vazia separa (\varepsilon, 1), (\varepsilon, 1e1), (1, 1e) e (1e, 1e1), porque só 1 e 1e1 pertencem à linguagem. A testemunha e1 separa (1, 1e1), e 1e1 separa (\varepsilon, 1e): nos dois pares, 1e1 pertence e 1e1e1 não. Os quatro ainda podem virar cadeia aceita, então ocupam estados úteis.
Uma máquina com esse número aceita em inteiro e expoente e manda ao erro o que falta nesta lista: inicio vai a inteiro por dígito; inteiro fica em si por dígito e vai a apos_e pela letra e; apos_e vai a expoente por dígito; expoente fica em si por dígito.
Por fim, uma testemunha. Qual separa os prefixos 4 e 4.5 na máquina de números?
DicaResposta
Qualquer cadeia com dígitos opcionais, um ponto e ao menos um dígito depois dele, como .5 ou 5.5. 4 e 4.5 pertencem à linguagem, então a vazia falha, e dígitos também, porque 45 e 4.55 são aceitas. Com .5, 4.5 é aceita e 4.5.5 cai no erro no segundo ponto.
1.5 Para ir além
No material, “Um modelo de neurônio que virou quíntupla” conta a origem do modelo, num artigo de 1943. “Sete passos para valor_2, e nenhum de volta” executa uma máquina como sequência de configurações. “O que a máquina precisa lembrar” demonstra o limite inferior e prova que os estados bastam. “A função total vira memória” mede a tabela em bytes, e “Três jeitos de dizer não” separa as três formas de recusa e a mensagem de cada uma.