Matemática Computacional

Expressões Regulares

Introdução

• As expressões regulares definem as linguagens regulares de uma

forma declarativa (algo que um autômato finito não pode fazer). Ou

seja, as expressões regulares são a formalização algébrica de um

autômato finito1. Isso faz com que elas sirvam como linguagem de

entrada para diversos sistemas que processam strings, seja em

ferramentas do mundo UNIX, em um editor de textos ou até mesmo

em um SGBD. Com as expressões regulares podemos especificar

complexos padrões a serem pesquisados em um string.

1 – Sistema de Estados Finitos é a próxima matéria a ser vista.

Origem

• Sua origem está em dois estudos, o primeiro teorizava o

funcionamento dos neurônios, o segundo demonstrava a descrição

algébrica de tais modelos. Só em 1968 um algoritmo de busca do

editor de textos qed para o UNIX veio a utilizar tal recurso e

posteriormente foi criada a ferramenta grep “Global (search for)

Regular Expression and Print” (Jargas, 2009).

Segundo Menezes (2000), uma linguagem é regular se, e se somente se, é possível construir

um autômato finito que reconheça tal linguagem.

Conceitos básicos

• Alfabeto: conjunto finito de caracteres (um conjunto vazio também

pode ser considerado um alfabeto). É representado pelo símbolo Σ .

• Palavra: sequência finita de símbolos do alfabeto de forma adjacente.

A palavra vazia é representada pelo símbolo . Se Σ representa um

alfabeto, então Σ* representa o conjunto de todas as palavras possíveis

sobre o alfabeto. Já Σ+ representa o conjunto de todas as palavras do

alfabeto, exceto a palavra vazia, Σ+ = Σ*- { }.

• Tamanho ou comprimento: o número de símbolos que compõe uma

palavra w é representado por |w|.

• Para cada expressão regular E, descrevemos a linguagem que ela

denota por L(E).

Operações

• União: o operador “+” serve para denotar tal operação.

Exemplo: L(E) = 01* + 10* denota todos os strings que são um

único zero seguido por qualquer número de 1’s ou um único 1

seguido por qualquer número de zeros.

• Concatenação: é o conjunto de strings que podem ser formados

tomando-se qualquer string de uma linguagem L e concatenando-se

esse string com qualquer string de uma linguagem M. Denotamos tal

operação com o operador “.” ou simplesmente não indicamos nenhum

operador.

Exemplo: L = {001, 10, 111} e M = { , 001}, então

LM é {001, 10, 111, 001001, 10001, 111001}

Operações (continuação)

• Fechamento (estrela ou de Kleene): representa todos os conjuntos

de strings que podem ser formados, tomando-se qualquer número de

strings de L, possivelmente com repetições. Denota-se por L*

Precedência de operadores

• O operador de fechamento tem a precedência mais alta, se aplicando

à menor sequência de símbolos à sua esquerda. Por isso recomenda-

se o uso de parênteses para reduzir a margem de erro.

• Em seguida na precedência temos o operador de concatenação e por

fim as uniões.

Exemplo precedência de operadores

A expressão regular 01* não é o mesmo que (01)*, pois a primeira

expressão denota todos os strings iniciados por 0 e com um, vários ou

nenhum caractere 1. Já a segunda expressão representa todos os

strings com um caractere 0 seguido de um caractere 1, uma, várias ou

nenhuma vez.

L(E) = 01* , temos {0, 01, 011, 0111, ...}

L(E) = (01)* , temos { , 01, 0101, 010101, ...}

Exemplos

• Expressão que representa todos os strings formados sobre o alfabeto

{a,b}, que contenham o substring bb.

L(E) = (a+b)*bb(a+b)*

• Expressão que representa a linguagem das palavras que tenha aa

como prefixo e bb como sufixo, sobre o alfabeto {a,b}.

L(E) = aa(a+b)*bb

• Expressão que representa todas as palavras que terminam com 00 ou

11, sobre o alfabeto {0,1}.

L(E) = (0+1)*(00+11)

Exercícios

1. Utilizando as expressões regulares do slide anterior, apresente 5 strings

representados a partir de cada expressão.

2. Crie a expressão regular para cada notação formal das linguagens :

a) L = {w ∈ {a, b} | w inicia por b, seguido de zero ou mais a’s}

b) L = {w ∈ {a, b} | w termina por aa ou bb}

c) L = {w ∈ {a, b} | cada a em w é imediatamente precedido por um

b}

d) L = {w ∈ {a, b} | w tem abab como um substring}

e) L = {w ∈ {a, b} | w não possui dois a’s consecutivos}

f) L = {w ∈ {a, b} | w tenha exatamente dois b’s}

g) L = {w ∈ {0, 1} | w termine com 1 e |w| >=4}

h) L = {w ∈ {0, 1} | w tenha o número de 1’s múltiplo de três}

Correção dos exercícios

• L = {w ∈ {a, b} | w inicia por b, seguido de zero ou mais a’s}L(E) = ba*

• L = {w ∈ {a, b} | w termina por aa ou bb}L(E) = (a+b)*(aa+bb)

• L = {w ∈ {a, b} | cada a em w é imediatamente precedido por um b}L(E) = (b+ba)*

• L = {w ∈ {a, b} | w tem abab como uma substring}L(E) = (a+b)*(abab)(a+b)*

• L = {w ∈ {a, b} | w não possui dois a’s consecutivos}L(E) = (a+ )(b+ba)*

• L = {w ∈ {a, b} | w tenha exatamente dois b}L(E) = a*ba*ba*

• L = {w ∈ {0, 1} | w termine com 1 e |w| >=4}L(E) = (0+1)(0+1)(0+1)+ 1

• L = {w ∈ {0, 1} | w tenha o número de 1’s múltiplo de três}L(E) = (0*10*10*10*)+

Metacaracteres padrão UNIX

• As expressões regulares são formadas por símbolos com funções

especiais (metacaracteres) e caracteres literais.

• Na prática existem algumas diferenças entre a notação matemática e

a notação derivada dos sistemas UNIX. O caractere “+” era utilizado

para indicar a operação lógica “ou”, já como metacaractere padrão

UNIX é um símbolo quantificador, já o ponto “.” agora é utilizado como

uma espécie de caractere curinga que pode substituir qualquer

caractere.

Alguns metacaracteres UNIX

Metacaractere Nome Função Tipo

. ponto subst. um caractere qualquer representantes

[] lista lista de caracteres permitidos representantes

[^] lista negada lista de caracteres proibidos representantes

? opcional zero ou um caractere quantificadores

* asterisco zero, um ou mais caracteres quantificadores

+ mais um ou mais caracteres quantificadores

{} chaves de n até m, exemplo: {n,m} quantificadores

\ escape torna literal um caractere outros

| ou ou um ou outro outros

() grupo delimita um grupo outros

- traço intervalo  

Exemplos com metacaracteres

• As chaves simulam

os metacaracteres

“*+?”, com elas é

possível especificar

um número exato

ou até mesmo uma

faixa numérica.

Expressão Casa com

n.o não,não, nzo, n3o, ...

11.30 11:30, 11 30, 11.30, 11y30, ...

<.> <x>, <k>, <m>,<4>, ...

n[aã]o nao, não

[Tt]eclado Teclado, teclado

11[:.]30 11:30, 11.30

<[aeiou]> <a>, <e>, <i>, <o> , <u>

fala[rs]? fala, falar, falas

5*2 2, 52, 552, 5552, ...

b[ip]* b, bi, bip, biip, bipp, bpipip,...

5+2 52, 552, 5552, 55552, ...

Exemplos com metacaracteres(continuação)

Expressão Casa com

5+2 52, 552, 5552, 55552, ...

b[ip]+ bi, bp, bip, biip, ...

[0-9] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[0123456789] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

[a-z]

a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,

z

[A-Z] A,B,C,D,E,F,G,H,I,J,K,L,M,...,Z

[0-9A-Fa-f] Números hexadecimais !!

n[^pb] n2, nu, nx, na, nz, ...

[0-5]\. 0.,1.,2.,3.,4.,5.

• Conforme

Jargas(2009),

nunca tente

resolver uma

expressão regular

de uma só vez. É

preciso generalizar

e depois fazer os

refinamentos.

Exercícios

3) Reescreva o exercício n° 2 (o que for possível) utilizando os metacaracteres

padrão UNIX.

4) Continue a aprimorar as seguintes expressões regulares abaixo:

a) Data no formato dd/mm/aaaa

ER: primeira versão: ../../....

aprimorando: [0-9]{2} / [0-9]{2} / [0-9]{4}Resposta: ((0[1-9])|(1[0-9])|(2[0-9])|(3[0-1]))/((0[1-9])|(1[0-2]))/[0-9]{4}

b) Hora no formato hh:mm

ER: primeira versão: ..:..

aprimorando: [0-9]{2}:[0-9]

c) Telefone

ER: primeira versão: ....-....

Exercícios

5) Crie as expressões regulares (utilizando os metacaracteres padrão

UNIX) para os seguintes itens:

a) CPF

b) e-mail

c) URL (endereços web com os domínios .com, .net, .edu, .gov, .nom,

todos eles do Brasil)

d) Nome de arquivo padrão MSDOS (começando por uma letra, com

8 caracteres e uma extensão de 3 caracteres)

Dicas

• O GoogleDoc’s já possui o suporte à expressões regulares em localizar/substituir.

• No site www.regexpal.com é possível verificar online suas expressões.

• Referências sobre esse assunto:

Jargas, Aurélio Marinho, Expressões Regulares – Uma Abordagem Divertida. Rio de Janeiro:

Novatec, 2009.

Menezes, Paulo Fernando Blauth, Linguagens Formais e Autômatos. Porto Alegre: Sagra

Luzzatto, 2000.