%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
S4((4<br/>inicial)) -->|ε| S0((0))
S4 -->|ε| S5(((5<br/>aceitação)))
S0 -->|a| S1((1))
S1 -->|ε| S2((2))
S2 -->|b| S3((3))
S3 -->|ε| S5
S1 -->|ε| S0
1 Autômatos não determinísticos e a construção de Thompson — Exercícios
Os três problemas a seguir cobram o que este módulo ensina: a máquina com transições vazias, a construção de Thompson regra por regra, o fecho vazio, a simulação que carrega um conjunto de estados por símbolo lido e o custo que se conta antes de construir qualquer coisa. Nenhum pede programa escrito. Todos se resolvem com papel e lápis, e cada um traz uma conta curta, que você confere por outra conta. Resolva na ordem: o primeiro testa a construção, o segundo testa a simulação e o terceiro mede o que as duas custam.
1.1 Exercício 1: A máquina de (ab)* desenhada à mão
Nível Básico
Uma pessoa desenhou à mão a máquina de Thompson do padrão (ab)*, isto é, a máquina que a construção de Thompson monta para ele, e pediu que alguém conferisse o desenho antes de usá-la. Para conferir, você precisa das regras da construção, repetidas aqui. A máquina é feita de estados, as situações em que ela pode estar, e de transições, as setas de um estado a outro. A construção percorre a árvore do padrão, em que cada trecho dele é um nó, e devolve para cada nó um bloco: um pedaço de máquina com um estado de entrada e um de saída. Cada folha, que é um nó sem nada pendurado, cria dois estados e uma transição. A concatenação, que cola um trecho no outro, não cria estado: acrescenta uma transição vazia da saída do primeiro bloco para a entrada do segundo. Transição vazia é a seta que a máquina atravessa sem ler nada e que o desenho marca com \varepsilon. Vamos chamar de catraca a transição que lê um símbolo e de corredor a transição vazia.
O operador * repete zero ou mais vezes o trecho do padrão a que se aplica. Aplicado ao bloco desse trecho, de entrada e_1 e saída s_1, ele cria dois estados novos, a entrada e e a saída s do bloco novo, e quatro transições vazias: de e para e_1 (uma vez ou mais), de e para s (zero vezes), de s_1 para e_1 (de novo) e de s_1 para s (basta). Os estados do desenho seguem a numeração da construção. Em cada nó, ela visita primeiro o que está pendurado à esquerda, depois o que está à direita e por fim o próprio nó, e cada estado recebe o próximo número livre ao ser criado. O 4 é o estado inicial, em que a máquina começa, e o 5 é o de aceitação.
A simulação executa a máquina sem escolher caminho: ela guarda, a cada momento, o conjunto de todos os estados em que a máquina pode estar. O conjunto de partida é o fecho vazio do estado inicial, isto é, esse estado e tudo o que se alcança dele só por corredores. A cada símbolo lido, passe pelas catracas desse símbolo e calcule o fecho vazio do conjunto dos estados a que elas levam: esses estados e tudo o que se alcança deles só por corredores. A cadeia é aceita quando o estado de aceitação está no último conjunto.
O que peço de você: quatro respostas, nesta ordem. (a) Calcule quantos estados, quantas transições e quantos corredores a máquina correta de (ab)* tem, somando nó por nó da árvore. (b) Conte as transições do desenho, compare com o resultado de (a) e diga em duas frases o que a comparação demonstra e o que deixa em aberto. (c) Confira o desenho, transição vazia por transição vazia, contra as regras da concatenação e do operador *. Aponte a única transição vazia ligada ao estado errado, escreva a que estados ela deveria ligar e diga o que a definição de bloco deste módulo afirma sobre como um bloco se relaciona com o resto da máquina. (d) Dê uma cadeia que o desenho aceita e (ab)* não aceita, e outra que (ab)* aceita e o desenho recusa. Para cada uma, escreva a sequência de conjuntos de estados da simulação sobre o desenho e a da simulação sobre a máquina correta, e aponte o primeiro conjunto em que as duas sequências diferem.
Você terá terminado quando (a) trouxer os totais de estados, transições e corredores com a soma nó por nó; (b) trouxer a contagem do desenho ao lado da de (a) e as duas frases que dizem o que a comparação demonstra e o que ela deixa em aberto; (c) nomear a transição vazia errada, os dois estados que ela deveria ligar e o que a definição de bloco deste módulo afirma sobre a relação entre um bloco e o resto da máquina; e (d) trouxer as duas cadeias, cada uma com as duas sequências de conjuntos escritas passo a passo, sem programa nenhum, e com o primeiro conjunto em que elas diferem.
1.2 Exercício 2: O programa que recusa a cadeia ac
Nível Intermediário
Um programa pequeno roda a simulação por conjunto de estados sobre a máquina de Thompson de (ab|a)c. O programa foi escrito para seguir a definição de simulação deste módulo, repetida aqui. Uma transição vazia é a seta que a máquina atravessa sem ler símbolo; no diagrama, ela leva escrito \varepsilon. O fecho vazio E(S) de um conjunto de estados S é o menor conjunto que contém S e todo estado alcançável a partir de S por zero ou mais transições vazias. A simulação começa em S_0 = E(\{q_0\}), sendo q_0 o estado inicial. Para cada símbolo a_i lido, ela calcula S_i = E(\text{mover}(S_{i-1}, a_i)), em que \text{mover} reúne os destinos das transições que leem a_i a partir dos estados de S_{i-1}. A cadeia é aceita quando o estado de aceitação pertence ao último conjunto.
A máquina está no diagrama, com os estados numerados pela ordem em que a construção os cria. O 6 é o inicial e o 9 é o de aceitação. Ao rodar a cadeia ac, o programa imprimiu o traço que vem logo depois do diagrama: a lista dos conjuntos de estados, um para antes da primeira leitura e um para cada símbolo lido. No fim, o programa respondeu que recusa a cadeia. Quem o escreveu esperava que ela fosse aceita e já conferiu o desenho: a máquina está correta. Três palavras aparecem nas perguntas adiante. A linguagem de um padrão é o conjunto das cadeias que ele descreve. O veredito de uma cadeia é a resposta esperada para ela, aceita ou recusa. Uma bateria é uma lista de cadeias de teste que se roda inteira de cada vez, cada cadeia com o seu veredito.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
S6((6<br/>inicial)) -->|ε| S0((0))
S6 -->|ε| S4((4))
S0 -->|a| S1((1))
S1 -->|ε| S2((2))
S2 -->|b| S3((3))
S4 -->|a| S5((5))
S3 -->|ε| S7((7))
S5 -->|ε| S7
S7 -->|ε| S8((8))
S8 -->|c| S9(((9<br/>aceitação)))
O que peço de você: quatro partes, nesta ordem. (a) Calcule à mão a simulação correta sobre a cadeia abc, escrevendo S_0, S_1, S_2 e S_3, e diga em qual conjunto aparecem ao mesmo tempo um estado que espera b, isto é, de onde sai uma transição que lê b, e outro que espera c. (b) Sem olhar para a máquina, escreva a linguagem de (ab|a)c e decida por ela o veredito de cada uma das cinco cadeias ac, ab, abc, acc e c. (c) Compare o traço impresso com a definição, aponte o primeiro conjunto em que ele diverge, escreva o conjunto correto ao lado e diga qual das duas aplicações de E na definição, a de S_0 ou a que segue cada \text{mover}, o programa deixou de fazer. (d) Entre as cinco cadeias de (b), diga em quais o programa defeituoso ainda acerta o veredito. Uma bateria formada só por essas cadeias em que ele acerta passaria inteira: diga se esse resultado confirma, contraria ou deixa em aberto a correção do programa, que programa trivial passaria na mesma bateria e qual cadeia você acrescentaria para decidir.
Você terá terminado quando (a) trouxer S_0 a S_3 escritos e o conjunto em que convivem um estado que espera b e outro que espera c; (b) trouxer a linguagem do padrão e os cinco vereditos, cada um justificado por ela e não pela máquina; (c) trouxer o primeiro conjunto divergente ao lado do correto e a aplicação de E que faltou; e (d) nomear as cadeias em que o programa defeituoso acerta, disser se a bateria que passa inteira confirma, contraria ou deixa em aberto a correção, descrever o programa trivial e trouxer a cadeia que decide.
1.3 Exercício 3: O filtro que um único padrão pode derrubar
Nível Desafiador
Um fórum comunitário de apoio a pessoas em crise filtra as mensagens por padrões que qualquer participante cadastra: a mensagem que algum desses padrões descreve fica retida para moderação. O serviço atende todos ao mesmo tempo, e um filtro lento atrasa todas as mensagens, inclusive as de quem está pedindo ajuda naquele momento. A equipe de operação discute duas propostas. As duas apostam que, para evitar o filtro lento, é suficiente o que se sabe antes de a primeira mensagem chegar. A primeira proposta aceita padrões de até 20 caracteres digitados. A segunda constrói, no cadastro, a tabela determinística completa do padrão, para decidir cada mensagem com uma consulta por símbolo lido.
Três lembretes, porque as contas usam os três. Primeiro: |r| é o número de nós da árvore do padrão r, e c(r) é quantos desses nós são concatenações; a tabela de custos deste módulo dá dois estados novos por folha, dois por alternância (a escolha, escrita com |), dois pelo operador * e nenhum por concatenação. Segundo: a simulação que anota os estados já visitados consulta cada transição no máximo duas vezes por símbolo lido, uma ao mover e outra no fecho vazio. Terceiro: guardar numa tabela cada conjunto de estados que a simulação encontra é construir o autômato determinístico cujos estados são esses conjuntos. Esse autômato pode precisar de um estado para cada conjunto de estados da máquina original: até 2^n, para uma máquina de n estados. Em (a \mid b)^{*}c, com dez estados, essa tabela fica com só cinco linhas, uma por conjunto encontrado, contra um teto de 2^{10} = 1024.
O padrão de teste é (a|aa)*b: zero ou mais pedaços a ou aa, seguidos de um b. A máquina de Thompson dele tem 14 transições. A equipe também compara a simulação com um motor com retrocesso. É um programa que testa a mensagem contra o padrão seguindo um percurso de cada vez, e um percurso é um caminho de estado em estado pelas setas da máquina. A cada falha, o motor volta atrás, tenta a alternativa seguinte e só recusa depois de esgotar todas as repartições da mensagem em pedaços a e aa. Para uma mensagem de m letras a sem b no fim, vamos chamar de p(m) o número de repartições dela em pedaços de uma ou duas letras, contando a ordem dos pedaços: para m = 2 há duas repartições, dois pedaços a ou um pedaço aa. O diagrama mostra em que momento cada proposta age.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
subgraph cad["no cadastro, antes de qualquer mensagem"]
P["padrão digitado<br/>a primeira proposta limita aqui"] --> T["árvore do padrão"]
T --> M["máquina de Thompson"]
M --> TAB["tabela determinística<br/>a segunda proposta constrói aqui"]
end
subgraph msg["a cada mensagem recebida"]
SIM["simulação<br/>um conjunto de estados por símbolo lido"]
CON["consulta à tabela<br/>uma por símbolo lido"]
end
M --> SIM
TAB --> CON
SIM --> V["resposta sobre a mensagem"]
CON --> V
O que peço de você: quatro partes. (a) Formule por recursão sobre os tipos de nó a função n(r), o número de estados da máquina de Thompson de r, e demonstre por indução sobre a árvore que n(r) = 2\,(|r| - c(r)). Conclua o teto n(r) \le 2|r|, calcule n(r) para (a|aa)*b e diga quanto sobra do teto e por quê. (b) Escreva uma recorrência para p(m), uma fórmula que dá p(m) a partir dos valores de p para mensagens mais curtas, com os valores iniciais, e calcule p(10). Mostre, a partir da recorrência, que p(40) passa de um milhão. Compare p(40) com o máximo de consultas a transição que a simulação faz em 40 letras a, contando só as consultas por letra lida, e explique, pelo que acontece com dois percursos que chegam ao mesmo estado, por que o trabalho da simulação não cresce com o número de repartições. (c) Critique cada proposta, uma de cada vez. Aqui, [a-z] é uma faixa de 26 símbolos, que vira 26 folhas ligadas por 25 alternâncias, e x+ vira x seguido de x*, o que põe x duas vezes na árvore. Para a primeira proposta, compare o padrão [a-z]+@[a-z]+, de 13 caracteres digitados, com uma sequência literal de 13 caracteres: calcule o número de estados de cada máquina com a fórmula de (a) e diga o que isso mostra sobre o limite de 20 caracteres. Para a segunda proposta, use o teto 2^n da máquina de [a-z]+@[a-z]+ e o exemplo de (a \mid b)^{*}c para explicar por que a tabela completa não oferece, no cadastro, o tipo de garantia que a conta de (a) oferece.
(d) Escreva um parágrafo de decisão: proponha uma regra para admitir padrões no cadastro e uma estratégia para executá-los a cada mensagem, diga que grandeza cada uma limita e em que ponto do diagrama ela já é conhecida, e nomeie o que a sua escolha deixa sem garantia e o que ela custa.
Você terá terminado quando (a) trouxer a definição recursiva de n(r), a demonstração cobrindo os quatro tipos de nó, o teto e o valor de n(r) para (a|aa)*b, com a sobra explicada; (b) trouxer a recorrência com os valores iniciais, p(10), o argumento de que p(40) passa de um milhão, o número de repartições lado a lado com o de consultas e a explicação pelos dois percursos que chegam ao mesmo estado; (c) apoiar a crítica em números calculados por você, trazendo para a primeira proposta o número de estados das duas máquinas, a de [a-z]+@[a-z]+ e a da sequência literal, e o que esses números mostram sobre o limite de 20 caracteres, e para a segunda o teto 2^n da máquina de [a-z]+@[a-z]+ e o exemplo de (a \mid b)^{*}c, com a explicação de por que a tabela completa não oferece, no cadastro, a garantia que a conta de (a) oferece; e (d) propuser a regra e a estratégia e disser, para cada uma, que grandeza ela limita e em que ponto do diagrama essa grandeza já é conhecida, e, para a escolha, o que deixa sem garantia e o que custa.
Três hábitos de método saem destes problemas. O primeiro: faça a conta de tamanho nó por nó e confira o resultado por outra conta, como recontar as transições pela soma das regras e pela contagem no desenho. O segundo: um veredito só confere uma máquina, ou o programa que a simula, quando sai da linguagem do padrão, e um teste vale pelo que seria capaz de reprovar. O terceiro: diante de um padrão que você não escreveu, pergunte que grandeza se conhece antes de rodá-lo e desconfie da que só aparece depois.