flowchart LR
A["Símbolo<br/>objeto primitivo do alfabeto"] --> B["Cadeia<br/>sequência finita de símbolos"]
B --> C["Todas as cadeias sobre o alfabeto<br/>infinito, mas enumerável"]
C --> D["Linguagem<br/>qualquer subconjunto desse universo"]
D --> E["Linguagem regular<br/>a que alguma expressão descreve"]
1 Módulo 2: Alfabetos, Linguagens e Expressões Regulares — Resumo
Esta é a versão de revisão. Recapitulo em ritmo de véspera o vocabulário formal que sustenta a primeira metade da disciplina; nada é demonstrado por inteiro, e para isso existem a versão completa do material deste módulo e o livro. O critério aqui é operacional: você tem de usar estas definições, não só reconhecê-las.
Você já copiou um padrão de busca da internet, colou no código, funcionou, e duas semanas depois apareceu o caso que ele rejeita e não deveria. Aí mudou um caractere, testou, mudou outro. Não faltou esforço: faltou modelo. Este módulo constrói esse modelo pelo fundo, que é onde a intuição erra. E já aviso o inimigo: a cadeia vazia.
1.1 Símbolo, alfabeto, cadeia
Um alfabeto \Sigma é um conjunto finito e não vazio de símbolos. A teoria não diz o que é um símbolo: ele é primitivo. Podem ser caracteres ou categorias léxicas vindas de uma fase anterior do compilador, e é essa indiferença que permite reusar o mesmo aparato em dois níveis do sistema. A finitude não é decorativa: os algoritmos dos próximos módulos indexam tabelas por símbolo, e alfabeto infinito não quebra o código, quebra os teoremas.
Uma cadeia sobre \Sigma é uma sequência finita de símbolos, e \lvert w \rvert os conta com repetição. A de comprimento zero é a cadeia vazia, \varepsilon. Com \Sigma^n para as cadeias de comprimento exatamente n, o universo é
\Sigma^* = \bigcup_{n \ge 0} \Sigma^n \qquad\text{e}\qquad \Sigma^+ = \bigcup_{n \ge 1} \Sigma^n .
E aqui está o detalhe que decide o módulo: \Sigma^0 = \{\varepsilon\}, e não o conjunto vazio. Existe exatamente uma maneira de não escrever nada. Escreva \emptyset e \{\varepsilon\} lado a lado até a diferença virar automática.
A operação que sustenta tudo é a concatenação: uv tem os símbolos de u seguidos dos de v. É associativa, tem \varepsilon como neutro e não é comutativa, porque sobre \{a,b\} já vale ab \ne ba. Guarde: soma comutativa e produto não comutativo — trocar fatores de lugar por analogia com a aritmética da escola é o erro que mais aparece.
Três relações merecem nome: x é prefixo de w quando w = xv, sufixo quando w = ux e subcadeia quando w = uxv. O que some quando alguém enumera à mão é sempre o mesmo — a cadeia vazia é as três coisas de qualquer cadeia, e toda cadeia é as três de si mesma. E ac não é subcadeia de abc: subcadeia exige contiguidade, sem a qual o nome muda para subsequência.
Pare e pense. Toda cadeia elevada a zero devolve a cadeia vazia — inclusive a própria cadeia vazia. Por que isso é forçado pela definição, e não convenção? Escreva a recursão da potência e olhe o primeiro passo.
E não esqueça: a escolha do alfabeto é decisão de projeto, cara de reverter — com os pontos de código de um sistema de escrita universal, nenhuma tabela de transição direta serve, e passa-se a indexar por faixas.
1.2 Linguagens: conjuntos de cadeias
Uma linguagem sobre \Sigma é um subconjunto qualquer de \Sigma^* — e é essa generosidade quase escandalosa que dá alcance ao aparato. Os identificadores válidos de uma linguagem de programação formam uma linguagem; os programas sintaticamente corretos formam outra; os que terminam também. A única diferença que a teoria enxerga é a dificuldade de decidir a pertinência.
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
União, interseção e diferença se aplicam sem novidade. O complemento pede cuidado, porque depende do alfabeto: a mesma L = \{a\} tem complementos diferentes conforme \Sigma seja \{a\} ou \{a,b\}, e falar dele sem fixar \Sigma é falar de algo indefinido. A operação nova estende a concatenação aos conjuntos:
L_1 L_2 = \{\, uv \mid u \in L_1 \ \text{e} \ v \in L_2 \,\}.
Contar ocorrências não é contar objetos: com L_1 = \{a, ab\} e L_2 = \{b, \varepsilon\} há quatro pares e três cadeias no resultado. A operação é associativa, não comutativa, tem \{\varepsilon\} como neutro e \emptyset como absorvente. Distribui sobre a união e falha sobre a interseção, e a razão reaparece na ambiguidade de gramáticas: a concatenação perde a informação de onde estava a fronteira.
Com L^{n+1} = L^n L e L^0 = \{\varepsilon\}, chegamos ao fecho de Kleene e ao fecho positivo:
L^* = \bigcup_{n \ge 0} L^n \qquad\text{e}\qquad L^+ = \bigcup_{n \ge 1} L^n .
O nome é de Stephen Kleene, que introduziu a operação ao caracterizar os eventos representáveis em redes de autômatos finitos, no volume Automata Studies de 1956. Sem o fecho, o que se descreve a partir de conjuntos finitos continua finito. Duas consequências, por derivação e nunca por decoreba. L^* sempre contém \varepsilon, porque a potência zero está na união; L^+ só a contém se L já a continha. E \emptyset^* = \{\varepsilon\} enquanto \emptyset^+ = \emptyset — forçado pela álgebra, já que com L^0 vazio teríamos L^1 = \emptyset para toda linguagem.
As duas identidades que todo mundo troca. Concatenar com a linguagem que só contém a cadeia vazia devolve a linguagem inteira; concatenar com a linguagem vazia devolve a linguagem vazia, porque não há cadeia alguma para começar o par. O neutro é a caixa com uma folha em branco; o absorvente é a caixa fechada.
Daí a dificuldade que motiva a segunda metade do módulo. Linguagens interessantes são infinitas e não se descrevem por extensão. Pior: as linguagens formam uma coleção não enumerável e as descrições finitas, uma enumerável — quase todas ficam sem descrição, em qualquer notação que se invente. A pergunta muda para: que classe vale a pena descrever?
1.3 Expressões regulares: seis construtores e nada mais
Fixado o alfabeto, o conjunto das expressões regulares é o menor conjunto tal que: o vazio é expressão; a cadeia vazia é expressão; cada símbolo é expressão; e, se r e s são expressões, então (r \mid s), (rs) e (r^*) também. Três casos-base, três construtores, fim. Cuidado: \emptyset e \varepsilon aparecem aqui como elementos da sintaxe e antes como objetos semânticos — é a diferença entre a palavra e a coisa. Por precedência, estrela liga mais forte, depois concatenação, depois união; então ab^* é a seguido do fecho de b.
A semântica se define pela mesma indução que definiu a sintaxe:
L(\emptyset) = \emptyset, \qquad L(\varepsilon) = \{\varepsilon\}, \qquad L(a) = \{a\}, L(r \mid s) = L(r) \cup L(s), \qquad L(rs) = L(r)\,L(s), \qquad L(r^*) = L(r)^* .
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 texto; à direita, sobre conjuntos; e a correspondência é composicional — o significado do todo depende só do das partes. É ela que dá forma a todo algoritmo dos próximos módulos, um caso por construtor.
Se são só seis construtores, de onde vem tudo o que você já viu? De açúcar sintático: o mais é a expressão concatenada com o próprio fecho, a interrogação é a união com a cadeia vazia, uma classe entre colchetes é a união dos símbolos listados, o ponto é a união do alfabeto. Tudo eliminável mecanicamente, e o preço é tamanho, não poder. Daí a recomendação: represente só os seis na estrutura de dados e monte as derivadas em cima deles, como faz a implementação de referência da Peneira.
enum class TipoRegex : std::uint8_t {
Vazio, // denota a linguagem { }
Epsilon, // denota a linguagem { cadeia vazia }
Simbolo, // denota a linguagem { "c" }
Uniao,
Concatenacao,
Estrela,
};
struct Regex {
TipoRegex tipo;
char simbolo; // significativo quando tipo == Simbolo
RegexPtr esquerda; // subexpressão; nula nos casos-base
RegexPtr direita; // segunda subexpressão; nula fora de União/Concatenação
};Acrescentar um caso para o sinal de mais parece economia e custa caro no módulo seguinte, quando o algoritmo que converte expressão em máquina tiver doze casos em vez de seis. E o hábito que quero incutir: leia a expressão como árvore, não como texto. Assim quase toda pergunta responde sozinha — ela aceita a cadeia vazia? Só se todos os fatores da concatenação puderem produzi-la. Esse raciocínio é o que faremos adiante sob o nome de anulabilidade.
1.4 A álgebra dessas expressões
Escrevemos r \equiv s quando L(r) = L(s). A definição desloca uma pergunta sobre texto para uma sobre conjuntos: demonstra-se equivalência por dupla inclusão.
| Identidade | Nome |
|---|---|
| r \mid s \equiv s \mid r | comutatividade da união |
| r \mid \emptyset \equiv r | neutro da união |
| \varepsilon r \equiv r \varepsilon \equiv r | neutro da concatenação |
| \emptyset r \equiv r \emptyset \equiv \emptyset | absorvente da concatenação |
| \emptyset^* \equiv \varepsilon | fecho do vazio |
| r^{**} \equiv r^* | idempotência do fecho |
| r^* \equiv \varepsilon \mid r r^* | desdobramento do fecho |
| (r \mid s)^* \equiv (r^* s^*)^* | fecho da união |
Uma delas serve para raciocinar, não só para encolher expressão: o desdobramento do fecho diz que uma cadeia do fecho ou é vazia, ou começa com uma cadeia da base seguida de outra do fecho — é a forma recursiva que fundamenta a construção de autômatos e a repetição nas gramáticas.
Agora o ponto mais importante, e ele é uma limitação: a manipulação algébrica é excelente para demonstrar e péssima para refutar. Se você manipulou meia hora e não transformou r em s, isso não mostra que são diferentes; mostra que você não achou o caminho. Para refutar, exiba uma cadeia que está em uma linguagem e não na outra — uma testemunha encerra a questão.
flowchart TB
P["Duas expressões denotam a mesma linguagem"] --> D["Suspeita de que sim"]
P --> R["Suspeita de que não"]
D --> DA["Cadeia de identidades da tabela<br/>cada passo justificado"]
DA --> OK["Equivalência demonstrada"]
DA -.-> NADA["Não achei o caminho<br/>isso não conclui coisa alguma"]
R --> RT["Exibir uma cadeia que está em uma<br/>e não está na outra"]
RT --> NO["Equivalência refutada pela testemunha"]
Concordância não é demonstração. Comparar duas expressões gerando as cadeias das duas linguagens até um comprimento dado pega quase todo erro de prática, mas não demonstra equivalência: elas podem coincidir até o comprimento dez e divergir no onze. É evidência, não prova — e um programa que funciona induz justamente a esquecer a diferença.
Três resultados delimitam o método. Redko demonstrou, em 1964, que nenhum conjunto finito de identidades puramente equacionais é completo para a equivalência de expressões regulares: um catálogo como o da tabela sempre deixa alguma equivalência verdadeira de fora. Salomaa obteve, em 1966, sistemas completos ao acrescentar uma regra de inferência com hipótese. E decidir equivalência, embora decidível, é PSPACE-completo, resultado de Stockmeyer e Meyer de 1973. Vale ainda a regra de Arden, de 1961: se \varepsilon \notin A, então X = AX \cup B tem solução única X = A^*B — com A = \{\varepsilon\} a unicidade evapora, de novo a cadeia vazia decidindo tudo.
1.5 A fronteira com as notações de biblioteca
A afirmação é forte: boa parte do que as bibliotecas chamam de “expressão regular” não é expressão regular. Ken Thompson publicou em 1968, nas Communications of the ACM, um algoritmo que construía um reconhecedor executável a partir de uma expressão regular e o incorporou ao editor em que trabalhava; dessa linhagem saiu a ferramenta de busca por padrões do Unix. No caminho, cada ferramenta acrescentou o que lhe convinha — parte açúcar inofensivo, parte construção que empurra o poder expressivo para fora da classe e, com ele, o custo do reconhecimento.
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"]
Do lado de dentro ficam quantificadores, contadores, classes de caracteres, o ponto, agrupamento e alternação: tudo expandível nos seis construtores, com alfabeto finito. As âncoras de início e fim são caso intermediário — falam de posição e não de cadeia, então não são expressões regulares pela definição, mas o que expressam continua na classe. Do lado de fora ficam retrovisores, olhares de comprimento variável e construções recursivas, que nem fingem: são um mecanismo de pilha dentro da notação de padrões.
Reconhecer “um trecho qualquer, seguido de qualquer coisa, seguido do mesmo trecho” exige lembrar conteúdo ilimitado, e a memória de um reconhecedor regular é finita e fixada antes de a entrada ser vista. Alfred Aho registrou, no capítulo sobre algoritmos de busca de padrões do Handbook of Theoretical Computer Science, de 1990, que decidir se uma cadeia casa com um padrão contendo retrovisores é NP-completo. Isso aparece na fatura de tempo de execução. A estratégia do próximo módulo converte o padrão em máquina e passa a entrada por ela sem voltar atrás, em tempo linear; a outra é o retrocesso, adotado por quase toda biblioteca — só que o número de alternativas pode crescer exponencialmente. Em 2 de julho de 2019 a Cloudflare publicou um relatório atribuindo uma interrupção global do seu serviço exatamente a isso.
O critério prático, numa frase. Se, para reconhecer o padrão, é preciso lembrar algo de tamanho ilimitado — um trecho já casado, uma contagem de aninhamento —, ele não é regular. Se cabe numa quantidade fixada antes de a entrada ser lida, há reconhecimento em tempo linear.
Para quem projeta uma notação: inclua o açúcar, exclua o que muda a classe. Aqui a teoria não explica a decisão; ela a toma.
1.6 O caso conduzido e o que o seu grupo entrega
Toda a teoria converge para uma tarefa concreta: descrever, com precisão total, as categorias léxicas de uma linguagem. Um programa da Peneira tem nomes, números, textos entre aspas, padrões entre barras, pontuação e espaços — seis categorias, cada uma com a expressão que a descreve, a decisão de projeto registrada e dois corpora, o das cadeias aceitas e o das rejeitadas. Três decisões ilustram a teoria: os números aceitam zeros à esquerda, registrado como escolha e não como descuido; os textos não têm sequências de escape, porque uma aspa escapada exigiria um analisador com estado dentro do analisador léxico; e o literal de padrão é bloco opaco, de barra a barra, porque quem olha dentro dele é outro componente, módulos adiante.
A entrega do seu grupo é o análogo disso: especificação léxica completa, todas as categorias em notação de expressões regulares, com os conjuntos de aceitação e rejeição e os casos de fronteira identificados como tais. Não há código exigido — avalia-se a precisão. E o erro de método que vou combater o semestre inteiro é especificar por exemplo em vez de especificar por expressão: dizer que “números são coisas como 42 ou 3.14” é ilustração. Teste de qualidade: escolha uma cadeia esquisita e pergunte se é aceita. Se a resposta sai sem hesitação, está boa; se você precisa deliberar, ela está frouxa — e a frouxidão será resolvida sem registro quando alguém escrever o código.
1.7 Síntese
Partimos de três primitivos: alfabeto finito e não vazio, cadeia como sequência finita de símbolos, concatenação associativa com neutro \varepsilon e sem comutatividade. Subimos para as linguagens, subconjuntos quaisquer de \Sigma^* — e é o fecho que produz infinitude a partir de descrição finita. Sobre essa base entraram as expressões regulares, com sintaxe indutiva e semântica definida pela mesma indução. Tudo o que a notação prática oferece além disso ou é açúcar eliminável ao custo de tamanho, ou está fora da classe e muda o problema — e a fatura dessa mudança tem nome, data e serviço derrubado.
Falta a este módulo, de propósito, uma coisa: aprendemos a descrever linguagens e não sabemos reconhecê-las — a única implementação que esta teoria permite é enumerar cadeias e procurar na lista, o que não termina para linguagem infinita alguma. É por isso que o próximo módulo existe. E se você retiver uma coisa só, que seja a diferença entre a linguagem vazia e a que contém a cadeia vazia.