exerc5cap3GR_monitorRafael

Prévia do material em texto

Exercício Gramáticas Regulares 
Lista elaborada pelo monitor Rafael 
1. Converta as seguintes ER em AFND-ɛ: 
a) 01* 
b) (0+1)01 
c) (0+1)*1(0+1) 
 
2. Construa gramáticas regulares para as seguintes linguagens (a e b sobre o alfabeto 
{0,1}): 
a) L = {w ϵ ∑* | w inicia sempre por 1 e termina sempre com 0} 
b) L = {w ϵ ∑* | w tem no máximo tamanho 3} 
b) O conjunto das cadeias sobre {a, b, c} que não contém aa. 
 
3. Transforme as gramáticas do exercício anterior em autômatos finitos. 
 
4. Dados os seguintes autômatos finitos determinísticos, converta-os para gramáticas 
regulares: 
a) 
 
 
b)