flowchart TB
Q["A entrada vazia deve ser aceita"] --> V["Linguagem vazia<br/>nenhuma cadeia dentro<br/>cardinalidade zero"]
Q --> E["Linguagem que contém só a cadeia vazia<br/>uma cadeia dentro<br/>cardinalidade um"]
V --> RV["O reconhecedor rejeita tudo<br/>inclusive a entrada vazia"]
E --> RE["O reconhecedor rejeita tudo<br/>exceto a entrada vazia"]
RV --> C["Comportamentos diferentes<br/>de objetos que se parecem no papel"]
RE --> C
Alfabetos, Linguagens e Expressões Regulares
O vocabulário formal que os próximos módulos vão consumir sem reapresentar
Roteiro da aula
- Duas expressões, o mesmo conjunto
- Cadeias e a estrutura que elas formam
- Linguagens, e as duas caixas que se confundem
- Seis construtores e nada mais
- Açúcar sintático e a árvore · demonstração
- A álgebra e a fronteira
Ao final, você será capaz de
- manipular cadeias e linguagens com as operações definidas;
- ler e escrever expressões regulares e demonstrar equivalências por manipulação algébrica;
- identificar, numa notação de biblioteca, quais construções extrapolam a classe regular.
Este slide entra depois das duas expressões da abertura, não antes: chegue com elas projetadas, sem título e sem explicação.
Anuncie a mudança de registro, porque a turma não a percebe sozinha e lê densidade formal como exigência arbitrária: no módulo anterior o critério era situar; aqui é operar.
Anuncie também que a segunda aula tem código digitado ao vivo — quem só assiste não aprende aquele bloco.
Duas expressões, o mesmo conjunto
Mesmo conjunto, custos diferentes
a^*b \qquad\qquad (a^*)^*b
Descrevem o mesmo conjunto de cadeias?
Recolha as hipóteses. A resposta é sim — a álgebra que demonstra isso é o penúltimo bloco.
Sobre trinta letras a e nenhum b?
Uma delas pode travar a busca. Qual, e por quê? A dívida será paga no fechamento.
Conjunto · notação · estratégia — as três palavras ficam no canto do quadro até o fim da segunda aula.
Faça as duas perguntas nesta ordem e não inverta. A hesitação da sala na primeira já é informação: quem aprendeu expressões regulares por imitação não tem como responder, porque nunca houve modelo.
Na segunda, não dê resposta alguma. Diga apenas que a resposta envolve uma interrupção mundial de serviço documentada publicamente. A dívida declarada segura melhor do que a resposta imediata, e costuma fazer alguém procurar o assunto por conta própria entre as duas aulas.
Feche escrevendo as três palavras no canto do quadro e não as apague.
Cadeias e a estrutura que elas formam
Os objetos, e as duas exigências que trabalham depois
Alfabeto
Conjunto finito e não vazio. Um alfabeto infinito não quebra a implementação: quebra os teoremas.
Cadeia
Sequência finita de símbolos. A cadeia vazia tem comprimento zero, e \Sigma^0 = \{\varepsilon\} — não \emptyset.
Comece pelo fundo da abstração, rápido e sem cerimônia, mas diga em voz alta que a finitude não é detalhe de arrumação: é a hipótese de que dependem praticamente todos os resultados deste andar.
A igualdade do segundo cartão é a primeira das quatro aparições da mesma distinção neste módulo. Nomeie-a como tal agora, para que as três seguintes sejam reconhecidas.
A concatenação é o eixo
As propriedades
Associativa, com \varepsilon como elemento neutro, e não comutativa: sobre \{a,b\} basta ab \ne ba.
O nome próprio
\Sigma^* com a concatenação é um monoide livre: nenhuma igualdade entre cadeias além das que os axiomas impõem.
“Livre” quer dizer que uma cadeia carrega exatamente a informação da sequência que a compõe, e nada mais.
Este slide sustenta tudo o que vem depois, então gaste tempo aqui e não no anterior.
Faça no quadro, e não projetado, a demonstração por indução de \lvert uv \rvert = \lvert u \rvert + \lvert v \rvert: caso base u = \varepsilon, com uv = v; passo escrevendo u = a u', de onde \lvert uv \rvert = 1 + \lvert u'v \rvert = 1 + \lvert u' \rvert + \lvert v \rvert pela hipótese.
Diga por que está demonstrando algo tão óbvio: a forma do argumento — caso base na cadeia vazia, passo que retira o primeiro símbolo — é a de quase toda demonstração dos próximos módulos, e vale internalizá-la agora, quando a atenção não está ocupada com o conteúdo.
Contiguidade separa duas noções parecidas
Subcadeia
Trecho contíguo. Em abc: \varepsilon, a, b, c, ab, bc, abc — sete, e ac não está.
Subsequência
Símbolos na ordem, com buracos permitidos. Aqui ac está.
Em aaa, a subcadeia aa ocorre em duas posições e é uma só: contar ocorrências não é contar objetos distintos.
Enumere abc no quadro antes de projetar: prefixos \varepsilon, a, ab, abc — quatro, que é n+1; sufixos \varepsilon, c, bc, abc — quatro pelo mesmo motivo. Só então as subcadeias.
A maneira segura de não errar a contagem é coletar num conjunto, e é exatamente o que o código do bloco de construção faz.
Não revele nada sobre o par subcadeia/subsequência além do que está no slide: a votação seguinte depende disso.
Primeira votação
Sobre a cadeia abc, a cadeia ac é:
- subcadeia e subsequência;
- subsequência, mas não subcadeia;
- subcadeia, mas não subsequência;
- nenhuma das duas.
Voto individual primeiro, sem comentário seu; discussão em duplas; segundo voto. Revelar a resposta antes da discussão anula a técnica.
Resposta: (b). Quem vota (a) não reteve a exigência de contiguidade e é a maioria no primeiro voto. Quem vota (d) leu contiguidade nas duas definições.
Feche com a consequência que interessa: praticamente toda categoria léxica de linguagem de programação exige contiguidade — os símbolos de um identificador são adjacentes no texto —, e essa é uma das razões pelas quais o formalismo regular basta para descrevê-las.
Linguagem é qualquer subconjunto de \Sigma^*
A caixa vazia e a caixa com a folha em branco
Antes do diagrama, explore a generalidade da definição em voz alta, porque a turma não a vê sozinha: o conjunto dos identificadores válidos é uma linguagem, o dos programas sintaticamente corretos é uma linguagem sobre outro alfabeto, o dos programas que terminam também é. A única diferença que a teoria enxerga entre elas é a dificuldade de decidir a pertinência.
Então pare tudo e escreva \emptyset e \{\varepsilon\} lado a lado no quadro. A folha em branco é uma coisa; a ausência de folha é outra. Segunda aparição da distinção.
As operações, com a conta feita
Concatenação
L_1 = \{a, ab\}, L_2 = \{b, \varepsilon\}: quatro pares, três cadeias — \{a, ab, abb\}.
Neutro e absorvente
\{\varepsilon\}L = L; \emptyset L = \emptyset. Trocar um pelo outro é a origem das falsas demonstrações.
Distributividade sobre \cap
Falha. Com L = \{a, aa\}, L_1 = \{a\}, L_2 = \{aa\}: à esquerda, vazio; à direita, aaa.
aaa vem de aa \cdot a à esquerda e de a \cdot aa à direita: a concatenação perde a fronteira.
Faça as três contas inteiras no quadro; são curtas e convencem. No primeiro cartão, o par (a,b) e o par (ab,\varepsilon) produzem a mesma cadeia — é o fenômeno das subcadeias de aaa, um nível acima.
A perda da fronteira é a ideia a carregar do slide, e reaparece adiante como ambiguidade de gramáticas. Avise disso.
Potências e fechos: derive, não decore
L^0 = \{\varepsilon\} \quad\text{para toda } L, \text{ inclusive } L = \emptyset
Por que não é convenção
Se L^0 = \emptyset, então L^1 = L^0L = \emptyset para toda linguagem. Absurdo.
A leitura combinatória
Há exatamente uma maneira de concatenar zero cadeias — não fazer nada —, e o resultado dela é a cadeia vazia.
Faça a turma derivar, não decorar. O argumento do primeiro cartão costuma bastar para quem já opera com definições; o segundo é o que convence os demais.
Deixe o slide no ar ao passar para a votação: quem votar por eliminação vai usá-lo. Terceira aparição da distinção.
Segunda votação
Qual é o valor de \emptyset^*, o fecho de Kleene do conjunto vazio?
- \emptyset;
- \{\varepsilon\};
- \Sigma^*;
- indefinido, porque não há cadeia a concatenar.
Resposta: (b), e esta é a questão que mais separa quem entendeu de quem decorou — espere maioria em (a) no primeiro voto.
O argumento a extrair do segundo voto é o da definição: \emptyset^* = \bigcup_{n\ge 0}\emptyset^n, e a parcela n = 0 vale \{\varepsilon\}, enquanto todas as demais são vazias. Escreva o contraste ao lado, porque ele fixa: \emptyset^+ = \emptyset, porque a união começa em n = 1.
Quem vota (d) percebeu a estranheza e concluiu que a definição falha; é o erro mais interessante e o melhor gancho para dizer que a definição foi escolhida justamente para não falhar em caso algum.
Se a maioria permanecer errada depois da discussão em duplas, não siga adiante: refaça a definição no quadro.
Quase toda linguagem é indescritível
As linguagens
Subconjuntos de \Sigma^*: pela diagonalização de Cantor, coleção com a cardinalidade do contínuo.
As descrições finitas
Cadeias finitas sobre um alfabeto finito de notação: coleção enumerável.
A consequência
Não há sobrejeção de enumerável sobre não enumerável: qualquer sistema de descrição finita deixa linguagens de fora.
A pergunta deixa de ser “como descrever qualquer linguagem” e passa a ser “que classe vale a pena descrever, e com que notação”.
Fechamento da primeira aula. Não conte isso para desanimar; conte para trocar a pergunta — e encerre exatamente aqui, sem responder.
É a melhor pendência que se pode deixar entre as duas aulas, porque a resposta é o assunto inteiro da segunda.
Seis construtores e nada mais
Três casos-base, três construtores
Casos-base
A expressão do conjunto vazio; a expressão da cadeia vazia; cada símbolo do alfabeto.
Construtores
União, concatenação, estrela. Precedência: estrela, depois concatenação, depois união.
Tudo o que se vê numa ferramenta de busca ou é abreviação escrita nesses seis, ou não é expressão regular coisa nenhuma.
Retome pela pergunta pendente da primeira aula, não por resumo. A surpresa a explorar é o tamanho da resposta: seis.
Faça a advertência de notação, porque a confusão é real e persistente: \emptyset e \varepsilon aparecem aqui como elementos da sintaxe, caracteres que se escrevem, e apareceram na primeira aula como objetos semânticos. Mesmo desenho, naturezas diferentes. Adote em voz alta o hábito de dizer “a expressão \varepsilon” ou “a cadeia \varepsilon”, e cobre isso da turma.
Verifique a precedência com os dois casos que apanham todo mundo: ab^* é a(b^*) e não (ab)^*; a \mid bc é a \mid (bc) e não (a\mid b)c.
A semântica são seis igualdades
flowchart LR
subgraph SIN["Sintaxe - texto que se escreve"]
A0["expressão do vazio"]
A1["expressão da cadeia vazia"]
A2["um símbolo do alfabeto"]
A3["alternação de duas expressões"]
A4["justaposição de duas expressões"]
A5["estrela sobre uma expressão"]
end
subgraph SEM["Semântica - conjunto denotado"]
B0["conjunto vazio"]
B1["conjunto com a cadeia vazia"]
B2["conjunto com uma cadeia de um símbolo"]
B3["união dos dois conjuntos"]
B4["concatenação dos dois conjuntos"]
B5["fecho de Kleene do conjunto"]
end
A0 --> B0
A1 --> B1
A2 --> B2
A3 --> B3
A4 --> B4
A5 --> B5
À esquerda, operações sobre sintaxe; à direita, operações sobre conjuntos. Uma igualdade para cada construtor, e nada além.
O ponto a martelar é a composicionalidade — o significado do todo depende apenas do das partes —, porque é ela que dará forma a todos os algoritmos dos próximos módulos: um caso por construtor, cada caso combinando os resultados dos filhos. Anuncie que a função digitada no bloco de construção é este diagrama transcrito.
Desdobrando (a\mid b)^*a
L(r) = L((a\mid b)^*)\,L(a) = (\{a\}\cup\{b\})^*\{a\} = \{a,b\}^*\{a\}
O conjunto das cadeias terminadas em a.
Exercite a definição uma vez com todo o cuidado, no quadro, passo a passo. Depois faça a turma verificar duas coisas.
Que \varepsilon \notin L(r), porque toda cadeia do conjunto tem ao menos o a final. E que a cadeia a está no conjunto, obtida tomando a cadeia vazia do fecho seguida do a — quarta aparição da distinção da primeira aula, e é aqui que ela paga: sem a cadeia vazia no fecho, a expressão descreveria outra coisa.
Açúcar sintático e a árvore
As formas derivadas são elimináveis
As abreviações
O mais é rr^*; a interrogação é (r\mid\varepsilon); a classe é união finita de símbolos; o ponto é a união do alfabeto.
O preço
Uma classe de vinte e seis letras vira vinte e cinco uniões. Preço de tamanho, não de poder.
A decisão de projeto
Represente apenas os seis construtores na estrutura de dados e monte o resto em termos deles.
O terceiro cartão será cobrado dos grupos adiante, então defenda-o com o número: acrescentar um caso ao tipo enumerado para o sinal de mais parece economizar uma composição e custa caro no módulo seguinte, quando o algoritmo de construção da máquina tiver de tratar doze casos em vez de seis.
É esta decisão que o bloco de construção ao vivo torna concreta. Quem não a digitar uma vez não a respeita depois.
Ler a expressão como árvore, não como texto
flowchart TB
CAT["concatenação"] --> OP1["opcional"]
CAT --> POS["fecho positivo"]
CAT --> OP2["opcional"]
OP1 --> S["sinal de menos"]
POS --> D1["classe de dígitos"]
OP2 --> CAT2["concatenação"]
CAT2 --> P["ponto separador"]
CAT2 --> POS2["fecho positivo"]
POS2 --> D2["classe de dígitos"]
A expressão é a de um número com sinal opcional, parte inteira obrigatória e parte fracionária opcional. Desenhe a árvore no quadro antes de projetar e resolva as perguntas na frente da turma, sempre pela expressão e nunca pela intenção.
Aceita a cadeia vazia? Só se os três fatores puderem produzi-la; o primeiro pode, o terceiro pode, o segundo não, por ser fecho positivo. Logo não aceita — e esse raciocínio, trivial aqui, é o cálculo de anulabilidade que aparecerá algoritmicamente adiante.
Aceita cadeia que começa pelo separador decimal, ou dígito seguido de separador e nada depois? Não e não. Aceita zeros à esquerda? Sim, e isso é decisão de quem escreveu, desde que registrada. Aceita sinal positivo? Não, e a assimetria precisa estar anotada sob pena de parecer erro.
Se a turma não conseguir decidir essas quatro, as definições não foram operacionalizadas — volte antes de seguir.
Terceira votação
Qual construção de uma biblioteca de busca não pode ser reescrita usando apenas os seis construtores?
- o quantificador de uma ou mais repetições;
- a classe de caracteres com faixa;
- o retrovisor, que exige que um trecho já casado reapareça idêntico;
- o ponto, que casa qualquer símbolo.
Resposta: (c). As outras três são açúcar, e vale reconstruir a expansão de cada uma no segundo voto.
O argumento sobre o retrovisor é o mesmo que separou os dois andares inferiores da hierarquia no módulo anterior: reconhecer exige lembrar um trecho de comprimento ilimitado, e a memória de um reconhecedor da classe regular é fixada antes de a entrada ser vista.
Registre a consequência que costuma surpreender: a linguagem das cadeias formadas por um trecho repetido duas vezes não é regular e não é sequer livre de contexto.
Demonstração
O que se digita neste bloco
A estrutura é o conteúdo
Um tipo com exatamente seis casos, as formas derivadas montadas sobre ele, e a semântica como função.
O resto é digitação
Nenhuma peça é longa. O que se aprende aqui é que a definição indutiva e o programa são a mesma coisa em duas notações.
Bloco de construção ao vivo, e ele não é demonstração: avise a sala para abrir o editor e digitar junto. Pause ao fim de cada peça e circule para conferir — não pergunte “todo mundo conseguiu”, que sempre recebe silêncio afirmativo.
Se metade da sala estiver olhando em vez de digitando, pare e espere. O tipo com seis casos digitado à mão é o que torna concreta a decisão de não acrescentar um caso para o sinal de mais.
O tipo com exatamente seis casos
Verbalize, ao digitar, que a ordem dos casos é a da definição escrita no quadro — três bases e três construtores, nada mais. É essa correspondência que faz o próximo trecho sair sozinho.
Quem quiser acrescentar um caso para o sinal de mais vai pedir aqui. É o momento de recusar com o número: o algoritmo do próximo módulo trataria doze casos em vez de seis, para sempre.
As formas derivadas, montadas sobre as primitivas
RegexPtr maisUmRegex(RegexPtr a) {
// A mesma subárvore aparece duas vezes; é o que motiva o ponteiro
// compartilhado em vez do exclusivo.
RegexPtr estrela = estrelaRegex(a);
return concatRegex(std::move(a), std::move(estrela));
}
RegexPtr opcionalRegex(RegexPtr a) {
return uniaoRegex(std::move(a), epsilonRegex());
}A decisão a verbalizar enquanto digita é a de compartilhar a subárvore em vez de duplicá-la: quando o sinal de mais é montado como r seguido de r^*, a mesma subárvore aparece dos dois lados, e apontar duas vezes para ela é a escolha certa por razão estrutural, não por economia de memória.
Peça à turma que escreva a classe entre colchetes com as mesmas duas linhas de ideia: união de símbolos, um por vez. Vinte e seis letras, vinte e cinco uniões — o preço de tamanho, agora visível no laço.
A semântica, um caso por construtor
Linguagem linguagemDe(const Regex& r, std::size_t comprimentoMaximo) {
// Um caso por construtor: a função é a definição indutiva transcrita.
switch (r.tipo) {
case TipoRegex::Vazio:
return Linguagem{};
case TipoRegex::Epsilon:
return Linguagem{vazia()};
case TipoRegex::Simbolo:
return Linguagem{std::string(1, r.simbolo)};
case TipoRegex::Uniao:
return uniao(linguagemDe(*r.esquerda, comprimentoMaximo),
linguagemDe(*r.direita, comprimentoMaximo));
case TipoRegex::Concatenacao:
return concatenacao(linguagemDe(*r.esquerda, comprimentoMaximo),
linguagemDe(*r.direita, comprimentoMaximo),
comprimentoMaximo);
case TipoRegex::Estrela:
return fechoKleene(linguagemDe(*r.esquerda, comprimentoMaximo),
comprimentoMaximo);
}
return Linguagem{};
}Digite este trecho com o quadro à vista, na mesma ordem das seis igualdades escritas no bloco anterior. O objetivo é que a turma veja a mesma coisa em duas notações; diga isso em voz alta, porque nem todo mundo percebe.
Chame a atenção para o que cada caso faz: os três primeiros devolvem conjuntos prontos, os três últimos combinam os resultados dos filhos. É a composicionalidade em execução, e é a forma que todos os algoritmos dos próximos módulos vão repetir.
O limite de comprimento não é detalhe
// Fecho de Kleene: união de todas as potências, da zero em diante. Contém
// sempre a cadeia vazia — inclusive quando a linguagem de partida é vazia.
Linguagem fechoKleene(const Linguagem& a, std::size_t comprimentoMaximo);
// Fecho positivo: idem, mas a partir da potência um. Só contém a cadeia vazia
// se a linguagem de partida já a contiver.
Linguagem fechoPositivo(const Linguagem& a, std::size_t comprimentoMaximo);Nomeie a insuficiência em vez de escondê-la: sem o limite, o laço do fecho não para para nenhuma linguagem que contenha cadeia não vazia. O que se calcula é uma fatia da linguagem, uma janela sobre o conceito, não o conceito.
Amarre à limitação anunciada no cabeçalho: só conseguimos representar linguagens finitas. O objeto infinito ganha representação finita no próximo módulo, quando o autômato entra — e é por isso que ele existe.
O fecho do conjunto vazio, executando
$ peneira --linguagens
A = { a, b }
B = { <vazia>, c } (contém a cadeia vazia)
uniao(A, B) = { <vazia>, a, b, c }
concatenacao(A, B) = { a, ac, b, bc }
A elevado a 0 = { <vazia> } (contém a vazia, não é o conjunto vazio)
A elevado a 2 = { aa, ab, ba, bb }
fecho de Kleene de A, até comprimento 4:
{ <vazia>, a, aa, aaa, aaaa, aaab, aab, aaba, aabb, ab, aba, abaa, ... (19 a mais) }
fecho positivo de A, até comprimento 4:
{ a, aa, aaa, aaaa, aaab, aab, aaba, aabb, ab, aba, abaa, abab, ... (18 a mais) }
fecho de Kleene do conjunto vazio = { <vazia> } (contém a cadeia vazia)
fecho positivo do conjunto vazio = { } (este sim é vazio)Aponte para as duas últimas linhas e retome a votação da primeira aula: quem votou na alternativa errada tem aqui o veredito, produzido pela definição transcrita e não por afirmação sua.
Vale mostrar também a linha da potência zero, que é a mesma distinção outra vez. Quem contar as cadeias do fecho positivo vai notar que ele tem exatamente uma a menos que o de Kleene nesta fatia — e é a cadeia vazia.
A bateria de identidades, executando
$ peneira --regex
expressao: (a|b)*
linguagem ate comprimento 4: { <vazia>, a, aa, aaa, aaaa, aaab, aab, aaba, aabb, ab, aba, abaa, ... (19 a mais) }
expressao: aa* (a+ montado como a a*)
linguagem ate comprimento 4: { a, aa, aaa, aaaa }
identidades algebricas, conferidas ate comprimento 4:
(a|b)* == (a*b*)* : confere
a** == a* : confere
ab == ba : diverge (esperado: diverge)
Concordar ate um comprimento e evidencia, nao demonstracao.
A prova de equivalencia chega no modulo 5.Note em voz alta o terceiro caso: além dos dois que devem conferir, incluímos um que deve divergir. Uma bateria em que tudo passa não prova que a verificação funciona — pode ser que ela sempre responda “confere”. É o mesmo princípio de escolher o caso de teste que revela o defeito.
A primeira identidade impressa é exatamente a que será demonstrada à mão no bloco seguinte. Diga isso ao projetar: aqui há evidência até o comprimento quatro; lá haverá demonstração para todo comprimento.
O que a construção deixou provado
A evidência
As identidades conferem até o comprimento examinado, e o caso que devia divergir divergiu.
A confirmação do desenho
Seis casos no tipo bastaram: as formas derivadas se montaram sem nenhum caso novo.
O preço
O que se calcula é uma fatia da linguagem, limitada por comprimento. Sem esse limite o laço do fecho não para.
Uma bateria em que tudo passa não prova que a verificação funciona — pode ser que ela sempre responda “confere”.
O terceiro cartão é o que separa demonstração de propaganda e precisa ser dito em voz alta: o programa não representa o conceito, representa uma janela sobre ele. O objeto infinito só ganha representação finita no próximo módulo, quando a máquina entrar.
Se alguém perguntar aqui como se reconhece de verdade, responda que a máquina é o assunto do próximo módulo, que ela tem memória finita e não volta atrás, e siga. Ceder aqui consome os dois blocos que faltam.
A álgebra, e o que ela não consegue fazer
As identidades que se usam para raciocinar
Estrutura
Neutros e absorventes; distributividade sobre a união.
Fecho
r^* \equiv \varepsilon \mid rr^* é a forma recursiva do fecho. r^{**} \equiv r^* é a idempotência.
O desdobramento do fecho é a base do algoritmo que constrói autômatos a partir de expressões; a idempotência é a chave do último bloco.
Monte no quadro apenas estas, e não a tabela inteira: a tabela é o que a turma copia e não usa.
Anuncie as duas dívidas do slide — o desdobramento paga no próximo módulo, a idempotência paga daqui a dois blocos — para que ninguém trate a lista como decoração.
O passo que depende da cadeia vazia
(r\mid s)^* \equiv (r^*s^*)^*
Com A = L(r) e B = L(s): se w_i \in A, então w_i \in A^*B^* tomando a parte de B vazia — e isso exige \varepsilon \in B^*.
Faça a demonstração inteira no quadro; escolhi esta porque as duas inclusões têm dificuldades diferentes. Da esquerda para a direita, toda w é concatenação de cadeias w_i, cada uma em A ou em B.
Pare exatamente no passo do slide e aponte o dedo para ele: sem a cadeia vazia no fecho, a inclusão falharia. É a melhor evidência disponível de que a distinção martelada na primeira aula é o que faz as demonstrações fecharem.
Feche o bloco com a limitação, que é o ponto mais importante dele: a manipulação algébrica é excelente para demonstrar equivalências e péssima para refutá-las — não achar o caminho não demonstra que as expressões diferem. Para refutar, exiba uma cadeia que pertence a uma linguagem e não à outra. Uma cadeia é uma testemunha, e uma testemunha encerra a questão.
Quatro resultados, com autoria e data
Axiomatização
Redko, 1964: nenhum conjunto finito de identidades puramente equacionais é completo. Salomaa, 1966: sistemas completos, com uma regra de inferência com hipótese.
Equação e decisão
Arden, 1961: X = AX \cup B tem solução única X = A^*B quando \varepsilon \notin A. Stockmeyer e Meyer, 1973: a equivalência é decidível, e PSPACE-completa.
Concordância até um comprimento dado é evidência, não demonstração: duas expressões podem coincidir até o comprimento dez e divergir no onze.
Dê os quatro com autoria e data, porque é isso que os torna verificáveis pela turma em vez de afirmação sua.
Mostre que a hipótese de Arden é necessária: com A = \{\varepsilon\} e B = \emptyset, qualquer X satisfaz a equação.
A nota é a consequência metodológica sobre o programa do bloco anterior, e vale enunciá-la olhando para a tela: a decisão de verdade chega com a unicidade do autômato mínimo, adiante.
A fronteira, e a volta ao gancho
O critério cabe numa pergunta
flowchart TB
N["Construção oferecida por uma notação de biblioteca"] --> Q{"Pode ser reescrita<br/>usando só os seis construtores"}
Q -->|sim| DENTRO["Açúcar sintático<br/>quantificadores, classes, faixas, ponto"]
Q -->|não| FORA["Fora da classe regular<br/>retrovisores, olhares gerais, recursão"]
DENTRO --> LIN["Máquina de memória finita<br/>tempo proporcional à entrada"]
FORA --> EXP["Retrocesso<br/>risco de custo exponencial"]
A pergunta é uma só: isto pode ser expandido nos seis construtores? Use-a para reconduzir a digressão “mas na minha biblioteca funciona”, que aparece sem falta neste bloco, às vezes com o estudante já testando no celular.
Dentro: quantificadores, contadores, classes com faixa e negação, ponto, classes nomeadas, agrupamento e alternação. As âncoras de início e fim de texto são o caso interessante — falam sobre posição e não sobre a cadeia, o que expressam continua na classe regular, e existem porque a maioria das bibliotecas resolve o problema de busca e não o de reconhecimento. Num compilador, em que se reconhece um lexema completo a partir de uma posição, elas não fazem falta.
Fora, em três famílias: retrovisores, pelo argumento da memória ilimitada; olhares adiante e atrás em versão geral; e construções recursivas, que nem fingem — são um mecanismo de pilha dentro da notação. Registre que Alfred Aho, no capítulo sobre algoritmos de busca de padrões em cadeias do Handbook of Theoretical Computer Science, publicado em 1990, consignou que decidir se uma cadeia casa com um padrão contendo retrovisores é NP-completo.
Duas estratégias, e a conta do retrocesso
Converter em máquina
Passa a entrada uma vez. Tempo proporcional ao comprimento, independente da forma do padrão.
Retroceder
Tenta alternativas e volta quando falham. É o que suporta retrovisores e olhares — e o que quase toda biblioteca de propósito geral adota.
Com (a^*)^*b sobre trinta letras a, cada partição dos a entre as duas repetições é uma alternativa distinta, e todas são tentadas antes de concluir que não há casamento.
Volte ao quadro da abertura e pague a dívida na ordem em que ela foi contraída.
Pela idempotência do fecho — a identidade do bloco anterior —, (a^*)^*b é equivalente a a^*b, que é reconhecida trivialmente. Mesma linguagem, mesma biblioteca, custos incomparáveis: a diferença está na estratégia combinada com a forma do padrão, e não no conjunto descrito.
O caso real
Cloudflare, 2 de julho de 2019
A empresa publicou relatório atribuindo uma interrupção global do seu serviço a uma regra recém-implantada que continha um padrão com retrocesso catastrófico.
O defeito não estava no conjunto descrito, nem apenas na notação usada, e sim na combinação dessa notação com uma estratégia de reconhecimento que paga caro por certas formas de padrão.
Enuncie a lição olhando para as três palavras do canto do quadro, que estão lá desde a abertura da primeira aula. É a última vez que elas aparecem, e o fecho do arco.
A frase que a turma leva para casa: quem conhece a fronteira prevê a categoria do problema; quem aprendeu por imitação, não.
Síntese
Uma linguagem é qualquer subconjunto de \Sigma^*, quase todas são indescritíveis, e a classe que uma notação de seis construtores alcança é exatamente a que se descreve com texto finito — sendo o custo de reconhecer essa descrição uma propriedade da estratégia, não do conjunto.
Cadeia monoide livre sobre o alfabeto
Vazio \emptyset não é \{\varepsilon\}
Seis três bases, três construtores
Fronteira açúcar ou fora da classe
Retome os três objetivos do primeiro slide, um a um, citando o que das duas aulas serve de evidência para cada um.
Anuncie o que a tutoria vai cobrar: a especificação léxica completa da linguagem do grupo, com corpora de aceitação e de rejeição e os casos de fronteira identificados como tais. Deixe claro que a ausência de código na entrega é decisão, não folga — o analisador léxico depende de teoria que ainda não chegou —, e que uma especificação frouxa não se manifesta agora: cobra o preço no módulo seguinte, quando não houver contra o que verificar o reconhecedor construído.
Se o tempo apertar, o que se corta é o slide dos quatro resultados com autoria; a distinção entre o vazio e a cadeia vazia, nunca.
Referências
- LOUDEN, Kenneth C. Compiladores: princípios e práticas. São Paulo: Cengage Learning, 2004.
- AHO, Alfred V. Compiladores: princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson Education do Brasil, 2008.
- MENEZES, Paulo B. Linguagens formais e autômatos. v. 3, 6. ed. Porto Alegre: Grupo A, 2011.
- AHO, Alfred V. Algorithms for Finding Patterns in Strings. In: Handbook of Theoretical Computer Science, v. A. Amsterdam: Elsevier, 1990.
- STOCKMEYER, L. J.; MEYER, A. R. Word Problems Requiring Exponential Time. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, p. 1-9, 1973.