✖

Expressões regulares

A expressão regular é uma cadeia de texto que permite descrever um conjunto de palavras. As expressões regulares também podem ser entendidas como uma maneira simples de descrever um autômato finito.

O que é uma expressão regular

Na aritmética usamos símbolos como · e + para montar uma expressão como, por exemplo, (2 + 3) · 4. Ao avaliar essa expressão, obtemos um número. A expressão regular é uma sequência de caracteres e de alguns símbolos especiais, por exemplo a(x ∪ y), cuja avaliação é uma linguagem (formal). O resultado da expressão (2 + 3) · 4 é o número 20, e o resultado da expressão regular a(x ∪ y) é o conjunto de duas palavras “ax”, “ay”.

Como avaliaríamos a expressão regular anterior, a(x ∪ y)? Cada letra é, na verdade, uma abreviação de um conjunto unitário que contém a letra em questão, e a multiplicação oculta é a concatenação de palavras. A expressão regular poderia ser reescrita “por extenso” assim:

{a}∘({x}∪{y})

Depois a avaliaríamos assim: a união {x} ∪ {y} nos dá a linguagem {x,y}. Concatenando as linguagens {a} e {x,y}, obtemos a linguagem {ax, ay}.

As expressões regulares são usadas com muita frequência na programação, e a maioria das linguagens de programação tem expressões regulares implementadas de alguma forma. Elas são usadas, por exemplo, para verificar se um texto digitado pelo usuário atende a certos critérios (por exemplo, se é um e-mail válido, uma data válida etc.) e também para substituir textos (por exemplo, podemos querer substituir todas as ocorrências de URL em um texto por links clicáveis etc.).

As implementações reais de expressões regulares costumam ser mais poderosas do que as expressões regulares descritas aqui e usam uma sintaxe um pouco diferente, mas sobretudo mais complicada.

Definição de expressão regular

Vamos definir a expressão regular sobre algum alfabeto Σ. Dizemos, então, que uma expressão regular é:

  1. a, em que a ∈ Σ. Ou seja, um caractere isolado do alfabeto é uma expressão regular.
  2. ϵ: a palavra vazia, que na programação também se escreve como aspas vazias “”.
  3. ∅: a expressão regular deve ser capaz de descrever também a linguagem vazia, então a linguagem vazia é uma expressão regular.
  4. (R1 ∪ R2), em que R1, R2 são expressões regulares.
  5. (R1 ∘ R2), em que R1, R2 são expressões regulares.
  6. (R∗), em que R é uma expressão regular.

Em vez do símbolo ∪ do item 4, podemos também usar o símbolo da barra vertical: |. Em vez do símbolo ∘, não precisamos usar nada. Da mesma forma que normalmente não escrevemos diretamente o símbolo de multiplicação, o ponto central ·, normalmente também não escrevemos o símbolo de concatenação ∘. Estas expressões regulares são, assim, idênticas: a ∘ (b ∪ c) e a(b|c).

O que significam os operadores individuais?

  • ∪ ou | representa a união de linguagens.
  • ∘ representa a concatenação de linguagens.
  • ∗ representa o fecho de uma linguagem.

Exemplos:

  • a representa a linguagem simples {a}.
  • a|b representa a linguagem formada por duas palavras, {a, b}.
  • a ∘ b representa a linguagem {ab}.
  • a(b|c)d representa a linguagem {abd, acd}.
  • a(b∗) representa a linguagem de todas as palavras que começam com a letra “a”, seguida de qualquer quantidade de letras “b”.
  • (ab)∗ representa a linguagem de todas as palavras {ϵ, ab, abab, ababab, …}.
  • 0∗10∗ representa a linguagem de todas as palavras binárias que contêm exatamente um 1. (Observe que seria mais preciso escrever essa expressão assim: (0∗)1(0∗), mas, quando a notação é legível mesmo sem isso, podemos omitir os parênteses.)
  • Σ∗1Σ∗ representa a linguagem de todas as palavras que contêm pelo menos um 1.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ representa a linguagem de todos os números naturais positivos.

Em seguida vamos mostrar a equivalência entre expressões regulares e autômatos finitos. Veremos que, para cada expressão regular cuja avaliação é a linguagem R, existe um autômato finito A para o qual vale L(A) = R, e vice-versa.

Fontes

Capítulos: Expressões regulares, Conversão de expressão regular em autômato, Autômato finito não determinístico generalizado, Conversão de autômato em expressão regular