flowchart TB
R["concatenação"] --> A["alternância"]
R --> C["símbolo c"]
A --> X["símbolo a"]
A --> Y["símbolo b"]
1 Expressões regulares e linguagens regulares — Exercícios
Em 15 de dezembro de 1951, Stephen Kleene assinou na RAND o memorando RM-704. O assunto declarado eram redes de neurônios, e o texto só circulou para fora em 1956, na coletânea Automata Studies, organizada por Shannon e McCarthy. Dezessete anos depois do memorando, em junho de 1968, nos Bell Labs, Ken Thompson publicou nas Communications of the ACM o artigo Regular Expression Search Algorithm: um programa que lia uma expressão regular e escrevia, a partir dela, código de máquina do IBM 7094 para procurar o padrão num texto. Passaram-se mais cinquenta e um anos até 2 de julho de 2019, quando um fragmento de padrão com sete caracteres — .*.*=.* — parou um serviço inteiro, no incidente que John Graham-Cumming relatou por escrito.
Guarde essas três datas, porque elas emolduram os três problemas a seguir. A notação existe desde 1951 e o método que a executa sem retroceder existe desde 1968; o que aconteceu em 2019 aconteceu do lado da implementação, e não do lado da classe. Distinguir esses dois lados é o exercício central deste ponto do percurso, e ele aparece aqui em três tamanhos.
O primeiro problema é de leitura: cinco expressões pequenas, e o conjunto que cada uma denota escrito por extenso. O segundo é uma conta — a primeira vez em que você vai fazê-la em vez de lê-la —, e ela mede em nós de árvore o preço de um operador de conveniência. O terceiro põe quatro exigências de um sistema real lado a lado e pergunta qual delas cabe na classe regular, qual não cabe, e o que fazer com a que não cabe.
Tenha papel ao lado, principalmente no segundo. A conta dele tem três parcelas e cada uma cobra uma coisa diferente; feita de cabeça, ela sai com uma parcela a menos, e é sempre a mesma que some.
Os três cobram a expressão regular como objeto matemático, com sintaxe e semântica próprias. A sintaxe diz o que conta como expressão bem formada; a semântica diz que conjunto de cadeias cada expressão denota. Nenhum dos três pede código, e nenhum se resolve reconhecendo uma notação já usada em alguma ferramenta. Sempre que se pegar respondendo pela aparência do texto do padrão, pare e refaça a pergunta pela definição: qual é o conjunto, e o que a máquina precisaria lembrar para decidir se uma cadeia está nele.
1.1 Exercício 1: cinco expressões, cinco conjuntos
Nível básico
Um colega escreveu cinco expressões numa folha, sobre o alfabeto \Sigma = \{a, b\}, e afirmou que duas delas denotam exatamente o mesmo conjunto. Ele não disse quais. As cinco são r_1 = \emptyset, r_2 = \varepsilon, r_3 = \emptyset^*, r_4 = \emptyset a e r_5 = (a \mid \varepsilon).
Antes de responder, fixe os dois símbolos que derrubam mais gente aqui, e que já apareceram no capítulo anterior noutra roupa. A cadeia vazia, escrita \varepsilon, é a sequência de comprimento zero — um elemento, que ocupa lugar dentro de um conjunto. A linguagem vazia, escrita \emptyset, é o conjunto que não contém cadeia alguma. Como expressões regulares, as duas são construções distintas da definição, e a linguagem denotada por cada uma tem cardinalidade diferente: zero de um lado, um do outro.
O que peço de você: três respostas curtas, cada uma com a razão ao lado.
Em (a), escreva por extenso, entre chaves, a linguagem denotada por cada uma das cinco expressões, e dê a cardinalidade de cada conjunto. Aponte então o par que denota o mesmo conjunto e diga, numa frase, por que a igualdade é entre os conjuntos denotados e não entre os textos escritos. Cuidado com r_4: a concatenação de linguagens justapõe cada cadeia da primeira com cada cadeia da segunda, e vale a pena perguntar quantos pares existem quando um dos dois conjuntos está vazio.
Em (b), tome as duas expressões a \mid bc e (a \mid b)c. Escreva por extenso a linguagem denotada por cada uma, exiba uma cadeia que pertença a uma e não à outra, e diga qual regra de precedência entre a alternância e a concatenação produz essa diferença. Olhe em seguida o diagrama abaixo: ele mostra a árvore de uma das duas, com o parêntese de agrupamento já desaparecido na leitura. Diga qual das duas é, e justifique pela forma da árvore, não pelo texto que a originou.
Em (c), compare a^* com a^+. Liste os quatro primeiros elementos de cada uma, em ordem crescente de comprimento, e nomeie a cadeia que está numa e não está na outra. Explique depois, em duas ou três frases, como duas posições escritas no papel conseguem denotar um conjunto infinito — e por que a frase “expressão curta denota linguagem pequena” é falsa.
Você terá terminado quando conseguir dizer, sem consultar o material, por que \emptyset e \emptyset^* denotam conjuntos de cardinalidades diferentes, sendo o segundo construído a partir do primeiro. Se a sua explicação de (c) servir igualmente bem para a^* e para uma lista de mil cadeias escritas à mão, ela ainda não separou o tamanho do texto do tamanho do conjunto.
1.2 Exercício 2: o preço da conveniência, em nós
Nível intermediário
Uma notação de padrões oferece faixas de símbolos, fecho positivo e opcional, e nenhum dos três pertence ao núcleo da definição formal. O núcleo tem três operadores — concatenação, alternância e fecho — e duas folhas, o símbolo literal e a cadeia vazia. Tudo o mais é açúcar sintático: abreviação de uma composição do núcleo, que se desfaz durante a leitura da expressão e não sobrevive dentro da árvore.
As reduções estão registradas em pares, e são estas. O fecho positivo x+ reduz a xx*, isto é, a uma concatenação entre a subárvore de x e o fecho dessa mesma subárvore — e a subárvore é clonada, nunca apontada duas vezes, porque dois pais apontando o mesmo filho produzem um grafo em lugar de uma árvore. O opcional x? reduz à alternância entre x e a cadeia vazia. A faixa [a-e] reduz à enumeração [abcde], e essa à alternância de cinco símbolos. O parêntese de agrupamento reduz a nada: não vira nó, não vira folha, não deixa marca.
Considere agora o padrão ([a-e]+)?, escrito com nove caracteres. Antes de calcular qualquer coisa, escreva num canto do papel o seu palpite para o número de nós da árvore reduzida. Escreva mesmo, com número; o palpite errado é o instrumento deste exercício, e ele só funciona se estiver no papel antes da conta.
flowchart TB
E1["passo 1<br/>faixa de cinco símbolos"] --> P1["parcela 1<br/>folhas mais alternâncias<br/>= ?"]
E2["passo 2<br/>fecho positivo sobre o resultado do passo 1"] --> P2["parcela 2<br/>o que o fecho acrescenta<br/>= ?"]
E3["passo 3<br/>opcional sobre o resultado do passo 2"] --> P3["parcela 3<br/>o que o opcional acrescenta<br/>= ?"]
P1 --> T["total de nós da árvore reduzida<br/>= ?"]
P2 --> T
P3 --> T
O que peço de você: a conta em três parcelas separadas, depois a forma geral, depois a remedida.
Em (a), meça as três parcelas do diagrama, uma de cada vez, e não some antes de ter as três. A primeira é a subárvore da faixa de cinco símbolos: quantas folhas e quantas alternâncias. A segunda é o que o fecho positivo acrescenta sobre essa subárvore, lembrando que ele a clona. A terceira é o que o opcional acrescenta sobre o resultado do passo anterior. Só então some, e compare o total com o palpite que você escreveu.
Em (b), generalize. Chame de k o número de símbolos da faixa e escreva a fórmula fechada f(k) para o total de nós desse mesmo padrão com uma faixa de k símbolos no lugar da de cinco. Confira a fórmula avaliando-a em k = 5, que precisa devolver o total de (a), e avalie-a em seguida em k = 26, que é a faixa das letras minúsculas. Diga se a fórmula é linear em k e o que isso significa para quem digita três caracteres esperando pagar três.
Em (c), remedida. A mesma exigência pode ser escrita com um quantificador contado: [a-e]{3}, que reduz a três cópias da faixa concatenadas em sequência. Escreva a fórmula g(k) para essa forma, avalie-a em k = 26 e compare com o resultado de (b). Generalize por último para n cópias da faixa: escreva a expressão em função de n e de k, identifique nela o produto e a soma, e diga qual dos dois fatores é o perigoso quando alguém pode escrever n livremente numa linha de configuração.
Feche a conta com a leitura que ela sustenta. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções. A máquina, aqui, é a construção do autômato que vem nos capítulos seguintes, e ela só conhece as cláusulas do núcleo; o tradutor é a leitura da expressão, e a moeda com que ele paga são nós de árvore. Esta é a versão pequena e barata de uma conta que volta bem mais adiante, com instruções de máquina no lugar dos nós — e medir a barata agora é o que torna previsível a forma da cara.
Você terá terminado quando puder explicar, com os números na mão, por que a árvore ficou muitas vezes maior que o texto sem que a linguagem denotada tenha mudado de tamanho. Se a sua resposta a (c) não disser qual dos dois fatores cresce sob controle de quem escreve o padrão, ela ainda não é resposta de projeto.
1.3 Exercício 3: quatro exigências, uma notação de triagem
Nível desafiador
Este problema leva o capítulo inteiro para um cenário que ele não tratou, e o cenário está descrito por completo aqui. Um serviço público de atendimento recebe mensagens escritas por cidadãos num balcão digital. Um motor de padrões lê cada mensagem assim que ela chega e a encaminha ao setor competente; o que o motor não consegue triar volta para uma fila de leitura humana, que anda devagar. Quem espera nessa fila não trabalha no serviço e não escreveu padrão nenhum.
Quatro exigências foram levantadas para a próxima versão do motor, e ninguém classificou nenhuma delas.
flowchart TB
M["mensagem recebida no balcão digital"] --> F["motor de padrões<br/>compilado a partir das quatro exigências"]
F --> S["triada e encaminhada ao setor certo"]
F --> N["não triada<br/>volta para a fila de leitura humana"]
E1["exigência 1<br/>código de protocolo:<br/>duas letras e seis dígitos"] -.-> Q["que memória<br/>cada exigência pede?"]
E2["exigência 2<br/>data no formato de oito dígitos<br/>separados por barras"] -.-> Q
E3["exigência 3<br/>trecho entre parênteses,<br/>sem profundidade máxima"] -.-> Q
E4["exigência 4<br/>o mesmo código de protocolo<br/>repetido duas vezes na mensagem"] -.-> Q
Q -.-> F
A primeira exigência é reconhecer um código de protocolo, formado por duas letras maiúsculas seguidas de seis dígitos. A segunda é reconhecer uma data escrita como oito dígitos separados por barras, na forma dd/mm/aaaa. A terceira é reconhecer o trecho de uma mensagem que esteja entre parênteses, e os cidadãos abrem parênteses dentro de parênteses sem que ninguém tenha declarado profundidade máxima. A quarta é sinalizar a mensagem em que um mesmo código de protocolo aparece duas vezes, qualquer que seja o código — o que denuncia reabertura de chamado já encerrado.
O que peço de você: três respostas, cada uma justificada pela memória exigida ou pela conta feita.
Em (a), classifique as quatro exigências: quais cabem na classe regular e quais não cabem. Justifique cada classificação pela memória que a máquina reconhecedora precisaria ter, e não pela aparência do padrão que alguém escreveria. Trate a terceira refazendo o argumento das casas de pombo: fixe uma máquina de k estados, apresente k+1 profundidades de abertura diferentes, mostre que duas delas terminam no mesmo estado e conclua o que a máquina deixa de distinguir a partir dali — e diga por que acrescentar estados não resolve para nenhum k finito. A quarta parece a mais simples das quatro e está mais alto na hierarquia; depois de classificá-la, responda ainda esta pergunta, que é o discriminador do item: uma máquina dotada de uma pilha — que devolve o que guardou em ordem inversa — daria conta dela? Justifique pelo que a pilha devolve, e feche dizendo o que mudaria na classificação da quarta exigência se o conjunto de códigos de protocolo válidos fosse finito e conhecido de antemão.
Em (b), trate o arranjo. Hoje o motor lê os padrões uma vez, na partida do serviço, e guarda as árvores prontas; uma proposta em discussão sugere ler cada padrão de novo a cada mensagem que chega, para poupar memória residente. Escreva as duas contas de custo em símbolos: chame de c o custo de reduzir e montar a árvore de um padrão, de p o número de padrões e de m o número de mensagens recebidas por dia. Diga qual das duas contas multiplica c por m e qual multiplica c por p, aponte qual dos dois fatores cresce fora do controle de quem opera o serviço, e diga que medição precisaria existir antes de a proposta ser aceita ou recusada.
Em (c), decida o motor. Duas bibliotecas estão disponíveis. A primeira oferece retrovisão — o recurso que permite exigir, dentro do próprio padrão, que um trecho já casado se repita adiante —, e é a única das duas que atenderia diretamente à quarta exigência. A segunda não oferece retrovisão e implementa o método publicado ainda nos anos sessenta, que decide numa única passada, sem nunca voltar atrás sobre o texto já lido. Diga qual das duas adotar e por quê. Nomeie a classe de complexidade que a literatura atribui a casar padrão com retrovisor, com a fonte que o capítulo registra. Formule então, em uma frase própria, o critério que separa o que uma classe de linguagens garante do que uma implementação entrega — a frase é sua, e ela é o que sustenta a decisão. Feche dizendo quem paga a diferença entre as duas escolhas no cenário descrito, e o que responder a quem propuser resolver a questão testando as duas bibliotecas com entradas grandes.
Você terá terminado quando as três respostas puderem ser lidas como um argumento único: (a) diz o que a classe alcança, (b) diz o que o arranjo custa, e (c) diz o que a implementação escolhida devolve em troca. Se a sua recusa em (c) se sustentar apenas em desempenho medido, falta-lhe o passo que (a) já lhe deu.
Um método que funciona nos três. Comece traduzindo cada enunciado em objetos da definição: alfabeto, cadeia, conjunto denotado, folha, nó de operador, árvore. Enquanto o problema estiver descrito pelo texto do padrão, a intuição opina; descrito por conjuntos e árvores, ele passa a ter resposta que outra pessoa consegue conferir sem executar nada.
Depois, a cada afirmação que for escrever sobre classe, faça a mesma pergunta: o que essa máquina precisaria lembrar para decidir? Do capítulo anterior você já traz o critério que a responde — quem só sabe em que estado está não sabe quantas vezes já entrou nele —, e é ele que separa os degraus, e nunca o tamanho do texto, a quantidade de operadores usados ou a impressão de que uma exigência é simples. Duas das exigências do terceiro problema parecem parentes próximas e estão em degraus diferentes.
Por último, escreva o palpite antes da conta no segundo problema, e guarde os dois lado a lado quando terminar. A distância entre eles é o resultado que interessa ali, e ela desaparece se a conta vier primeiro.