Tema 05 - Expressões Regulares e Linguagens Regulares - GABARITO DOS 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 
GABARITO DOS EXERCÍCIOS 
1) Enumere TODAS as sequências de comprimento 2 ou 3 que pertençam às linguagens abaixo. 
a) L ( ab* v ba* ) Resp.: ab, ba, abb, baa 
b) L [ a(bb)* v b(aa)* ] Resp.: abb, baa 
c) L [ (a v b)* a (a v b) ] Resp.: aa, ab, aaa, aab, baa, bab 
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* ) Resp.: Sequências não vazias em que o símbolo inicial só ocorra uma única vez. 
b) L [ a(bb)* v b(aa)* ] Resp.: Sequências de comprimento ímpar, em que o símbolo inicial só ocorra 
uma única vez. 
c) L [ (a v b) (a v b) (a v b)* ] Resp.: Sequências contendo no mínimo dois símbolos. Ou 
Sequências de comprimento maior ou igual a 2. 
d) L [ (a v b) ( (a v b) (a v b) )* ] Resp.: Sequências de comprimento ímpar. 
e) L [ (a v b)* a (a v b) ] Resp.: Sequências em que o penúltimo símbolo é a. 
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). 
Resp.: b* a b* a b * 
 
b) Sequências em que o segundo e o terceiro símbolos sejam distintos. 
Resp.: (a v b) (ab v ba) (a v b)* ou então (a v b) ab (a v b)* v (a v b) ba (a v b)* 
 
c) Sequências de comprimento ímpar que contenham todos os símbolos iguais. 
Resp.: a(aa)* v b(bb)* 
 
d) Sequências de comprimento par e iniciadas pelo símbolo a. 
Resp.: a (a v b) ( (a v b) (a v b) )* 
 
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. 
Resp.: b* (a bb*)* ou então (ab v b)*