Tema 05 - Expressões Regulares e Linguagens Regulares - EXERCÍCIOS

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
TEMA 5: Expressões Regulares e Linguagens Regulares 
 
EXERCÍCIOS 
Após estudar o material relativo ao tema Expressões Regulares e Linguagens Regulares, resolva os exercícios a 
seguir, extraídos do MATERIAL DE APOIO. 
1) Enumere TODAS as sequências de comprimento 2 ou 3 que pertençam às linguagens abaixo. 
a) L ( ab* v ba* ) b) L [ a(bb)* v b(aa)* ] c) L [ (a v b)* a (a v b) ] 
2) Descreva em português as linguagens regulares abaixo. 
Considere implicitamente o alfabeto I = { a, b } na sua descrição: 
a) L ( ab* v ba* ) 
b) L [ a(bb)* v b(aa)* ] 
c) L [ (a v b) (a v b) (a v b)* ] 
d) L [ (a v b) ( (a v b) (a v b) )* ] 
e) L [ (a v b)* a (a v b) ] 
3) Escreva as expressões regulares que caracterizem as linguagens a seguir. Considere o alfabeto { a, b }. 
a) Sequências que tenham exatamente dois símbolos a (e qualquer quantidade de b’s). 
b) Sequências em que o segundo e o terceiro símbolos sejam distintos. 
c) Sequências de comprimento ímpar que contenham todos os símbolos iguais. 
d) Sequências de comprimento par e iniciadas pelo símbolo a. 
e) Sequências em que toda ocorrência de a seja imediatamente sucedida por uma ocorrência de b. 
ATENÇÃO: as sequências λ e bbb se adequam à definição, e devem ser contempladas na expressão regular.