exercicio teoria responder (1)

Prévia do material em texto

1. Autômatos de Pilha são mais poderosos que as Gramáticas Livres de Contexto? Justifique. 
 
2. O que são Compiladores/Interpretadores? Como os Autômatos de Pilha são utilizados para a 
criação destes componentes para as Linguagens de Programação? 
 
 
3 Escreva o Autômato de Pilha e sua definição formal, para o modelo capaz de 
reconhecer cadeias no formato anb2nc3n, ou seja, reconhece cadeias com a 
quantidade de b’s é o dobro de a’s, e a quantidade de c’s é o triplo de a’s. O 
alfabeto da linguagem é {a,b,c}. 
 
4 Abaixo, mostramos um exemplo de Autômato de Pilha para reconhecer 
palavras cuja segunda metade é o inverso da primeira. 
 
 
Para cada palavra abaixo, encontre alguma computação que comprove que se ela 
é aceita pelo autômato. 
 
a. aa 
b.  
b. baab 
c. aaaa 
 
 
5 Com base na gramática abaixo, mostre uma derivação e uma árvore de derivação para a 
palavra 11 + 00 x 01. 
 
E → N 
| E+E 
| ExE 
 
N → 0 
| 1 
| 0N 
| 1N 
 
 
6 Considere a gramática definida abaixo. Diga se ela gera as palavras abaixo. 
Construa uma derivação e uma árvore de derivação para as palavras que a gramática 
puder gerar. 
 
S → aSa 
| bSb 
| T 
 
T → a 
| b 
|  
 
a)  
b) abab 
c) bbbb 
d) baa 
e) babab 
 
7 Prove que a gramática definida abaixo é ambígua. 
 
 
 
	a) (