Expressões Regulares

Prévia do material em texto

EXPRESSÕES REGULARES 
Marcelo Guerra 
INTRODUÇÃO 
 É uma notação para definição de linguagens. 
 
 Podem ser consideradas uma “linguagem de 
programação”. 
 Usadas em buscas em textos (ou bases de dados). 
 Análise léxica em compiladores. 
 
 Estão relacionadas aos AFN’s e são uma alternativa 
mais amigável como notação. 
INTRODUÇÃO 
 Descrição algébrica de linguagem. 
 
 Têm a capacidade de descrever a mesma classe de 
linguagens que os autômatos finitos – linguagens 
regulares. 
 
 Oferecem um modo declarativo para expressar os 
strings que devem ser aceitos. 
 
 São usadas como linguagem de entrada para sistemas 
que processam strings. 
 
Comandos de pesquisa para localizar strings 
Analisadores léxicos 
OPERADORES DE EXPRESSÕES REGULARES 
 Expressões regulares denotam linguagens 
 Exemplo: A exp. reg. 01* + 10* denota o conjunto de 
strings contendo um único 0 seguido de um número 
indeterminado de 1’s ou o contrário. 
 
 Operações em Expressões Regulares: 
 A união de L e M – L ∪ M: é o conjunto de todas as 
strings que estão em L OU em M. 
 
 Concatenação de L e M – LM: conjunto de strings que 
pode ser formados tomando-se qualquer string em L 
E concatenando-se com qualquer string em M. 
OPERADORES DE EXPRESSÕES REGULARES 
 Fechamento (ou estrela, ou fechamento de Kleene) – L* 
- conjunto de todos os strings formados a partir de 
qualquer string de L, com repetições possíveis, e 
concatenando-se todos eles. 
 
 Se L = {0,1} então L* = todas as strings de 0’s e 1’s. 
 Se L={0, 11} então L* = todas as strings de 0’s e 1’s onde os 1’s 
aparecem aos pares. 
 Exemplos: 11110 , 011 e e. 
 Note que as cadeias 01011 e 101 não pertencem a L*. 
 
 L* é a união infinita ∪i0 L
i, onde: 
 L0={ ε }, L1=L, Li p/ i>1 é LL…L (concatenação de i cópias de L) 
 
EXEMPLOS 
 L={ 0,11} 
 
 L* = todas as strings de 0’s e 1’s com 1’s aos pares 
 
 L0={ e }, (independente de qual linguagem é L) 
 
 L1=L 
 
 os dois primeiros termos na expansão de L* são {e, 0, 11} 
 
 L2 = { 00, 011, 110, 1111} 
 
 L3 = { 000, 0011, 0110, 01111, 11011, 11110, 111111} 
 
 … 
 
CONSTRUINDO EXPRESSÕES REGULARES 
 Álgebras possuem expressões elementares a 
partir das quais construímos outras expressões 
através de um conjunto de operadores. 
 
 Também é necessário algum método para 
agrupar operadores com seus operandos, tais 
como parênteses. 
 
 
ÁLGEBRA DE EXPRESSÕES REGULARES 
 Essa álgebra pode ser definida indutivamente como 
segue: 
 
 Base: Consiste em 3 partes 
 
1. As constantes  e e são exp. reg. denotando as linguagens 
 e { e }, respectivamente. Isto é, L()=  e L(e)={e}. 
 
2. Se a é qualquer símbolo, então a é uma expressão regular. 
 L(a) = {a} 
 
3. Variáveis, em geral escritas em maiúsculas e em itálico, 
representam linguagens. 
ÁLGEBRA DE EXPRESSÕES REGULARES 
o Indução: há quatro partes na etapa indutiva. 
 
o Sejam E e F expressões regulares. Então: 
 
1. E + F é uma expressão regular, denotando a união de L(E) e L(F). 
 L(E) ∪ L(F) = L(E+F) 
 
2. EF é uma expressão regular denotando a concatenção de L(E) e 
L(F). 
 L(E)L(F) = L(EF) 
 
3. E* é uma expressão regular denotanto o fechamento de L(E). 
 L(E*) = (L(E))* 
 
4. (E) é uma expressão regular denotando a mesma linguagem que E. 
 L( (E) )=L(E) 
 
 
EXEMPLOS 
 A linguagem sobre  = {0,1} que consiste em 0’s e 1’s 
alternados. 
 
 (01)* + (10)* + 0(10)* + 1(01)* 
 (e+1)(01)*(e +0) 
 
PRECEDÊNCIA DOS OPERADORES 
 Os operadores das expressões regulares estão 
associados com seus operandos em uma ordem 
específica. 
 
1. O operador estrela tem a precedência mais alta. 
2. O operador “ponto” (concatenação). 
3. As uniões (operador +) são agrupadas a seus operandos. 
 
 Os parênteses podem ser aplicados para agrupar 
operandos e operadores segundo a finalidade 
desejada. 
 
 
EXEMPLO 
 Reagrupar a expressão 01*+1 
 
 O operador estrela é agrupado primeiro ao símbolo 1 
imediatamente à sua esquerda. 
 
 Em seguida fazemos a concatenação entre 0 e (1*), 
obtendo (0(1*)) 
 
 Por fim, o operador de união conecta esta última à 
expressão a sua direita: (0(1*)) +1. 
 
 Esta linguagem é o string 0 mais todos os strings que 
consistem por qualquer número de 1s (inclusive 
nenhum) mais o string 1. 
 
 
EXEMPLO 
 Usar parênteses para reagrupar a expressão 
01*+1: 
 
 Possíveis reagrupamentos: 
 (01)*+1 
 Denotando a linguagem contendo todos os strings que 
repetem “01” zero ou mais vezes mais o string 1; 
 
 0(1*+1) 
 Denotando a linguagem do conjunto de strings que 
começam com 0 e têm qualquer número de 1s em 
seguida. 
 
PERCEBA 
 (0+1)* denota a linguagem formada por todas as 
cadeias de 0´s e 1´s = {e, 0, 1, 00,01,10,11,000,...] 
 a+b*c denota um único a e todas as cadeias 
consistindo de zero ou mais vezes b seguido de c. A 
linguagem é formada por {a, c, bc, bbc, bbbc, ...} 
 (0+1)* 001 denota todas as cadeias de 0´s e 1´s 
terminadas em 001 
 0*1*2* denota qualquer número de 0´s seguido por 
qualquer número de 1´s seguido por qualquer número 
de 2´s 
 Igualdades 
 (a+b)*=(a+b)*+(a+b)* 
 (a+b)*=(a*b*)* 
 (a+b)*=(a+b)*(a+b)* 
 (a+b)*=a(a+b)*+b(a+b)*+ e 
EXERCÍCIO 
 Escreva expressões regulares para as seguintes 
linguagens. 
 
 Todas as cadeias sobre  = {a, b} com um número par de a’s, 
seguido por um número ímpar de b’s. 
 (aa)*b(bb)* 
 Todas as cadeias sobre  = {0, 1} com pelo menos um par de 
zeros consecutivos. 
 (0+1)*00(0+1)* 
 Todas as cadeias sobre  = {0, 1} que terminam em 01. 
 (0+1)*01 
 Todas as cadeias que contenham as subcadeias 000 e 111, 
nesta ordem. 
 (0+1)*000(0+1)*111(0+1)* 
 
 
EXERCÍCIO 
Encontre a ER para as Linguagens: 
 
 Consiste das palavras sobre o alfabeto ∑ = {a , b , c} que contém pelo 
menos um a e pelo menos um b 
 ((a+b+c)*a (a+b+c)*b (a+b+c)*)+((a+b+c)*b(a+b+c)*a(a+b+c)*) 
 Consiste das palavras sobre o alfabeto ∑ = {0 , 1} cujo o quinto símbolo 
é um 0 
 (0+1)(0+1) (0+1) (0+1)0(0+1)* 
 Consiste das palavras sobre o alfabeto ∑ = {a , b} que comece com b e 
finalize com a 
 b(a+b)*a 
 Consiste das palavras sobre o alfabeto ∑ = {a , b} que comece com bb 
ou um a 
 (bb+a)(a+b)* 
 Consiste das palavras sobre o alfabeto ∑ = {a , b} que contém no 
mínimo dois a 
 (a+b)*a (a+b)*a (a+b) 
 Consiste das palavras sobre o alfabeto ∑ = {a , b , c} que contém abc 
como subpalavra 
 (a+b+c)*abc (a+b+c)* 
AUTÔMATOS FINITOS E EXPRESSÕES 
REGULARES 
 Apesar das distinções entre as duas notações, os 
dois formalismos representam a mesma classe de 
linguagens. 
 
 Para demonstrar que expressões regulares e 
autômatos finitos são equivalentes, devemos 
mostrar que: 
 
1. Toda linguagem definida por um autômato finito é 
definida por uma expressão regular. 
2. Toda linguagem definida por uma expressão regular é 
definida por um autômato. 
EQUIVALÊNCIAS 
AFN 
AFD 
e-AFN 
ER 
DE AFD PARA EXPRESSÕES REGULARES 
 E.R. para definir uma liguagem de qualquer AFD é 
uma tarefa árdua. 
 Metodologia: Construímos expressões que 
descrevam conjuntos de strings que identificam 
certos caminhos no diagrama de transições do AFD. 
 Porém, só se permite que os caminhos passem por um 
subconjunto limitado dos estados. 
1 2 
0,1 
1 
0 
SIMPLIFICAÇÃO DE EXPRESSÕES 
REGULARES 
DE AFD PARA EXPRESSÕES REGULARES 
 Na definição indutiva: Começamos com expressões com nós únicos ou arcos 
únicos (e não quaisquer nós); 
 
 Construímos indutivamente expressões que permitem 
passar por conjuntos de estados progressivamente 
maiores; 
 
 Por fim, se permite que os caminhos possam passar por 
qualquer estado. 
1 2 
0,1 
1 
0 
TEOREMA 3.4 
 Se L = L(A), A é um AFD, então existe uma Exp. 
Reg. R, tal que L = L(R). 
 
 Prova 
 Suponha que os estados de A sejam {1,2,…,n}, n  ℕ. 
 
 A primeira tarefa é construir uma coleção de expressões 
regulares que descreva conjuntos de caminhos 
progressivamente mais amplos no diagrama de 
transições de A. 
 
 Suponha o nome da exp reg cuja linguagem é o 
conjunto de strings w tais que w é o rótulo do caminho 
do estado i ao estado j em A, sem nós intermediários 
cujo número seja maior que k. 
PROVA 
 Base: k = 0. 
 Tendo em vista que todos os estados são numerados com 1 
ou algum valor superior, a restrição é que os caminhos não 
podem ter estados intermediários. 
 
 Existem dois tipos de caminhos que satisfazem essa 
condição: 
1. Um arco do nó i para o nó j 
2. Um caminho de comprimento 0 que consiste apenas no nó i 
 
 Se i ≠ j apenas (1) é possível. Devemos analisar o AFD e 
encontrar os símbolos a tais que exista transição de i 
para j em a. 
PROVA 
a) Se não existe tal símbolo, então 
b) Se existe exatamente um símbolo a, então 
 
c) Se existem símbolos a1, a2, …, ak rotulando 
arcos do estado i para o estado j, então 
 
 = a1+ a2+ …+ ak 
 
 Se i=j, o caminho de comprimento 0 
corresponde à exp reg ε. Então, fazemos a 
união de ε a cada uma das exp encontradas nos 
casos (a) até (c) 
PROVA 
 Indução: suponha que exista um caminho do 
estado i para o estado j que não passa por nenhum 
estado maior que k. 
 Há dois casos possíveis a se considerar: 
 
1. O caminho não passa pelo estado k. Nesse caso o 
rótulo do caminho está na linguagem 
 
2. O caminho passa pelo estado k pelo menos 1 vez. 
Neste caso o caminho pode ser dividido da seguinte 
forma: 
a) O caminho de i a k sem passar por k 
b) O caminho de k a k sem passar por k 
c) O caminho de k a j sem passar por k 
PROVA 
 Quando combinamos as expressões dos dois 
tipos anteriores, temos: 
 
 
 
 para os rótulos de todos os caminhos desde o 
estado i até o estado j que não passam por 
nenhum estado mais alto que k. 
 
PROVA 
 Resumindo, 
 
 
 
 
 
 
 
 
 assumindo que temos 
 
 então 
1k
ijR
PROVA 
 
 No fim, teremos para todo i e j. 
 
 A expressão regular para a linguagem do 
autômato será a soma (união) de todas as exp 
reg tais que j é um estado de aceitação. 
EXEMPLO 
 Converter o seguinte AFD em uma expressão 
regular 
 
 
 
 
 
 
 Aceita todos as cadeias que tem ao menos um 0. 
1 2 
0,1 
1 
0 
EXEMPLO – EXPRESSÕES DE BASE (1O PASSO) 
1 2 
0,1 
1 
0 
 
 
e + 1 
0 
∅ 
(e + 0 +1) 
EXEMPLO – PARTE INDUTIVA 
 Os caminhos que passam pelo estado 1 são dados 
pela instancia da regra geral: 
 
 
 
EXEMPLO – PARTE INDUTIVA 1 2 
0,1 
1 
0 
EXEMPLO – PARTE INDUTIVA (2O PASSO) 
1 2 
0,1 1 
0 
0
11
0
11
0
11
0
11
1
11 *)( RRRRR 
i=j=1 
EXEMPLO – PARTE INDUTIVA (2O PASSO) 
1 2 
0,1 1 
0 
0
12
0
11
0
11
0
12
1
12 *)( RRRRR 
i=1 e j=2 
EXEMPLO – PARTE INDUTIVA (2O PASSO) 
1 2 
0,1 1 
0 
0
11
0
11
0
21
0
21
1
21 *)( RRRRR 
i=2 e j=1 
EXEMPLO – PARTE INDUTIVA (2O PASSO) 
1 2 
0,1 1 
0 
0
12
0
11
0
21
0
22
1
22 *)( RRRRR 
i=2 e j=2 
EXEMPLO – PARTE INDUTIVA 
 Os caminhos que passam somente por todos os 
estados (k=2) são dados pela instancia da regra 
geral: 
 
* 
1 2 
0,1 
1 
0 
EXEMPLO – PARTE INDUTIVA (3O PASSO) 
 Os caminhos que passam somente por todos os 
estados (k=2) são dados pela instancia da regra 
geral: 
 
* 
1 2 
0,1 1 
0 
1
21
1
22
1
12
1
11
2
11 *)( RRRRR 
i=1 e j=1 
EXEMPLO – PARTE INDUTIVA (3O PASSO) 
 Os caminhos que passam somente por todos os 
estados (k=2) são dados pela instancia da regra 
geral: 
 
* 
1 2 
0,1 1 
0 
1
22
1
22
1
12
1
12
2
12 *)( RRRRR 
i=1 e j=2 
EXEMPLO – PARTE INDUTIVA (3O PASSO) 
 Os caminhos que passam somente por todos os 
estados (k=2) são dados pela instancia da regra 
geral: 
 
* 
1 2 
0,1 1 
0 
1
21
1
22
1
22
1
21
2
21 *)( RRRRR 
i=2 e j=1 
EXEMPLO – PARTE INDUTIVA (3O PASSO) 
 Os caminhos que passam somente por todos os 
estados (k=2) são dados pela instancia da regra 
geral: 
 
* 
1 2 
0,1 1 
0 
1
22
1
22
1
22
1
22
2
22 *)( RRRRR 
i=2 e j=2 
EXEMPLO – PARTE INDUTIVA 
 A exp reg resultante é a união de todas as 
expressões em que o primeiro estado é o inicial e 
o último é um final. 
 
1 2 
0,1 
1 
0 
*