2 ERGram

Expressões Regulares e
Gramáticas

profa. Laís do Nascimento Salvador
E-mail: [e-mail]
Grande parte dos slides foi gentilmente cedida pelo prof. Ivan Carlos Alcântara de Oliveira

Teoria dos Autômatos
Expressões Regulares
•

A expressão regular é a maneira mais compacta e mais simples de descrever conjuntos regulares, e é usada com essa finalidade em construção de compiladores, editores, sistemas operacionais, protocolos, etc.

•

É um formalismo denotacional, também considerado gerador.

Teoria dos Autômatos
Expressões Regulares
Definição: Uma Expressão Regular (ER) sobre um alfabeto Σ é definida como segue:
• φ é uma ER (linguagem vazia)
• ε é uma ER (linguagem contendo somente a cadeia vazia ε)
• para cada a ∈ Σ, a é uma ER
• se α e β são ER´s, então α|β é uma ER. (α OU β
– alternância)
• se α e β são ER´s, então αβ é uma ER.
(concatenação)
• se α é uma ER, então (α) * é uma ER
(exponenciação)

Teoria dos Autômatos
Expressões Regulares
•

α*: ε | α | αα | ααα |.....

•

α+: α | αα | ααα |.....

•

α+ = αα*

•

ordem de precedência(decrescente):
– exponenciação
– concatenação
– alternância

Teoria dos Autômatos
Expressões Regulares
Expressão regular Linguagem representada aa Somente a palavra aa

ba*

Todas as palavras que começam com b, seguido por zero ou mais a´s

(a|b)*

Todas as palavras sobre {a, b}

(a|b)* aa (a|b) *

Todas as palavras que contém aa como subpalavra a* ba* ba*

Todas as palavras contendo exatamente
2 b´s

(a|b)* (aa| bb )

Todas as palavras que terminam com aa ou bb

(a| ε) (b | ba)*

Todas as palavras que não possuem 2 a

Teoria dos Autômatos
Expressões Regulares - Exercícios
Exercícios:
1. Indique se a cadeia 1011 pertence às linguagens correspondentes a cada uma das expressões regulares
a) __________ (10)*1011
b) __________ 0*(10 | 11)*
c) __________ 1(00)*(11)*
d) __________ (1 | 00)(01 | 0)1*
2) Escreva uma expressão regular para cada uma das seguintes linguagens sobre o alfabeto {a,b}:
a) O conjunto de