Baixe o app para aproveitar ainda mais
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 ∪i0 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 1k 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 *
Compartilhar