1 Expressões regulares e linguagens regulares — Guia

O molde a*, uma expressão regular de dois caracteres, descreve um conjunto de cadeias, fileiras de símbolos: a cadeia vazia, sem símbolos, a, aa, aaa, e a lista não acaba. Dez caracteres, abcdefghij, descrevem um conjunto de uma cadeia só. O tamanho do texto não informa o do conjunto. As expressões a*b* e (a|b)* usam as mesmas duas letras, mas a cadeia ba pertence só à segunda. Quem escreve a|bc querendo (a|b)c recebe uma expressão válida para outro conjunto, sem que nada acuse a troca.

A expressão descreve, ou denota, um conjunto de cadeias, uma linguagem. Responder sim ou não sobre uma cadeia é trabalho de uma máquina; dela trata o módulo dos autômatos finitos determinísticos. Aqui há dois trabalhos. Num, você diz que linguagem uma expressão denota. No outro, chega de uma regra em português à expressão exata. Os dois passam por uma árvore que o texto não mostra: um organograma de caixinhas, os nós, com a raiz no topo e as folhas embaixo.

1.1 Do texto à árvore, da árvore ao conjunto

Uma expressão se fabrica por indução. As folhas são de três tipos: o conjunto vazio \emptyset, a cadeia vazia \varepsilon e um símbolo do alfabeto. Os operadores são três: escolher, a alternância |; colar, a concatenação, sem sinal; e repetir zero ou mais vezes, o fecho *. Sem parênteses, o agrupamento sai da precedência: aplica-se o fecho, depois a concatenação, e a alternância por último. Operadores iguais em fila se agrupam pela esquerda, e abc vira concat(concat('a', 'b'), 'c'), cada nó antes dos filhos. Cada nó recebe um conjunto, das folhas para a raiz.

NotaDefiniçã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)^*.

O fecho reúne as potências da linguagem: colar zero, uma, duas cadeias dela, sem parar. A potência zero é \{\varepsilon\} para qualquer linguagem, inclusive a vazia.

NotaDefiniçã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.

A equivalência se recusa com uma testemunha, uma cadeia que está num conjunto e falta no outro. Para afirmá-la, cada cadeia de cada lado precisa se construir no outro.

NotaDefinição — Linguagem regular

Uma linguagem L \subseteq \Sigma^* é regular quando existe uma expressão regular r sobre \Sigma tal que L(r) = L.

As linguagens regulares formam uma classe, um conjunto de linguagens, que é fechada: unir, colar ou repetir linguagens regulares devolve linguagem regular. Se r_1 e r_2 denotam as partes, (r_1 \mid r_2), (r_1 r_2) e (r_1^*) são expressões, e denotam a união, a concatenação e o fecho. O fechamento é uma cerca, e ela delimita por dentro: compor nunca a atravessa.

Onde a cerca passa, quem diz é a memória. Uma máquina pode ler a cadeia numa passada, guardando o conjunto de lugares da expressão em que a leitura pode estar. Com a expressão fixa, esses conjuntos são k, um número fixo, e cada um vale como um estado, uma situação da máquina. Suponha uma expressão para as cadeias com tantos a quanto b, e k = 3. As entradas a, aa, aaa e aaaa não cabem em estados distintos. Se aaaa parar onde parou a, acrescente um b às duas. Então ab pertence e aaaab não, mas a máquina, no mesmo estado e diante do mesmo b, responde igual. Com k qualquer, entre k+1 entradas duas param no mesmo estado, e tantos b quanto os a da mais curta as separam: nenhuma expressão denota essa linguagem. Quem só sabe em que estado está não sabe quantas vezes já entrou nele.

1.2 Quatro caracteres, duas leituras

Pela precedência, a|bc dispensa parênteses, e o outro agrupamento pede (a|b)c. Uma execução da leitura monta duas árvores e conta os nós:

  a|bc
  -> alt('a', concat('b', 'c'))
  -> 5 nos

  (a|b)*c
  -> concat(fecho(alt('a', 'b')), 'c')
  -> 6 nos

Suba a árvore de a|bc pela definição. As folhas denotam \{a\}, \{b\} e \{c\}. A concatenação cola b com c em \{bc\}, e a alternância da raiz une: L(a \mid bc) = \{a, bc\}. Com parênteses, (a|b)c denota \{ac, bc\}.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
    subgraph A["a|bc"]
        direction TB
        A1(("alternância"))
        A2(("'a'"))
        A3(("concatenação"))
        A4(("'b'"))
        A5(("'c'"))
        A1 --> A2
        A1 --> A3
        A3 --> A4
        A3 --> A5
    end
    subgraph B["(a|b)c"]
        direction TB
        B1(("concatenação"))
        B2(("alternância"))
        B3(("'c'"))
        B4(("'a'"))
        B5(("'b'"))
        B1 --> B2
        B1 --> B3
        B2 --> B4
        B2 --> B5
    end
Figura 1: Os dois agrupamentos de quatro caracteres: a|bc, que a precedência escolhe, e (a|b)c, que pede parênteses.

Em (a \mid b)^{*}c são sete caracteres e seis nós. Os parênteses orientaram a leitura sem deixar nó, e a concatenação da raiz é o operador que ninguém digitou. O fecho reúne as potências de \{a, b\}: \{\varepsilon\}, depois duas cadeias, depois quatro. Colado com c, dá todas as cadeias de a e b seguidas de um c. A menor é c sozinho, e vem da potência zero.

1.3 Onde o conjunto contraria o palpite

O asterisco desta notação reúne potências. a* denota só cadeias de a, a vazia inclusive. O “qualquer coisa” que ele significa num campo de busca de arquivos fica fora.

L(\emptyset) tem zero elementos, e L(\varepsilon) tem um, a cadeia sem símbolos. Na concatenação, o \varepsilon é neutro, já que L(\varepsilon)L(r) = L(r). Já o \emptyset aniquila, L(\emptyset)L(r) = \emptyset, porque falta cadeia para colar com as de L(r). Ponha \emptyset onde cabia \varepsilon e o conjunto vazio sobe pela árvore enquanto o nó acima for outra concatenação, sem aviso. E L(\emptyset^*) = \{\varepsilon\}: a potência zero entra mesmo quando não há nada a repetir.

Árvores distintas podem denotar o mesmo conjunto. (a \mid b)^* e (a^*b^*)^* denotam todas as cadeias de a e b. Na segunda, ba sai em duas repetições do fecho externo. Mas a^*b^* e (a \mid b)^* diferem. A testemunha é ba.

1.4 Antes de abrir a resposta

Simule primeiro. Que árvore sai de a|b*c, e quais cadeias de até dois símbolos ela denota?

alt('a', concat(fecho('b'), 'c')), com seis nós: o fecho se aplica só ao b, e a alternância fica na raiz. As cadeias são a, c e bc. O c sozinho vem da potência zero de \{b\}. Já ac fica de fora: ela pertenceria aos agrupamentos (a|b*)c e (a \mid b)^{*}c, que exigem parênteses.

Agora escreva. Que expressão denota as cadeias de a e b em que todo a vem imediatamente seguido de um b?

(b|ab)*. Toda cadeia que cumpre a regra se corta em blocos b e ab, e toda concatenação desses blocos a cumpre. A cadeia vazia entra pelo fecho e pertence, porque sem a nenhum não há o que exigir. (ab)* deixaria b de fora. Outra escrita serve se denotar o mesmo conjunto, como (b*ab)*b*.

Por fim, compare. As expressões (ab)*a e a(ba)* são equivalentes?

São, mas as árvores diferem: o fecho é o filho esquerdo numa e o direito na outra. Cada cadeia da primeira, (ab)^n a, é a mesma cadeia a(ba)^n da segunda, e vice-versa: a, aba, ababa, sem fim.

1.5 Para ir além

No material, “Uma passada contra um cubo” conta a origem da notação e por que uma expressão demora num programa e não noutro. “O encaixe que o texto não mostra” trata dos textos malformados. “Cinco caracteres, 51 nós” traduz classe de símbolos, faixa, + e ? para os três operadores. “a+ e aa* são a mesma expressão?” mostra o que a comparação de árvores decide. Em “O fechamento é uma cerca”, o aninhamento de profundidade fixa cabe na classe, e “A extensão que atravessa a cerca” trata da retrovisão.