Baixe o app para aproveitar ainda mais
Prévia do material em texto
Professor Me. Paulo David pd.mnpa@gmail.com Faculdade Maurício de Nassau Curso: Sistemas de Informação Disciplina: Linguagens Formais e Autômatos Professor: Me. Paulo Roberto Sousa David Expressões Regulares • Em ciência da computação, uma expressão regular (ER) provê uma forma concisa e flexível de identificar cadeias de caracteres de interesse, como caracteres particulares, palavras ou padrões de caracteres. • São escritas em linguagem formal que pode ser interpretada por um processador de expressão regular. • O termo deriva do trabalho do matemático norte-americano Stephen Cole Kleene, que desenvolveu as expressões regulares como uma notação ao que ele chamava de álgebra de conjuntos regulares. • Seu trabalho serviu de base para os primeiros algoritmos computacionais de busca, e depois para algumas das mais antigas ferramentas de tratamento de texto da plataforma Unix. • O uso atual de expressões regulares inclui procura e substituição de texto em editores de texto e linguagens de programação, validação de formatos de texto (validação de protocolos ou formatos digitais) e filtragem de informação. • Um ponto crucial no estudo de linguagens é o de encontrar uma representação seja formal e finita. • A maioria dos formalismos provê pelo menos três operações para construir expressões regulares. Alternância: | • Uma barra vertical que separa alternativas. Exemplo: • rato|pato casa com rato ou pato. • Supermercado|Hipermercado casa com Supermercado ou Hipermercado. Agrupamento: ( ) • Parênteses são usados para definir o escopo e a precedência de operadores, entre outros usos. Exemplo: • Supermercado|Hipermercado é equivalente a (Super|Hiper)mercado. • Portanto, casa com Supermercado ou Hipermercado. Quantificação (ou repetição) • Um quantificador após um token (como um caractere) ou um agrupamento especifica a quantidade de vezes que o elemento precedente pode ocorrer. Quantificação (ou repetição) • Os quantificadores mais comuns são ?, * e +. Meta mnemônico ocorrência ? opcional zero ou um * asterisco zero, um ou mais + mais um ou mais Exemplos: Padrão Casa com ac?ção acção, ação ab?c ac, abc ab*c ac, abc, abbc, abbbc, abbbbc,... ab+c abc, abbc, abbbc, abbbbc,... a|b* ε, a, b, bb, bbb,... (a|b)* ε, a, b, aa, ab, ba, bb, aaa,... ab*(c|ε) a, ac, ab, abc, abb,... Definição 11: Dado um alfabeto Σ, as expressões regulares (ER) sobre este alfabeto são definidas recursivamente da seguinte forma: • ∅, (ou λ) e cada elemento a ∈Σ são ER; • se r e s são ERs então (r + s), (r.s) e (r*) são ER; • As ERs são obtidas unicamente pelas regras acima. • Expressões regulares podem expressar linguagens regulares, ou seja, a classe de linguagens aceita por um autômato finito. • Toda Linguagem Regular pode ser descrita por uma expressão denominada Expressão Regular. • Expressão Regular trata-se de um formalismo denotacional, também considerado gerador, pois se pode inferir como construir (gerar) as palavras de uma linguagem. ER Linguagem Gerada aa Somente a palavra aa ba* Todas as palavras que iniciam por b, seguido por, zero ou mais a (a+b)* Todas as palavras sobre {a,b} ER Linguagem Gerada (a+b)*aa(a+b)* Todas as palavras contendo aa como subpalavra a*ba*ba* Todas as palavras contendo exatamente dois b (a+b)*(aa+bb) Todas as palavras que terminam com aa ou bb Exemplo 1: Considere o AFD a seguir: Este AFD aceita as seguintes palavras: bb, babb, bababb, babababb, babababababb, ... S0 S3S1 b S2 b ab Este AFD aceita as seguintes palavras: bb, babb, bababb, babababb, babababababb, ... Considerando o alfabeto = {a,b}, podemos concluir que o AFD dado é equivalente a Expressão Regular: b(ab)*b. E por conseguinte, escrevemos a linguagem que é equivalente ao AFD e a ER, como: L = {b(ab)nb | n≥0} Exercício 2: Escreva a ER e a Linguagem que correspondem ao AFD a seguir: a) Reposta: ER: ba*ba L = {banba | n≥0} q0 b q1 q2 q3 b a a Exercício 3: Escreva a ER e a Linguagem que correspondem ao AFD a seguir: a) Reposta: ER: (ba*a)|(ab) L = {(bana)+(ab) | n≥0} q0 b q1 q2 q3 a a a b Exemplo 4: Considere o AFD a seguir: AFD dado é equivalente a Expressão Regular: ((b|c|d)(b|c|d)*(b|c|d)a*)|(aa*) q0 a q2 q1 a b,c,d b,c,d b,c,d Exercício: Escreva a ER e a Linguagem que correspondem ao AFD a seguir: b) q0 a q1 q2 q3 b a b q4 b a Professor Me. Paulo David pd.mnpa@gmail.com Faculdade Maurício de Nassau Curso: Sistemas de Informação Disciplina: Linguagens Formais e Autômatos Professor: Me. Paulo Roberto Sousa David Expressões Regulares
Compartilhar