Introdução Teoria da Computação Provas 2Va e 3Va

Prévia do material em texto

Universidade Federal Rural de Pernambuco
Departamento de Estatística e Informática
Disciplina: Introdução à Teoria da Computação
Professor: Pablo Azevedo Sampaio
Aluno: _____________________________________________
2ª Verificação de Aprendizagem
Considere a gramática livre de contexto abaixo. Considere que os não-terminais aparecem entre < e > e os terminais são tudo que está entre aspas. Assuma que o não-terminal inicial é <comando>.
�
Mostre uma árvore de derivação para uma cadeia qualquer. (1,0). Separadamente, mostre somente a cadeia gerada. (0,5).
Prove que a gramática é ambígua. Dica: a ambigüidade existe a partir do não-terminal <expr> das expressões. (1,0)
Converta a gramática abaixo para um autômato com pilha. O alfabeto terminal da gramática é {a,b,c}. (1,5).
�
Mostre a computação de aceitação de uma cadeia qualquer no autômato criado na questão anterior. (1,0).
A máquina de Turing abaixo aceita apenas as cadeias que têm duas partes idênticas formadas com símbolos a e b e separadas entre si por # (ou seja, cadeias na forma w#w, para w ( {a,b}* ). 
Mostre a computação que rejeita a cadeia b#a nesta MT. (1,0).
Mostre a computação que aceita a cadeia b#b nesta MT. (1,0).
Descreva de maneira informal como a MT vai se comportar ao receber a cadeia baba#baba, descrevendo as sucessivas alterações que ela fará na fita durante o processo. (1,0).
O que é um problema de decisão? Quando ele é chamado de decidível? (1,0). 
Explique o problema da parada, descrevendo suas entradas e saídas. Diga se este é um problema decidível ou indecidível. (1,0).
Boa prova!
<comando> ( <nome> “=” <expr> “;”
 | “retorne” <expr> “;”
<expr> ( <expr> “+” <expr>
 | <expr> “*” <expr>
 | <nome>
 | “10”
<nome> ( “aux” | “temp” | “x” 
		X ( aXb
| Y
 		Y ( c
 | (