Aula 05 – Teoria da Computação – Site do Professor Carlos Fernandes

Expressões regulares

Uma Expressão Regular (ER) é uma forma compacta de descrever linguagens regulares. Trata-se de uma definição que faz uso do fato de que a concatenação, união e o fecho de Kleene de linguagens regulares são regulares. Teremos então estas operações representadas pela justaposição (no caso da concatenação), o “+” (no caso da união) e o “*” (no caso do fecho de Kleene). Além disso, devemos também considerar as linguagens regulares mais simples. São elas: a linguagem vazia, a linguagem com a cadeia vazia e as linguagens com somente um símbolo.

Uma expressão regular sobre o alfabeto Σ={σ₁, …, σ_n} é de uma das seguintes formas:

∅; ε; σ_i, onde σ_i∈Σ.
Se e é uma expressão regular, então e* também é uma expressão regular. Se e₁ e e₂ são expressões regulares, então e₁e₂ e e₁+e₂ são expressões regulares. Se e é uma expressão regular, então (e) (um agrupamento de e) é uma expressão regular.
Nada mais é uma expressão regular.

Os exemplos que seguem mostram para algumas expressões regulares as respectivas linguagens descritas:

a representa a linguagem {a}, ou seja, a linguagem que só tem o símbolo a.
∅ representa a linguagem vazia, sem cadeias.
a+b+c representa a linguagem {a, b, c}.
ε representa a linguagem {ε}.
a^* representa a linguagem {a}^*, ou seja, todas as cadeias formadas somente com o símbolo a.
(a+b)^* representa as cadeias no conjunto {a, b}^*, ou seja, todas as cadeias formadas de a’s e b’s.
a^*+b^* representa a linguagem das cadeias formadas só com a’s ou só com b’s.

Podemos verificar que algumas expressões regulares podem ser equivalentes a outras, no sentido de especificarem a mesma linguagem formal. Por exemplo, (a^*+b^*)^* e (a+b)^* especificam a mesma linguagem {a, b}^*.

Existe uma forma recursiva de definir a linguagem que uma expressão regular descreve. Se e é uma expressão regular vamos usar [e] para denotar a linguagem que e descreve.

Seja e uma expressão regular, define-se [e] por casos, de acordo com as equações a seguir:

[σ_i]={σ_i}, com σ_i∈Σ
[∅]=∅
[ε] = {ε}.
[e₁+e₂]=[e₁]∪[e₂].
[e₁e₂]=[e₁][e₂].
[e^*]=[e]^*.

A definição desenvolvida acima permite que você atribua um conjunto de cadeias, e somente um, a qualquer expressão regular. Dizemos que [e] é a linguagem formal descrita, especificada, pela expressão regular e.

Algumas questões que surgem naturalmente se toda linguagem regular é especificável por alguma expressão regular e vice-versa.

Na própria definição de [ ] responde, juntamente às propriedades de fechamento de linguagens regulares, à segunda questão. Vejamos: os três primeiros itens da definição, ou seja, o significado pretendido das expressões σ_i, ∅ e ε são linguagens regulares. Os outros itens utilizam operações sobre linguagens regulares que resultam em uma linguagem regular. Relembre que a concatenação de linguagens regulares, o fecho de Kleene de uma linguagem regular e a união de linguagens regulares são linguagens regulares. Portanto, toda expressão regular define uma linguagem regular. Este é um fato importante.

Se e é uma expressão regular, então a linguagem [e] é regular.

Neste ponto talvez tenha ficado claro que é muito simples escrever uma ER, entretanto, é difícil, até mesmo para um computador, verificar se duas ERs descrevem a mesma linguagem.

O fato de as expressões regulares representarem linguagens regulares é importante, mas ele se torna mais útil se soubermos construir um reconhecedor (um AFD) a partir da expressão. Lembre-se das gramáticas, pois servem de guia para a construção de AFDs que reconhecem a linguagem gerada por elas. É bom descrever linguagens regulares de forma compacta, mas é melhor ainda se desta descrição pudermos sistematicamente construir um programa que verifique se as cadeias pertencem ou não à linguagem descrita pela expressão regular. De fato, a definição de [ ] anterior pode ser modificada para em vez de associar um conjunto à cada expressão regular, ela associa um autômato que reconhece a linguagem descrita pela expressão. Faremos isso através do uso de autômatos com transição ε.

Um autômato finito com transição ε, AFε, é um AFND onde a função de transição inclui a leitura da cadeia vazia. Na realidade, é uma forma de realizar a transição de estados sem que sejam lidos
símbolos da entrada. A função de transição δ de um AFε é tal que, δ:Q×(Σ∪{ε})→℘(Q). O efeito de uma transição ε é não determinístico. A transição δ(q₁, ε)={q₂} indica que na leitura de ε, estando o autômato no estado q₁, este muda para o estado q₂.

Desde que ε qualquer outra cadeia, também pode-se considerar que o autômato permanece no estado q₁. A extensão da função δ para cadeias de símbolos, $\boldsymbol{\hat{\delta}}$ , é então definida como:

• $\boldsymbol{\hat{\delta}}$ (q , ε)=δ(q, ε)
• $\boldsymbol{\hat{\delta}}$ (q, σ)=δ(q, σ)∪δ(q, ε)
• $\boldsymbol{\hat{\delta}}$ (q , σω) =∪_{q∈δ(q, σ)∪δ(q, ε)} $\boldsymbol{\hat{\delta}}$ (q, ω)

Define-se a linguagem aceita por um AFε como $\boldsymbol{\cal{A}}$ ={ω∈Σ^*/ $\boldsymbol{\hat{\delta}}$ (q ,ω)∩F}, onde F é o conjunto de estados finais de $\boldsymbol{\cal{A}}$ .

Um ponto importante é observar que todo AFε aceita uma linguagem regular. Isto pode ser argumentado ao verificarmos que as transições não são essenciais. Considere um AFε $\boldsymbol{\cal{A}}$ = 〈Q, Σ, q₀, F, δ〉 com δ(q, ε)=S. Podemos provar que a linguagem aceita por este AFε é regular, eliminando a transição . A transição significa que o autômato uma vez no estado q pode transitar a qualquer um dos estados s∈S. Pode-se eliminar esta transição ε considerando para cada símbolo σ∈Σ o conjunto {q′∈Q/q∈δ (q′, σ)} dos estados q′ que transitam para q via leitura de σ. Se definimos uma nova função de transição δ_nova, tal que, δ_nova(q’, σ)=δ(q’, σ)∪δ(q, ε). O autômato β=〈Q, Σ, q₀, F, δ_nova〉 é um autômato não determinístico sem transições ε que aceita a mesma linguagem que $\boldsymbol{\cal{A}}$ .

Todo autômato finito com transições $\boldsymbol{\epsilon}$ reconhece uma linguagem regular.

Pode-se agora formalizar a associação de uma expressão regular ao autômato finito que reconhece a linguagem descrita por ela. Seja e uma expressão regular, define-se o autômato $\boldsymbol{\cal{A}}$ e, [e], por casos, de acordo com as equações a seguir:

Se e=σ_i então $\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _σi, exibido na figura abaixo, com σ_i∈Σ;

$\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _σi

Se e=∅ então $\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _∅, exibido na figura abaixo;

$\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _∅

Se e=ε então $\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _ε, exibido na figura abaixo;

$\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _ε

Se e=e₁+e₂ então e=e₁∪e₂ então $\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _e1∪ $\boldsymbol{\cal{A}}$ _e2, exibido na figura abaixo, onde é criado um novo estado inicial, que tem uma transição ε indo para cada um dos estados iniciais de $\boldsymbol{\cal{A}}$ _e1 e $\boldsymbol{\cal{A}}$ _e2.

$\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _e1∪ $\boldsymbol{\cal{A}}$ _e2

Se e=e₁e₂ então $\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _e1 $\boldsymbol{\cal{A}}$ _e2, exibido na figura abaixo, onde cada estado final de $\boldsymbol{\cal{A}}$ _e1 tem uma transição indo para o estado inicial de $\boldsymbol{\cal{A}}$ _e2;

$\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ _e1 $\boldsymbol{\cal{A}}$ _e2

Se e=e^*₁ então $\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ ^*_e1, exibido na figura abaixo, onde é criado um novo estado inicial (e final) q₀, com uma transição indo para o estado inicial de $\boldsymbol{\cal{A}}$ _e1 e são incluídas transições $\boldsymbol{\cal{A}}$ _e1 dos estados finais de para o inicial de $\boldsymbol{\cal{A}}$ _e1.

$\boldsymbol{\cal{A}}$ _e= $\boldsymbol{\cal{A}}$ ^*_e1

Para qualquer expressão regular e, o autômato AFε $\boldsymbol{\cal{A}}$ _ee reconhece [e]. Eliminando-se transições ε, como explicado acima, obtém-se um AFND que reconhece [e].

Concluímos, então, que existem três formas de se formalizar uma linguagem regular. Via gramáticas regulares, via autômatos finitos (determinísticos ou não) e via expressões regulares. Além disso, para cada formalismo mostramos como efetivamente obter outra especificação formal em qualquer um dos outros dois formalismos. Ou seja, dada uma gramática regular, mostramos como construir uma expressão regular e um autômato, que respectivamente descrevem e reconhecem a linguagem gerada por esta. O mesmo se dá a partir de qualquer expressão regular. Vimos como, a partir de uma expressão regular, obter um AFND equivalente. O processo inverso também é possível. Já sabemos que de um AFND podemos obter uma gramática regular equivalente. A seguir vamos mostrar como, a partir desta gramática, obter uma expressão regular equivalente.

Vamos começar analisando a seguinte gramática regular G₁S→aS|b.

Vamos representar como [S] o conjunto de todas as sentenças geradas pelo símbolo S, ou seja [S]={w∈{0, 1}^*S⇒^*w}. Neste caso, como S é o símbolo inicial da gramática [S]=L(G₁), ou seja, os conjuntos são iguais. Como consequência das regras da gramática G₁, podemos escrever a seguinte igualdade de conjuntos: [S]=a[S]∪b. Ou usando o símbolo de expressões regulares para a união: [S]=a[S]+b. A solução desta equação é simplesmente: [S]=a*b.

A solução anterior é uma ilustração do Lema de Arden. Se conhecemos as linguagens L₁ e L₂ e definimos a linguagem L pela igualdade L=L₁L+L₂, então a menor linguagem que atende à igualdade é L=L*₁L₂, e esta solução é única quando ε∉L₁.

No caso de gramática com mais de uma variável (mais de um símbolo não terminal), podemos encontrar a expressão regular de forma parecida com a resolução de um sistema linear. Por exemplo,
considere a gramática G₂:

[S]→bS|aA ,
[A]→bA|aS|ε.

Podemos reescrever a gramática como a seguinte igualdade entre conjuntos:

[S]=b[S]+a[A],
[A]=b[A]+a[S]+ε.

A segunda igualdade é o mesmo que [A]=(a[S]+ε)+b[A].

Portanto, pelo Lema de Arden, pode ser reescrita sem recorrência como [A]=b^*(a[S]+ε).

Esta forma para [A] pode ser substituída na primeira equação [S]=b[S]+ab^*(a[S]+ε).

Isso pode ser rearranjado como [S]=(b+ab^*a)[S]+ab^*. Aplicando mais uma vez o Lema de Arden, chegamos à solução final [S]=(b+ab^*a)^*ab^*. Logo, a ER equivalente à gramática G₂ é (b+ab^*a)^*ab^*.

Vamos exemplificar o método com uma gramática mais difícil, com três símbolos não terminais. Considere a seguinte gramática:

S→0A|1S; A→0B|1S; B→0S|1A|ε

Para obtermos a solução primeiro obtemos as igualdades:

[S]=0[A]+1[S]
[A]=0[B]+1[S]
[B]=0[S]+1[A]+ε

Depois substituímos a 3a equação na segunda:

[A]=0(0[S]+1[A]+ε)+1[S]

Colocamos os termos em [A] separados:

[A]=01[A]+00[S]+0+1[S]

Aplicamos o Lema de Arden: [A]=(01)^*(00[S]+0+1[S])

Substituímos [A] na primeira equação:

[S]=0((01)^*(00[S]+0+1[S]))+1[S]
[S]=0(01)^*(00[S]+0+1[S])+1[S]
[S]=0(01)^*00[S]+0(01)^*0+0(01)^*1[S]+1[S]
[S]=(0(01)^*00+0(0 )^*1+1)[S]+0(01)^*0
[S]=(0(01)^*00+0(01)^*1+1)^*0(01)^*0

Logo a expressão regular equivalente é:

[S]=(0(01)^*00+0(01)^*1+1)^*0(01)^*0

Aplicabilidade

Expressões regulares POSIX

No sistema operacional Unix (e similares) diversos comandos utilizam expressões regulares, como : grep, sed e awk. Sua especificação foi normatizada em uma parte do padrão POSIX, mantido pela IEEE. Muitas linguagens de programação também passaram a aceitar linguagens regulares, por exemplo, Java, JavaScript, Perl, C#, R, Lua, entre outras, seguindo diferentes variantes de notação. É importante ressaltar que tanto as expressões regulares no sistema Linux, como as disponíveis nas linguagens supracitadas, apesar de manterem o nome histórico de ‘expressões regulares’, podem atualmente reconhecer linguagens não regulares, isto é, linguagens que não podem ser especificadas por uma gramática regular. O estudante interessado pode encontrar uma introdução a expressões regulares padrão POSIX em Hopcroft; Motwani; Ullman (2002) e um tratamento detalhado em Goyvaerts; Levitahn (2011).

Mais um uso é a implementação interna dum sistema de realce de sintaxe, como encontrado em ambientes de desenvolvimento integrado. Expressões regulares podem ser usadas para encontrar palavras reservadas, literais e outros tokens específicos, e para alterar a formatação do texto de acordo com o casamento feito.

Um uso difundido de expressões regulares é a filtragem de informação em bancos de dados de texto. Por exemplo, num arquivo de texto contendo cadastros de pessoas e suas datas de aniversário como a seguir:

1954-10-01 João Alberto
1976-07-25 Maria Eduarda
1966-10-22 Carlos Silva

Pode-se filtrar pessoas que nasceram num determinado ano, mês ou dia. Por exemplo, o uso do padrão ^[0-9]{4}-10-[0-9]{2} (.*)$ identifica o nome das pessoas que nasceram em outubro (mês 10). Para o cadastro acima seriam retornados dois grupos de captura, \1 contendo “João Alberto” e \2 contendo “Carlos Silva”. Explorando o exemplo anterior e o uso de validação de formatos digitais, é possível usar expressões regulares para validar as datas presentes no arquivo de texto de aniversários acima. O padrão (19|20)\d\d([- /.])(0[1-9]|1[012])\2([012][0-9]|3[01]) é usado para validar uma data entre 1900-01-01 e 2099-12-31.[10] Atentar que a separação entre ano, mês e dia pode se dar através de hífen, espaço em branco, barra ou ponto. Mas deve-se usar o mesmo símbolo de separação entre ano e mês e entre mês e dia, o que é possível através da nova chamada do grupo de captura anterior (o trecho \2 do padrão). Atentar também que o padrão é incompleto na medida em que não diferencia a quantidade de dias em cada mês, o que resulta no casamento de até “2000-02-31” (31 de fevereiro), incorreta de acordo com o calendário gregoriano.

Material da Google sobre Expressões Regulares

Link

Abaixo pequeno “paper” sobre expressões regulares para baixar o paper clique aqui.

Desmistificando ExpressSes Regulares

Observação

Expressões regulares tem uma importância grande para programadores. Aqueles que desejam ser bons programadores, sugerimos pesquisar na internet o assunto Expressões Regulares com foco na linguagem que se deseja utilizar, embora a teoria de expressões regulares seja independente de onde for implementado o recurso, na prática, algumas extruturas são alteradas/implementadas.

Exercícios

1.O número IP tem o formato nnn.nnn.nnn.nnn, por exemplo: 192.168.255.145. Crie uma expressão regular (ER) que localiza um número IP.

Expressão: [0-9][0-9][0-9]\.[0-9][0-9][0-9]\.[0-9][0-9][0-9]\.[0-9][0-9][0-9] ou reduzindo [0-9]{3}\.[0-9]{3}\.[0-9]{3}\.[0-9]{3}

Explicação: Na primeira expressão fica claro que estamos procurando ternos de números compostos de digito que vão de 0 a 9 e o ponto é um caracter de controle das expressões regulares, mas também um componente de um número IP, então colocamos \. para que o interpretador da expressão regular não tente interpretar o .. Na segunda expressão temos os digitos de 0 a 9 agupados em ternos (o termo {3} indica que o antecessor é repetido três vezes)

Extra: Tem um problema com a lógica destas expressões regulares. Qual?

2. Crie a expressão regular para achar a palavra “letra” em qualquer combinação de maiúsculas/minúsculas.

Expressão: [Ll][Ee][Tt][Rr][Aa]

Explicação: A expressão regular acima, acha qualquer combinação possível de escrita envolvendo a palavra LETRA e as variações possíveis de maiúsculas e minusculas.

3. Crie a expressão regular para achar a palavra “revista” no singular e no plural.

Expressão: revistas*

Explicação: Como o quantificador * casa a ocorrência anterior (letra s) zero ou mais vezes, esta ER casa:

- revista: revista seguido da letra “s” 0 (zero) vezes
- revistas: revista seguido da letra “s” 1 vez

Leitores mais atentos notarão que esta ER também localiza revistass, revistasss, etc.

4. Crie a expressão regular para achar as sequências zzz, zzzz, zzzzz.

Expressão: z{3,5}

Explicação: A letra z de três até cinco vezes, o que localizaria zzz, zzzz e zzzzz. Além disso, podemos ter uma definição mais relaxada como {,5} e {3,}, que seriam “até 5” e “no mínimo 3”, respectivamente.

5. Crie a expressão regular para achar números inteiros.

Expressão: [0-9]+

Explicação: Neste caso, o 0-9 é um intervalo, ou seja, é o mesmo que 0123456789. O quantificador + diz que este número de 0 a 9 pode aparecer uma ou mais vezes, então assim casamos 7, 13, 178, 3636374, etc..

Finalizando

Crie e teste suas expressões regulares aqui.