Expressões regulares e linguagens regulares — Atlas

O módulo inteiro em oito peças visuais. Cada uma olha o mesmo conteúdo por um lado: o resumo desenhado, os procedimentos passo a passo, os cartões para treinar de memória, o módulo contado em quadros, o mapa dos tópicos, o painel que junta tudo, a rede de conceitos e a folha para consultar na hora.

Resumo ilustrado

Resumo ilustrado em nove quadros. 1, o molde: a* denota o conjunto infinito ε, a, aa, aaa. 2, o núcleo: colar, escolher e repetir, com as folhas símbolo e ε. 3, a precedência: primeiro repetir, depois colar, por último escolher. 4, a árvore de a|bc, com a escolha na raiz e cinco nós. 5, o conjunto calculado das folhas para a raiz: {b} e {c} dão {bc}, que unido a {a} dá {a, bc}. 6, o vazio denota nenhuma cadeia e a cadeia vazia denota uma; o fecho do vazio é {ε}. 7, os atalhos custam nós: [a-z] tem cinco caracteres e 51 nós. 8, (a|b)* e (a*b*)* têm árvores diferentes e a mesma linguagem; a*b* e (a|b)* não são equivalentes, e ba é a testemunha. 9, o fechamento é uma cerca: unir, colar e repetir ficam dentro; contar tantos a quanto b e a retrovisão ficam fora.
Figura 1: O módulo numa página: o molde, o núcleo, a precedência, a árvore, o cálculo do conjunto, o vazio contra a cadeia vazia, o custo dos atalhos, a equivalência e a cerca do fechamento.

Fluxogramas

Cinco procedimentos do módulo. Siga cada um com o lápis, sobre uma expressão sua.

Ler o padrão e montar a árvore

Quatro funções, uma chamando a outra. A ordem das chamadas é a precedência: quem é chamado por último prende com mais força.

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    T["texto do padrão"]
    A["alternancia: lê uma concatenação"]
    C["concatenacao: lê uma repetição"]
    R["repeticao: lê um átomo"]
    AT{"atomo:<br/>o que vem?"}
    F["uma folha"]
    G["lê uma alternância<br/>e exige o )"]
    K["a classe de símbolos<br/>vira alternância de folhas"]
    E["erro, com a posição<br/>em que a falta se constata"]

    T --> A --> C --> R --> AT
    AT -->|"símbolo ou ."| F
    AT -->|"("| G
    AT -->|"["| K
    AT -->|"nada disso"| E

Figura 2: A descida: alternância chama concatenação, que chama repetição, que chama átomo. 

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    S["o átomo lido: a árvore x"]
    RQ{"vem *, + ou ?"}
    RS["fecho(x) para o *<br/>concat(x, fecho(x)) para o +<br/>alt(x, vazio) para o ?"]
    CQ{"começa outro átomo<br/>logo em seguida?"}
    CJ["lê a repetição seguinte;<br/>concat(esquerda, direita)<br/>vira a nova esquerda"]
    AQ{"vem uma barra |?"}
    AJ["lê a concatenação seguinte;<br/>alt(esquerda, direita)<br/>vira a nova esquerda"]
    FIM["árvore pronta"]

    S --> RQ
    RQ -->|"sim"| RS --> RQ
    RQ -->|"não"| CQ
    CQ -->|"sim"| CJ --> CQ
    CQ -->|"não"| AQ
    AQ -->|"sim"| AJ --> AQ
    AQ -->|"não"| FIM

Figura 3: A volta: cada função monta a sua parte da árvore, em laço, pela esquerda. Os atalhos já viram núcleo aqui, durante a leitura.

Calcular o conjunto que a expressão denota

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    I["árvore do padrão"]
    F{"que folha é?"}
    F1["vazio: ∅"]
    F2["cadeia vazia: {ε}"]
    F3["símbolo a: {a}"]
    S{"o nó de cima<br/>é qual operador?"}
    U["escolher: une os<br/>conjuntos dos filhos"]
    K["colar: cada cadeia do primeiro<br/>seguida de cada cadeia do segundo"]
    P["repetir: junta as potências,<br/>a começar pela potência zero, {ε}"]
    Q{"chegou à raiz?"}
    L["o conjunto da raiz é L(r)"]

    I --> F
    F --> F1
    F --> F2
    F --> F3
    F1 --> S
    F2 --> S
    F3 --> S
    S --> U
    S --> K
    S --> P
    U --> Q
    K --> Q
    P --> Q
    Q -->|"não, sobe um nível"| S
    Q -->|"sim"| L

Figura 4: O cálculo de L(r): cada folha dá um conjunto imediato, e cada operador combina os conjuntos dos filhos, das folhas até a raiz.

Reduzir um atalho ao núcleo

%%{init: {"flowchart": {"useMaxWidth": false, "rankSpacing": 30, "nodeSpacing": 30}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
    Q{"qual atalho<br/>a leitura<br/>encontrou?"}
    M["x+ vira concat(x, fecho(x))<br/>a subárvore de x aparece duas vezes"]
    O["x? vira alt(x, vazio)<br/>é por aqui que ε entra na árvore"]
    E["[abc] vira a alternância<br/>das folhas a, b e c"]
    R["[a-c] vira [abc],<br/>e daí a alternância"]
    W["o coringa . fica como folha própria:<br/>redutível, mas a expansão teria<br/>quase uma centena de folhas"]
    Z["x{3,5} fica fora da notação:<br/>redutível, descartado por utilidade"]
    N["núcleo: colar,<br/>escolher, repetir;<br/>folhas: símbolo e ε"]

    Q --> M
    Q --> O
    Q --> E
    Q --> R
    Q --> W
    Q --> Z
    M --> N
    O --> N
    E --> N
    R --> N

Figura 5: Cada atalho e o que ele vira. Duas exceções: o coringa fica, por tamanho; o quantificador contado sai da notação, por utilidade.

Decidir se duas expressões são equivalentes

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    D["duas expressões, r e s"]
    RD["lê e reduz as duas ao núcleo"]
    C{"as formas prefixas<br/>são o mesmo texto?"}
    S["equivalentes: a mesma árvore<br/>denota a mesma linguagem"]
    N["nada decidido ainda:<br/>árvores diferentes podem<br/>denotar a mesma linguagem"]
    T{"existe uma cadeia que está<br/>numa linguagem e falta na outra?"}
    NE["não equivalentes:<br/>a cadeia é a testemunha"]
    P["a decisão plena compara<br/>as máquinas mínimas, no módulo 05"]

    D --> RD --> C
    C -->|"sim"| S
    C -->|"não"| N --> T
    T -->|"achei uma"| NE
    T -->|"não achei"| P

Figura 6: Árvores iguais depois da redução decidem a favor. Árvores diferentes não decidem nada: falta procurar uma testemunha, ou comparar as máquinas mínimas, no módulo 05.

Saber se um requisito cabe na classe regular

%%{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 máquina<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 expressão que denota<br/>a linguagem do requisito"]
    F["fica fora da classe:<br/>nenhuma expressão denota<br/>a linguagem do requisito"]

    R --> P1 --> P2 --> P3
    P3 -->|"sim, teto fixo"| D
    P3 -->|"não, cresce com o texto"| F

Figura 7: Três perguntas sobre a memória que a máquina precisaria ter. Teto fixo: cabe. Memória que cresce com o texto: fica fora.

Cartões de memória

Leia a frente, diga a resposta em voz alta ou escreva no papel, e só então vire o cartão.

Definição: Expressão regular sobre um alfabeto
Seja \Sigma um alfabeto. O conjunto das expressões regulares sobre \Sigma é definido por indução: \emptyset é uma expressão regular; \varepsilon é uma expressão regular; a é uma expressão regular, para cada a \in \Sigma; e, se r e s são expressões regulares, então (r \mid s), (rs) e (r^*) também são. Nada mais é expressão regular.
Definição: Árvore sintática de uma expressão regular
Uma árvore é um conjunto finito de nós em que cada nó tem uma sequência ordenada de filhos e em que todo nó, exceto um — a raiz —, é filho de exatamente um outro nó. Nó sem filhos chama-se folha, e a subárvore de um nó é esse nó com todos os seus descendentes. A árvore sintática de uma expressão regular r sobre \Sigma é definida pela mesma indução da definição Expressão regular sobre um alfabeto: se r é \emptyset, \varepsilon ou a \in \Sigma, a árvore de r é uma folha rotulada com esse símbolo; se r é (s \mid t) ou (st), a árvore de r tem raiz rotulada com o operador e por filhos, nessa ordem, as árvores de s e de t; e se r é (s^*), a raiz é rotulada com o fecho e tem por único filho a árvore de s. Duas expressões têm a mesma árvore quando os rótulos e a ordem dos filhos coincidem em todos os nós.
Definição: A linguagem denotada
A linguagem denotada por uma expressão regular r, escrita L(r), é definida pela mesma indução: L(\emptyset) = \emptyset; L(\varepsilon) = \{\varepsilon\}; L(a) = \{a\} para a \in \Sigma; L(r \mid s) = L(r) \cup L(s); L(rs) = L(r)\,L(s); e L(r^*) = L(r)^*.
Definição: Linguagem regular
Uma linguagem L \subseteq \Sigma^* é regular quando existe uma expressão regular r sobre \Sigma tal que L(r) = L.
Definição: Equivalência de expressões
Duas expressões regulares r e s sobre \Sigma são equivalentes, escrito r \equiv s, quando L(r) = L(s). A equivalência é relação entre as linguagens denotadas, e não entre os textos das expressões nem entre as estruturas construídas a partir deles.
Teorema: Fechamento sob as três operações
Se L_1 e L_2 são linguagens regulares sobre \Sigma, então L_1 \cup L_2, L_1 L_2 e L_1^* são regulares. A demonstração é imediata pela definição Expressão regular sobre um alfabeto: dadas expressões r_1 e r_2 com L(r_1) = L_1 e L(r_2) = L_2, as expressões (r_1 \mid r_2), (r_1 r_2) e (r_1^*) são expressões regulares por construção, e a definição A linguagem denotada lhes atribui exatamente aquelas linguagens.
Expressão regular
Notação que descreve uma linguagem por indução: o vazio, a cadeia vazia e cada símbolo do alfabeto são casos base, e alternância, concatenação e repetição combinam descrições já formadas. Nada além do que essas regras produzem pertence à notação.
Fecho positivo
Operação que forma, a partir de uma linguagem, o conjunto de todas as concatenações de uma ou mais cadeias dela. Não inclui a cadeia vazia, salvo quando esta já pertencia à linguagem de partida.
Linguagem denotada
Conjunto de cadeias que uma expressão regular descreve, obtido percorrendo a estrutura da expressão: cada caso base dá um conjunto imediato, e cada operador dá a operação correspondente sobre conjuntos.
Linguagem livre de contexto
Conjunto de cadeias gerado por alguma gramática cujas produções têm um único não terminal do lado esquerdo. Equivale à família reconhecida pelos autômatos de pilha, e contém estritamente a família regular.
Padrão
Descrição da forma que os trechos de uma dada categoria podem assumir. Nesta obra é uma expressão regular sobre o alfabeto do texto de origem, e o conjunto que ela denota é o de todos os trechos daquela categoria.
Expansão
Sequência de instruções do repertório do alvo cujo efeito coincide com o de uma operação que esse repertório não oferece. O custo mede-se em instruções adicionais por ocorrência.

História em quadros

O módulo contado do começo ao fim, um quadro por passo, na ordem em que o livro avança.

História em quadros, doze quadros em quatro linhas. 1, um molde de dois caracteres: a* denota ε, a, aa, aaa, e a lista não acaba. 2, três datas: 1951, Kleene, neurônios; 1968, Thompson, ler o texto uma vez sem voltar; 2019, Cloudflare, o fragmento .*.*=.* com custo que cresce com o cubo. 3, as seis cláusulas: as folhas ∅, ε e a; as composições (r|s), (rs) e (r*); nada mais é expressão. 4, quem prende primeiro: repetir, depois colar, por último escolher; abc vira concat(concat(a,b),c). 5, a árvore passo a passo: a tem 1 nó, ab 3, a|bc 5, (a|b)*c 6; os parênteses custam zero nós. 6, da árvore ao conjunto: {b} e {c} dão {bc}, que unido a {a} dá {a, bc}; uma linguagem é regular quando alguma expressão a denota. 7, o vazio e a cadeia vazia: ∅ denota nenhuma cadeia, ε denota uma, e o fecho do vazio é {ε}; colar com ∅ apaga tudo, colar com ε não muda nada. 8, atalhos viram núcleo: x+ vira x x*, x? vira x|ε, [abc] vira a|b|c, e o coringa fica como folha. 9, o preço em nós: [a-z] tem cinco caracteres e 51 nós; uma faixa de n símbolos custa 2n − 1 nós; [a-z]+ custa 104 e [a-z]? custa 53. 10, o mesmo conjunto: (a|b)* e (a*b*)* têm árvores diferentes e a mesma linguagem; a*b* e (a|b)* não, e ba é a testemunha. 11, o fechamento é uma cerca: unir, colar e repetir continuam dentro; tantos a quanto b fica fora, pelo argumento de k estados e k+1 prefixos. 12, as regex de hoje e o saldo: a retrovisão sai da classe, três extensões só parecem sair; PCRE, de 1997, retrocede, e RE2, de 2010, não; reconhecer é trabalho da máquina, no módulo 03.
Figura 8: O módulo do começo ao fim, em doze quadros: o molde, as três datas, as seis cláusulas, a precedência, a árvore passo a passo, o conjunto que ela denota, o vazio e a cadeia vazia, os atalhos, o preço em nós, a equivalência, a cerca do fechamento e o saldo.

Mapa mental

Os tópicos do módulo, do centro para fora, na ordem do livro.

Mapa mental com o título do módulo no centro e oito ramos. Um conjunto infinito numa linha: a* com dois caracteres e conjunto infinito, Kleene em dezembro de 1951, Thompson em junho de 1968, Cloudflare em 2 de julho de 2019. Do texto à árvore: as seis cláusulas da definição, precedência e associatividade, a árvore passo a passo, o parêntese que desaparece. A linguagem denotada: o cálculo de baixo para cima, o vazio e a cadeia vazia, quando uma linguagem é regular. Atalhos e núcleo: o núcleo se define por uma recusa, as reduções uma a uma, o preço de uma classe de símbolos, o coringa como exceção. Equivalência: comparar árvores reduzidas, o que essa comparação não decide, pares que soam errados. O fechamento é uma cerca: três operações, especificar por partes, a cerca delimita por dentro, o que a cerca deixa passar. As regex de hoje: a retrovisão sai da classe, três extensões que só parecem pular a cerca, dois motores e dois compromissos. O saldo: a expressão denota, a máquina reconhece no módulo 03.
Figura 9: Os tópicos e subtópicos do módulo, em árvore, na ordem do livro, em sentido horário a partir do alto, à direita.

Painel do conhecimento

Conceitos

  • Expressão regular: o molde, feito de folhas (\emptyset, \varepsilon, um símbolo) e três operadores (escolher, colar, repetir).
  • Linguagem denotada, L(r): o conjunto de cadeias que o molde descreve.
  • Linguagem regular: a que alguma expressão denota.
  • Equivalência, r \equiv s: L(r) = L(s).
  • Fechamento: unir, colar e repetir linguagens regulares devolve linguagem regular.

Exemplos

  • a*: dois caracteres, conjunto infinito.
  • a|bc denota \{a, bc\}; (a|b)c denota \{ac, bc\}.
  • (ab)c e abc dão a mesma árvore.
  • L(\emptyset^*) = \{\varepsilon\}.
  • [a-z]: cinco caracteres, 51 nós.

Diagrama

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
    C(("concatenação")) --> A(("alternância"))
    C --> F3(("'c'"))
    A --> F1(("'a'"))
    A --> F2(("'b'"))
    F1 -.->|"denota"| L1["{a}"]
    F2 -.->|"denota"| L2["{b}"]
    F3 -.->|"denota"| L3["{c}"]
    A -.->|"denota"| L4["{a, b}"]
    C -.->|"denota"| L5["{ac, bc}"]

Figura 10: A árvore de (a|b)c, com o conjunto que cada nó denota.

Evidências

  • Dezembro de 1951: Kleene escreve o memorando RM-704 da RAND, sobre redes de neurônios.
  • Junho de 1968: Thompson publica um método que lê o texto uma vez e nunca volta atrás.
  • 2 de julho de 2019: na Cloudflare, o fragmento .*.*=.*, num motor que retrocede, custa um trabalho que cresce com o cubo do comprimento da linha.

Referências

  • Kleene, RM-704, RAND, 1951.
  • Thompson, Regular Expression Search Algorithm, Communications of the ACM, v. 11, n. 6, p. 419–422, 1968.
  • Graham-Cumming, relatório do incidente da Cloudflare, 2019.
  • Cox, Regular Expression Matching Can Be Simple And Fast, 2007.
  • Aho, Handbook of Theoretical Computer Science, 1990.

Aplicações

  • Busca em texto: em 1973, a pedido de McIlroy, o g/re/p sai do editor ed e vira programa próprio.
  • Descrever os trechos de uma categoria num programa: o padrão é uma expressão regular.
  • Dois motores, dois compromissos: PCRE (1997) retrocede; RE2 (Google, 2010) não.
  • Nos módulos 03 a 05, a expressão vira a máquina que reconhece.

Mapa conceitual

DicaAntes de olhar

Escreva num papel: expressão regular, árvore sintática, operadores, folhas, precedência, linguagem denotada, linguagem regular, atalho, núcleo, equivalência, convergência estrutural, fechamento, memória finita, retrovisão, máquina. Ligue os conceitos com setas, e escreva em cada seta um verbo que diga qual é a relação. Depois compare com o mapa.

Mapa conceitual. A expressão regular é lida como árvore sintática e denota a linguagem denotada. A precedência decide a forma da árvore sintática. A árvore termina em folhas, símbolo, ε e ∅, e tem nós internos que são os operadores colar, escolher e repetir; calculada das folhas à raiz, dá a linguagem denotada. O atalho se reduz ao núcleo, que contém só os operadores, e aumenta o tamanho da árvore. A equivalência compara duas linguagens denotadas, e a convergência estrutural detecta parte da equivalência. A linguagem denotada, quando alguma expressão a denota, é linguagem regular. O fechamento mantém unir, colar e repetir dentro da classe da linguagem regular. A memória finita marca onde fica a cerca da classe. A retrovisão exige lembrar um trecho inteiro, o que excede a memória finita, e fica fora da classe. A máquina reconhece cadeias de uma linguagem regular.
Figura 11: Os conceitos do módulo ligados por frases de ligação. Cada seta, lida da origem ao destino, é uma afirmação do módulo.

Folha de consulta

Escrita e precedência

  • repetir, o fecho: a*, prende primeiro
  • colar, a concatenação: ab, prende depois
  • escolher, a alternância: a|b, prende por último
  • iguais em fila agrupam pela esquerda: abc vira concat(concat('a', 'b'), 'c')
  • parênteses mudam a forma da árvore e custam zero nós

O conjunto, caso a caso

  • L(\emptyset) = \emptyset, L(\varepsilon) = \{\varepsilon\}, L(a) = \{a\}
  • L(r \mid s) = L(r) \cup L(s)
  • L(rs) = L(r)\,L(s)
  • L(r^*) = L(r)^*, a começar pela potência zero, \{\varepsilon\}

Atalhos e o que viram

Atalho Vira
x+ concat(x, fecho(x))
x? alt(x, vazio)
[abc] a alternância de a, b, c
[a-c] [abc]
. fica como folha própria
x{3,5} fora da notação

Contas de nós

  • faixa de n símbolos: 2n - 1 nós
  • [0-9]: 19 · [a-z]: 51 · [a-z]?: 53 · [a-z]+: 104
  • três faixas concatenadas: 155; sob +: 312, de 18 caracteres
  • a|bc: 5 nós · (a \mid b)^{*}c: 6 nós

Bordas e identidades

  • colar com \emptyset dá \emptyset; colar com \varepsilon não muda nada
  • L(\emptyset^*) = \{\varepsilon\}
  • (a^*)^* \equiv a^* e (a \mid b)^* \equiv (a^*b^*)^*
  • a^*b^* \not\equiv (a \mid b)^*: ba está só na segunda
  • L(a^*) contém \varepsilon; L(a^+), não

A cerca da classe

  • dentro: unir, colar, repetir; também complemento e interseção, que a notação não oferece como operador
  • dentro: aninhamento até uma profundidade fixa, um conjunto infinito
  • fora: tantos a quanto b; parênteses sem profundidade máxima; a retrovisão

Erros previsíveis

  • “a expressão reconhece a cadeia”: ela denota um conjunto; quem reconhece é a máquina
  • “árvores diferentes, linguagens diferentes”: (a \mid b)^* e (a^*b^*)^* desmentem
  • “o asterisco quer dizer qualquer coisa”: aqui ele junta as potências
  • “o coringa não é redutível”: é, e ficou por tamanho
  • “a retrovisão é um atalho”: ela sai da classe