Linguagens Formais e Aut matos Aula 6 Express es Regulares 14.11.2017.2

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