mp1 2014.1

Prévia do material em texto

Universidade Federal de Pernambuco (UFPE) 
Centro de Informática (CIn) 
Graduação em Ciência da Computação 
 
Informática Teórica 
(IF689) 
1º Semestre de 2014 
1ª Mini-Prova 
Recife, 07 de Maio de 2014 
 
 
1. (6,0) Considere Σ como o conjunto de todos os caracteres que o compilador JAVA 
consegue ler. Faça o que se pede: 
a. (3,0) Projete um autômato que reconheça comentários JAVA em uma mesma 
linha. 
b. (3,0) A partir do autômato criado, aplique o algoritmo ensinado em sala para 
criar a expressão regular equivalente. 
 
2. (4,0) Sejam ∑ = {1, #} e 
Y = {w | w = x1#x2# . . . #xk para k ≥ 0, cada xi є 1*, e xi ≠ xj para i ≠ j}. 
Prove que Y não é regular. 
 
 
Boa prova!