Teoria da Computação - Lista 1

Prévia do material em texto

UERJ Universidade do Estado do Rio de Janeiro 
IME Instituto de Matemática e Estatística 
DICC Departamento de Informática e Ciência da Computação 
Profa. Maria Alice Silveira de Brito 
IME4614 Compiladores I T01 Exercícios da primeira parte da matéria 
pag.1 -20/10/14 
1. Considere as seguintes linguagens regulares 
definidas a seguir 
sobre o alfabeto  = {0,1} e para cada uma delas: 
i) Enumere os seus primeiros elementos – linguagens 
dos itens K a V. 
ii) Apresente uma gramática regular que a gere. 
iii) Apresente um autômato finito determinístico que 
a reconheça. 
iv) Apresente uma expressão regular que a denote. 
1. LA = { } 2. LB = { 0 } 
3. LC = { 1 } 4. LD = { 00 } 
5. LE = { 11 } 6. LF = { 000 } 
7. LG = { 00, 0000, 000000, 
... } 
8. LH = { , 00, 0000, 
000000, ... } 
9. LI = { 111, 111111, 
111111111, ...} 
10. LJ = { , 111, 111111, 
111111111, ...} 
11. LK = { w  
*  w 
possui um número de 
símbolos múltiplo de 2 e 
|w|  0 } 
12. LL = { w  
*  w possui 
um número de símbolos 
múltiplo de 2 e |w|  2 } 
13. LM = { w  
*  w 
possui um número de 
símbolos múltiplo de 3 } 
14. LN = { w  
*  w possui 
um número de símbolos 
múltiplo de 2 e começa com 
00 } 
15. LO = { w  
* w 
possui um número de 
símbolos múltiplo de 3 e 
termina com 11 } 
16. LP = { w  
* w possui 
um número de símbolos 
múltiplo de 3 e começa com 
000 } 
17. LQ = { w  
* w não 
possui nem 0’s nem 1’s 
isolados } 
18. LR = { w  
* símbolos 
inicial e final de w são 
distintos } 
19. LS = { w  
* w 
começa com um número 
par de 0’s e termina com 
um número ímpar de 1’s } 
20. LT = { w  
* w possui 
exatamente três 1’s} 
21. LU = { w  
* w 
possui exatamente três 1’s 
não consecutivos} 
22. LV = { w  
* w é 
constituída de um ou mais 
blocos consecutivos, cada um 
com cinco símbolos, tendo 
pelo menos dois 0´s} 
2. Essa gramática G = < N, , P, S >, abaixo, 
define as propriedades de um conjunto bem 
familiar seu, tente descobrir qual é esse 
conjunto, gerando cadeias por árvores de 
derivação, ou, por intuição. 
S  V  -V 
V  P ED 
D  AD  P 
E  1 2  3  4  5  6  7  8  9 
A  1 2  3  4  5  6  7  8  9  0 
P  0  2  4  6  8 
3-II) Enumere os elementos das seguintes linguagens 
e apresente a gramática correspondente a cada uma 
delas: 
3-II-a) LA = { a
ibj 1  i  j  2.i } 
3-II-b) LB = { a
ibic2j i, j 1 } 
3-II-c) LC = { w  {a,b}
+número de a’s = número 
de b’s} 
4. O exemplo mais famoso de ambigüidade em 
linguagem de programação é if b then if b then a else 
a, no qual o else pode estar associado tanto ao 
primeiro if quanto ao segundo. A seguinte gramática 
reflete esta ambigüidade. 
G1 = < {S}, {if, then, else, a, b }, P1 , S>, em 
que 
P1 = {S  if b then S else S  if b then S  a }. 
4-a) Mostre que G1 é ambígua. 
Esta ambigüidade pode ser tratada se, 
arbitrariamente, estabelecermos que, para o comando 
em questão, o else deva estar associado ao último 
then. A seguinte gramática reflete esta consideração: 
G2 = <{ S1, S2 }, {if, then, else, a, b}, P2 , S1>, em 
que, 
P2 = { S1  if b then S1  if b then S2 else S1 a 
 S2  if b then S2 else S2 a }. 
4-b) Apresente a árvore de derivação de G2 cujo 
resultado seja 
if b then if b then a else a 
5. Enumere os elementos da linguagem e construa o 
AFND M que reconheça 
L(M) = {xyz | x, z є {a,b}* e (y = aaa ou y =bb)} 
6. Apresente um AFD que reconheça a linguagem 
gerada pela gramática 
G = <{S,A,B}, {0,1}, P, S}, em que P é o 
seguinte conjunto 
S  0A1B 
A  1S 
B  0S 
 
 
 
 
 
 
 
8. Apresente uma expressão regular que represente a 
linguagem 
L = {a2ib2j+1c3k+3i  0, j  0, k  0}. 
9. Apresente o AFD que reconhece cada uma das 
seguintes expressões regulares: 
A) 0  (01)*00  1*0 B) (10100)*10 
10. Usando a estratégia apresentada em aula para 
provar que existe um autômato determinístico B que 
aceita a linguagem L aceita por um autômato não 
determinístico A, construa um autômato 
determinístico B que reconheça L dada relação de 
transição de A. Dê ainda a Linguagem L, a expressão 
regular correspondente, e prove que L é regular: 
a) F={q0} b) F={q2} 
 
 0 1 
A B A 
B C D 
C A B 
D C B 
1 a b 
q0 q1 {} 
q1 {} q2 
q2 q1 q2 
2 a b  
q0 q1 {} q2 
q1 q1 q1 {} 
q2 {} {} {} 
7. Apresente uma gramática 
regular que gere a linguagem 
reconhecida pelo AFD 
M=<{A,B,C,D},{0,1},, A, 
{C}>, em que  é definido por: