exercicios llc

Prévia do material em texto

���������	
����
����	�
�	�����	
��
���
��	��
��
���
�	����	�
�
������ � ���	
��� � � � � � � � 
�� � � � �� 
 
�� � � � 
! " # 
�� � $%
& ' (�� 
� � ) * � + � 
 
, � � ) -) �� � 
��� � � � � � � � 
��. � � 
+ � 
�� � /� , /� 
 
1) Desenvolva Gramáticas Livre de Contexto (GLC) que geram as seguintes linguagens: 
a) L = {a,b}* 
b) L = {w | w ε {a,b}* e w = wr, isto é, w é palíndromo e poder ser lido de trás para frente 
e vice-versa} 
c) L = {aib2i | i ≥ 1} 
d) L = {aibjck | i ≠ j ou j ≠ k} 
 
2) Considere a GLC 
G=(V,T,P,S) 
V={S,A,B} 
T={0,1} 
P={S → A1B, A → 0A | ε, B → 0B | 1B | ε} 
Qual a linguagem gerada? Essa linguagem é regular ou livre de contexto? Justifique sua 
resposta. 
 
3) Construa uma GLC capaz de gerar todo o conjunto de Expressões Regulares válidas 
sobre o alfabeto {0,1}. Dica: utilize "e" para indicar a palavra vazia da expressão 
regular. 
 
4) Verifique se a seguinte gramática e ambígua ou não, justificando a resposta. 
G=(V,T,P,S) 
V={S} 
T={a,b} 
P={S → SS | aSa | bSb | ε} 
 
5) Se a gramática construída no exercício 3 for ambígua, construa uma nova gramática 
removendo a ambigüidade. 
 
6) Construa Autômatos com Pilha (AP) que reconheçam as seguintes linguagens: 
a) L = {aib2i | i ≥ 1} 
b) L = {anbmcn+m | n,m ≥ 0} 
c) L = {ambn | m ≥ n} 
 
Respostas: 
 
1) 
a) G=(V,T,P,S) 
V={S} 
T={a,b} 
P={S→a | aS | b | bS | ε} 
 
b) G=(V,T,P,S) 
V={S} 
T={a,b} 
P={S→ aSa | bSb | a | b | ε} 
 
c) G=(V,T,P,S) 
V={S} 
T={a,b} 
P={S→ abb | aSbb} 
 
d) G=(V,T,P,S) 
V={S,A,B,C,D,E} 
T={a,b,c} 
P={S→ AB | CD, A→ aA | ε, B→ bBc | E | cD, C→ aCb | E | aA, D→ cD | ε, E→ bE | b} 
 
2) 
A linguagem é livre de contexto e regular. 
É livre de contexto porque pode ser representada por gramática livre de contexto. 
E é regular, pois é denotada pela seguinte expressão regular 0*1(0+1)*. 
(Note que se uma linguagem é regular, por definição ela também é livre de contexto.) 
 
3) 
G=(V,T,P,S) 
V={S} 
T={0,1,(,),+,*,∅,e} 
P={S→ S+S | SS | S* | (S) | 0 | 1 | ∅ | e} 
 
4) 
Sim, é ambígua, pois possui duas árvores de derivação para a palavra "aa". 
 
 
 
 
 
 
 
 
5) G=(V,T,P,E) 
S
S S
a S a e
e
S
SS
a S ae
e
V={E,T,F} 
T={0,1,(,),+,*,∅,e} 
P={E→ E+T | T, T→ TF | F, F→ F* | (E) | 0 | 1 | ∅ | e} 
6) 
a) 
 
b) 
 
c) 
 
(b,e,X)
(a,e,X)
(b,e,X)
(c,X,e)
(c,X,e)
(c,X,e)
(?,?,e) (?,?,e)
(a,e,BB)
(b,B,e) (?,?,e)
(b,B,e)
(b,B,e) (b,B,e)
(a,e,B)
(?,e,e) (?,e,e)