%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
Q0["q0<br/>nada lido"] -->|"letra maiúscula"| Q1["q1<br/>letra lida"]
Q1 -->|"dígito"| Q2["q2<br/>um dígito"]
Q2 -->|"dígito"| Q3["q3<br/>dois dígitos"]
Q3 -->|"dígito"| Q4["q4<br/>três dígitos<br/>aceita"]
1 Autômatos finitos determinísticos — Exercícios
Os três problemas abaixo cobram o vocabulário deste capítulo e nada além dele: a quíntupla, a função de transição total, o estado de erro absorvente, o reconhecimento escrito como sequência de configurações, o projeto de uma máquina a partir de uma especificação em prosa, a tabela de transição com o preço dela em bytes, e o limite inferior de estados que se demonstra exibindo prefixos distinguíveis. Nenhum deles pede programa escrito, e todos se resolvem com papel, lápis e a disposição de refazer uma multiplicação pequena duas vezes. Resolva na ordem: o segundo trabalha sobre a máquina que o primeiro constrói, e o terceiro precisa do método dos dois.
1.1 Exercício 1: O desenho que economizou as setas
Nível Básico
Um depósito identifica cada prateleira por uma etiqueta curta: uma letra maiúscula seguida de exatamente três dígitos — B204, X007, Q913. O leitor óptico passa ao reconhecedor um texto sobre o alfabeto declarado \Sigma com 36 símbolos, as 26 letras maiúsculas do alfabeto latino sem acento e os dez dígitos. Quem desenhou a máquina no papel escreveu apenas as setas que levam adiante, que é o hábito de todo mundo que desenha autômato à mão.
O desenho tem cinco estados e nenhuma seta para o erro. Ele é abreviação de um objeto completo, e o completamento é uma construção que preserva a linguagem reconhecida: acrescenta-se um estado que não pertence ao conjunto de aceitação, e todo par estado-símbolo sem destino passa a apontar para ele, inclusive os pares que partem dele mesmo. Um estado com essa propriedade — toda seta que sai volta para ele — chama-se absorvente.
O que peço de você: três respostas, nesta ordem. (a) Escreva a quíntupla completa da máquina depois do completamento, nomeando os cinco componentes um a um, dizendo quantos estados o conjunto passa a ter e qual é o conjunto de aceitação. (b) Execute o reconhecimento das três cadeias a seguir como sequência de configurações, escrevendo cada configuração como o par formado pelo estado corrente e pelo sufixo ainda não consumido, e diga, para cada uma, qual das três formas de recusa do capítulo se aplica ou por que ela é aceita: B204; B20; e B2O4, em que o terceiro símbolo é a letra O maiúscula, e não o dígito zero — eu mesmo já perdi uma tarde inteira com essa troca. (c) Conte o preço do completamento: quantas transições o desenho declara, quantas células a tabela completa tem ao todo, quantas dessas células existem apenas para dizer que não, e quantos bytes a tabela ocupa se cada destino for armazenado em 8 bytes. Apresente a fração de células que apontam para o erro e escreva ao lado o nome da máquina de que ela é fração.
Você terá terminado quando a quíntupla de (a) estiver com os cinco componentes nomeados, os três traços de (b) mostrarem o sufixo encolhendo símbolo a símbolo até a cadeia acabar — inclusive no traço que cai no erro e continua nele —, e a conta de (c) fechar com as parcelas visíveis, sem que nenhum número apareça sem a coisa que ele mede ao lado.
1.2 Exercício 2: O sinalizador que aceita demais, e a coluna que custa caro
Nível Intermediário
A máquina da etiqueta do problema anterior foi implementada por duas pessoas, em separado, e as duas versões passam nos mesmos casos de teste. A versão A percorre a cadeia inteira e, terminado o texto, pergunta se o estado alcançado pertence ao conjunto de aceitação. A versão B guarda um sinalizador booleano: sempre que a máquina entra num estado de aceitação, o sinalizador é levantado, e ao fim a resposta é o valor do sinalizador. As duas rotinas estão no diagrama, lado a lado.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
subgraph A["versão A — decide depois de consumir tudo"]
A1["estado recebe q0"] --> A2{"resta símbolo?"}
A2 -->|"sim"| A3["estado recebe delta(estado, símbolo)"]
A3 --> A2
A2 -->|"não"| A4{"estado pertence a F?"}
A4 -->|"sim"| A5["aceita"]
A4 -->|"não"| A6["recusa"]
end
subgraph B["versão B — sinalizador levantado no caminho"]
B1["estado recebe q0<br/>visitou recebe falso"] --> B2{"resta símbolo?"}
B2 -->|"sim"| B3["estado recebe delta(estado, símbolo)<br/>se estado pertence a F, visitou recebe verdadeiro"]
B3 --> B2
B2 -->|"não"| B4{"visitou é verdadeiro?"}
B4 -->|"sim"| B5["aceita"]
B4 -->|"não"| B6["recusa"]
end
A segunda metade do problema é de memória. A tabela de transição é uma matriz densa, e o número de colunas depende de como o símbolo lido vira índice. Um caminho indexa a coluna diretamente pelo valor do byte, o que dá 256 colunas por estado. O outro monta, na construção do autômato, um vetor de mapeamento de 256 entradas que traduz cada byte na coluna do alfabeto declarado, e a matriz passa a ter uma coluna por símbolo de \Sigma. Para a conta, suponha que cada destino ocupe 8 bytes e que cada entrada do vetor de mapeamento ocupe 1 byte. O consumo da matriz é B(n,k,b) = n \cdot k \cdot b, com n estados contados com o de erro, k colunas e b bytes por destino.
O que peço de você: quatro partes, na ordem de dependência. (a) Exiba uma cadeia sobre a qual as duas versões respondem coisas diferentes, mostre o percurso dela nas duas rotinas e diga qual das duas está de acordo com a definição de linguagem reconhecida deste capítulo. (b) Descreva, em uma frase e sem citar cadeia nenhuma, a linguagem que a versão B reconhece de fato, e explique por que ela coincide com a linguagem pretendida em todos os casos de teste curtos que alguém escreveria à mão. (c) Calcule, pelos dois caminhos de indexação, o consumo em bytes da tabela da máquina da etiqueta completada: o total com 256 colunas, o total com as colunas do alfabeto declarado, o custo do vetor de mapeamento, a economia líquida e a razão entre os dois totais. Diga qual das três variáveis da fórmula está sob controle direto de quem implementa e que limite a escolha de 2 bytes por destino impõe ao número de estados. (d) Compare a matriz densa com a alternativa de guardar apenas as transições que não vão para o erro num mapa esparso. Diga qual das duas ganha em memória nesta máquina e por quanto, qual ganha no custo de consultar um símbolo e por quê, e qual dos dois critérios pesa mais quando a consulta acontece uma vez para cada símbolo do texto de entrada. Termine nomeando o que a escolha pela matriz densa custa.
Você terá terminado quando a cadeia de (a) vier com os dois percursos escritos, (b) descrever a linguagem da versão B sem se apoiar num exemplo, os cinco números de (c) estiverem cada um com a coisa que mede ao lado, e (d) apresentar a comparação com a vantagem da opção descartada dita primeiro, e não como se a opção adotada ganhasse em tudo.
1.3 Exercício 3: O campo de conferência que ninguém consegue lembrar
Nível Desafiador
Uma cooperativa de abastecimento de água recebe, por telemetria, um arquivo com uma linha por medidor instalado. O formato da linha tem três campos, e o alfabeto declarado \Sigma tem 13 símbolos: os dez dígitos, a letra M, a cerquilha e o sinal de igual. O primeiro campo é a letra M seguida do número de série do medidor, que é uma sequência de um ou mais dígitos sem comprimento máximo declarado — os medidores antigos do parque instalado têm série de quatro dígitos e os novos têm doze. O segundo campo é a cerquilha seguida da leitura, uma sequência de um ou mais dígitos. O terceiro campo é o sinal de igual seguido de um campo de conferência, que repete, dígito por dígito, o número de série declarado no primeiro campo. A linha M4071#00238=4071 está no formato; M4071#00238=4072 não está.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
C1["campo 1<br/>M seguido do número de série<br/>um ou mais dígitos, sem teto declarado"]
C2["campo 2<br/>cerquilha seguida da leitura<br/>um ou mais dígitos"]
C3["campo 3<br/>igual seguido da conferência<br/>repete o campo 1 dígito por dígito"]
C1 --> C2 --> C3
C3 -.->|"tem de coincidir, dígito por dígito, com"| C1
Antes de decidir o que fazer com o terceiro campo, a equipe precisa de uma máquina para o pedaço que sobra sem ele, e de um argumento que diga por que o número de estados escolhido basta. O instrumento desse argumento é o limite inferior de estados: dois prefixos são distinguíveis quando existe uma continuação, chamada testemunha, tal que exatamente uma das duas cadeias resultantes pertence à linguagem — e a testemunha pode ser a cadeia vazia. Exibida uma família de prefixos dois a dois distinguíveis com k membros, todo autômato finito determinístico que reconheça a linguagem tem pelo menos k estados. A exigência de que os prefixos sejam dois a dois distinguíveis tem consequência prática: a distinguibilidade não se propaga, e separar o primeiro do segundo e o segundo do terceiro nada diz sobre o primeiro e o terceiro.
O que peço de você: uma análise em quatro partes, escrita em prosa. (a) Projete um autômato finito determinístico para o formato sem o terceiro campo, isto é, para as linhas compostas apenas do primeiro e do segundo campos. Apresente a quíntupla com o estado de erro já incluído, descreva em uma frase o que cada estado útil lembra do que já foi lido, e calcule o número de células da tabela, quantas delas apontam para o erro e o consumo em bytes a 8 bytes por destino. (b) Justifique que o conjunto de estados úteis que você escolheu é suficiente e não pode ser menor: exiba uma família de prefixos dois a dois distinguíveis com tantos membros quantos são os seus estados úteis e, para cada par, escreva a testemunha que os separa. Ao menos um dos pares se separa pela cadeia vazia; diga qual e por quê. (c) Agora o formato inteiro, com o campo de conferência. Mostre que nenhum autômato finito determinístico o reconhece: construa uma família infinita de prefixos dois a dois distinguíveis, exiba a testemunha que separa dois membros quaisquer dela escrevendo-a em função dos prefixos escolhidos, e conclua pelo limite inferior de estados. Em seguida responda a um integrante da equipe que propõe resolver o impasse dando mais estados à máquina — dez mil, um milhão, o quanto for preciso —, explicando por que a proposta falha em princípio, e não por falta de memória disponível. (d) A equipe considera uma saída: limitar por norma o número de série a exatamente quatro dígitos, o que devolve o formato inteiro à classe deste capítulo. Mostre que essa versão limitada exige pelo menos dez mil estados, exibindo a família de prefixos que estabelece o número, e calcule o consumo mínimo da tabela de transição correspondente, em bytes, com o alfabeto de 13 símbolos e 8 bytes por destino.
Feche com um parágrafo de julgamento, que é o que amarra as quatro partes. A cooperativa tem três caminhos: limitar a série a quatro dígitos e pagar a conta de (d); manter a série livre e abandonar a classe deste capítulo, usando um reconhecedor com memória sem teto; ou aceitar as linhas sem conferir o terceiro campo, deixando a verificação para outro ponto do sistema. Diga o que cada caminho custa, quem paga a conta em cada um deles — inclusive os medidores de série longa já instalados, cujas linhas passariam a ser recusadas —, e o que a mensagem de recusa precisa dizer para que quem opera o sistema saiba se a linha foi rejeitada por um símbolo fora do alfabeto, por um símbolo válido em posição inválida ou por ter acabado antes da hora. Apresente o caminho que você escolher com o preço escrito ao lado.
Você terá terminado quando a máquina de (a) vier com o que cada estado lembra dito em português, todos os pares de (b) tiverem testemunha nomeada, a família de (c) for infinita e a testemunha estiver escrita em função dos prefixos, o número de (d) vier da família exibida e não de estimativa, e o parágrafo final atribuir cada custo a alguém concreto.
Três hábitos de método atravessam os problemas acima. O primeiro: diante de qualquer especificação em prosa, pergunte antes de desenhar o que a máquina precisaria lembrar ao chegar em cada ponto do texto, porque quem só sabe em que estado está não sabe quantas vezes já entrou nele — e essa frase, que parecia figura de linguagem, é o critério que decide se o requisito cabe na classe. O segundo: nunca conclua que uma linguagem está fora da classe por não ter conseguido desenhar a máquina; a incapacidade de encontrar prova apenas que você não encontrou, e o instrumento que prova impossibilidade é a família infinita de prefixos dois a dois distinguíveis, com a testemunha exibida. O terceiro: sempre que decidir uma representação, faça a conta antes e escreva o resultado ao lado da alternativa que você descartou; medir e otimizar são coisas diferentes, e uma decisão registrada com o número ao lado é revisitável, enquanto uma decisão tomada de olho vira, alguns capítulos depois, o jeito como sempre foi feito.