%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
R["concat"]
A["alt"]
F["fecho"]
L1["'a'"]
L2["vazio"]
L3["'b'"]
R --> A
R --> F
A --> L1
A --> L2
F --> L3
1 Expressões regulares e linguagens regulares — Exercícios
Os três problemas abaixo cobram o vocabulário deste capítulo e nada além dele: as seis cláusulas que decidem se um texto é expressão, a árvore que a leitura produz, a linguagem denotada calculada de baixo para cima, o núcleo de três operadores e duas folhas, a contagem de nós que as reduções geram, a cerca do fechamento e a distância entre comparar árvores e comparar linguagens. Nenhum deles pede programa escrito, e todos se resolvem com papel, lápis e a disposição de conferir uma conta pequena duas vezes. Resolva na ordem: o segundo usa a árvore que o primeiro aprende a ler, e o terceiro precisa dos dois.
1.1 Exercício 1: A árvore que ninguém digitou por inteiro
Nível Básico
Alguém escreveu um padrão pequeno numa notação de conveniência, passou o texto por um leitor que reduz tudo ao núcleo durante a leitura, e mandou a você apenas a árvore que saiu do outro lado. O texto original se perdeu no caminho. O que sobrou está no diagrama abaixo, com os filhos de cada nó na ordem em que aparecem da esquerda para a direita. Os rótulos são os do núcleo: concat para a concatenação, alt para a alternância, fecho para a repetição de zero ou mais, vazio para a folha da cadeia sem símbolos, e o símbolo entre aspas para a folha de símbolo. O alfabeto é \Sigma = \{a, b\}.
Repare na folha vazio antes de qualquer outra coisa. Não existe jeito de digitá-la: nenhuma sequência de caracteres num padrão escreve a cadeia sem símbolos. Ela nasce apenas de uma redução, e é essa a pista que devolve o texto original.
O que peço de você: quatro respostas curtas, nesta ordem. (a) Escreva a expressão do núcleo que a árvore representa, na forma linear que põe o rótulo da raiz seguido dos filhos entre parênteses, e conte quantos nós ela tem. (b) Escreva o padrão curto, na notação de conveniência, que o autor provavelmente digitou — aquele cuja redução produz exatamente essa árvore — e diga qual redução criou a folha vazio. (c) Calcule L(r) para a expressão da árvore, listando todas as cadeias de comprimento no máximo 2 e dizendo quantas são; faça o cálculo de baixo para cima, escrevendo o conjunto que cada nó denota antes de subir ao pai. (d) Um colega olhou a árvore, achou a folha vazio inútil e a arrancou junto com a alternância acima dela, deixando a folha 'a' pendurada direto na concatenação. Diga que cadeias saem do conjunto com esse corte e por quê.
Eu já cortei essa folha por engano, e o incômodo é que o programa continua funcionando: ele lê, constrói e encerra sem reclamar de nada. Você terá terminado quando a forma linear de (a) estiver com a contagem ao lado, o padrão de (b) vier com o nome da redução que o gerou, a lista de (c) estiver completa com a cadeia sem símbolos incluída, e a resposta de (d) nomear as cadeias perdidas em vez de dizer apenas que o conjunto ficou menor.
1.2 Exercício 2: Duas escritas, três vereditos possíveis
Nível Intermediário
Um sistema precisa reconhecer códigos de inventário no formato de três letras minúsculas, um hífen e um ou mais dígitos — abc-7, xyz-1024. O padrão escrito na notação de conveniência é [a-z][a-z][a-z]-[0-9]+, e são dezoito caracteres digitados. Antes de qualquer máquina existir, esse texto vira árvore, e a árvore tem tamanho. Vale relembrar a aritmética deste capítulo: uma faixa de n símbolos reduz a n folhas mais n-1 alternâncias, isto é, 2n-1 nós; o fecho positivo x+ reduz a concat(x, fecho(x)), o que duplica a subárvore de x e acrescenta dois nós; e cada concatenação, escrita ou apenas justaposta, custa um nó próprio. O alfabeto latino minúsculo tem 26 símbolos e os dígitos são 10.
Do outro lado do mesmo sistema há uma disputa. Duas pessoas escreveram padrões diferentes para o mesmo requisito e querem saber se descrevem o mesmo conjunto. A ferramenta disponível é o comparador do diagrama: ele lê as duas escritas, reduz as duas ao núcleo, escreve cada árvore na forma prefixa — o rótulo da raiz, os filhos entre parênteses, separados por vírgula — e compara as duas cadeias de caracteres resultantes.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T1["texto da primeira escrita"]
T2["texto da segunda escrita"]
LE["leitor: precedencia,<br/>reducao ao nucleo"]
P1["forma prefixa da primeira arvore"]
P2["forma prefixa da segunda arvore"]
C{"as duas cadeias<br/>de caracteres coincidem?"}
S["veredito: mesma arvore"]
N["veredito: arvores diferentes"]
Q["pergunta que fica sem resposta:<br/>e as linguagens denotadas,<br/>sao a mesma?"]
T1 --> LE
T2 --> LE
LE --> P1
LE --> P2
P1 --> C
P2 --> C
C -->|"sim"| S
C -->|"nao"| N
N -.-> Q
O que peço de você: quatro partes, na ordem de dependência. (a) Calcule quantos nós a árvore de [a-z][a-z][a-z]-[0-9]+ tem, apresentando a soma pedaço por pedaço — cada faixa, o hífen, o fecho positivo e as concatenações que costuram tudo — e escreva ao final a razão entre nós construídos e caracteres digitados. (b) Sem refazer a conta inteira, diga quantos nós o padrão passaria a ter se o + final virasse ?, e explique em uma frase de onde vem a diferença entre os dois quantificadores. (c) Classifique cada um dos quatro pares abaixo em exatamente um dos três vereditos — mesma árvore depois da redução, árvores diferentes e mesma linguagem, linguagens diferentes — justificando cada classificação: a+ contra aa*; [a-c] contra a|b|c; (a \mid b)^* contra (a^*b^*)^*; e a^*b^* contra (a \mid b)^*. Nos casos de linguagens diferentes, exiba uma cadeia que esteja num conjunto e não no outro. (d) O comparador respondeu “árvores diferentes” para o terceiro par de (c), e quem o rodou concluiu dali que as duas expressões descrevem conjuntos diferentes. Diga por que a ferramenta está certa e a conclusão está errada, e nomeie a verificação que decidiria a pergunta de verdade, dizendo que objeto ela precisa construir antes.
Você terá terminado quando a soma de (a) fechar com as parcelas visíveis, a resposta de (b) apontar a duplicação como causa, os quatro pares de (c) estiverem classificados com testemunha ou argumento ao lado, e (d) separar com todas as letras a pergunta “estas duas árvores são iguais?” da pergunta “estes dois conjuntos são iguais?”.
1.3 Exercício 3: A especificação que promete mais do que a classe entrega
Nível Desafiador
Uma equipe está especificando um formato de arquivo de configuração para um serviço público na internet, que recebe texto enviado por qualquer pessoa e precisa recusar o malformado depressa. A validação será escrita a partir de padrões, e a equipe já rascunhou cinco requisitos em prosa. (R1) O campo de contato é uma sequência de uma ou mais letras minúsculas, seguida de arroba, seguida de uma ou mais letras minúsculas. (R2) Os blocos podem conter blocos, delimitados por parênteses, sem profundidade máxima declarada. (R3) Uma versão alternativa do mesmo requisito fixa a profundidade máxima em três níveis de encaixe. (R4) Todo arquivo termina com um campo de conferência que repete, letra por letra, o valor do campo de identificação declarado no início — e o identificador não tem comprimento máximo. (R5) O identificador aceita apenas letras minúsculas do alfabeto latino sem acento, com no máximo dezesseis caracteres.
O procedimento do diagrama é o que decide, para cada requisito, se ele cabe na classe regular. Ele não olha a aparência do texto do padrão; olha a memória que a máquina precisaria ter ao chegar ao fim da entrada.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
R["requisito escrito em prosa"]
P1["1. que pergunta a maquina<br/>teria de responder<br/>ao chegar ao fim do texto?"]
P2["2. o que ela precisaria<br/>lembrar para responder aquilo?"]
P3{"3. o que ela precisa lembrar<br/>tem teto declarado?"}
D["cabe na classe regular:<br/>existe expressao que a denota"]
F["fica fora da classe:<br/>nenhuma expressao a denota"]
R --> P1 --> P2 --> P3
P3 -->|"sim, teto fixo"| D
P3 -->|"nao, cresce com o texto"| F
O que peço de você: uma análise em cinco partes, escrita em prosa, cada uma apoiada no que este capítulo estabeleceu. (a) Aplique o procedimento de três passos a cada um dos cinco requisitos, escrevendo para cada um a pergunta do passo 1, a memória do passo 2 e o veredito do passo 3; ao final, classifique R1 a R5 em dentro e fora da classe. (b) Para o requisito que sai da classe por encaixe sem teto, refaça o argumento da cerca: suponha uma máquina de k estados, com k escolhido antes de qualquer texto chegar, alimente-a com profundidades de abertura crescentes, e mostre o que acontece quando duas profundidades distintas terminam no mesmo estado. O argumento precisa valer para qualquer k, sem depender de nenhum número em particular. (c) Compare R2 com R3 e explique por que fixar a profundidade em três níveis muda o veredito, apoiando a explicação na definição de linguagem regular deste capítulo e no argumento de que toda linguagem finita é regular. (d) O requisito R4 é o único dos cinco que exige a repetição literal de um trecho já casado. Diga que construção das notações modernas o realizaria, por que ela sai da classe, e — dado que o serviço recebe texto de fora, sem controle sobre o tamanho — argumente qual das duas famílias de motor descritas no capítulo pode ser aceita aqui e o que a equipe perde ao escolhê-la. (e) A equipe discute, em paralelo, quantos tipos de nó o leitor de padrões vai produzir: tratar cada operador de conveniência com um nó próprio, ou reduzir tudo ao núcleo. Faça a aritmética dos dois caminhos sobre as três peças que percorrerão a árvore mais adiante, apresente os dois totais de casos escritos, e critique a decisão de manter o coringa no núcleo mesmo sendo ele redutível.
Termine com um parágrafo de julgamento, que é o que amarra as cinco partes. O R5 restringe o identificador ao alfabeto latino sem acento por escolha de projeto, e a teoria não obriga a isso: a classe regular aceita qualquer alfabeto finito, inclusive um que admita nomes escritos em outros idiomas. Diga quem paga o preço dessa restrição, o que ela poupa a quem escreve o validador, e — usando a sua conta de (e) e a fórmula da faixa — quanto custaria, em nós de árvore, admitir um alfabeto maior. Apresente a escolha com o preço escrito ao lado, e não como a opção obviamente melhor.
Você terá terminado quando os cinco vereditos de (a) vierem com a memória nomeada, o argumento de (b) se sustentar sem número fixo, (c) distinguir o teto declarado do parêntese, (d) escolher a família de motor com a perda dita em voz alta, (e) apresentar os dois totais lado a lado, e o parágrafo final atribuir o custo da restrição de alfabeto a alguém concreto.
Três hábitos de método atravessam os problemas acima. O primeiro: quando precisar decidir se duas escritas dizem a mesma coisa, nunca compare figuras a olho — reduza as duas, escreva cada árvore como uma cadeia de caracteres e compare os dois textos, porque a comparação visual falha justamente nos casos grandes, em que a diferença mora num nó do meio. O segundo: separe sempre o tamanho da árvore do tamanho do conjunto denotado; são duas grandezas independentes, e confundi-las leva a concluir que um padrão de dois caracteres tem estrutura enorme por descrever um conjunto sem fim. O terceiro: diante de qualquer requisito escrito em prosa, troque a pergunta “isso parece complicado?” pela pergunta “o que a máquina precisaria lembrar, e esse tanto tem teto?” — a aparência do padrão nunca respondeu a isso, e a memória exigida sempre responde.