• Disciplina: Teoria da Computação
• Período: 2017.1

Questões

Questão 1

Construa um autômato com pilha para mostrar que w#w' é possível, onde w != w’. Podemos assumir que os dois lados tem o mesmo tamanho.

Questão 2

Mostre, utilizando autômatos de pilha, que a classe das linguagens livres-de-contexto é fechada pelas operações de intersecção, complemento e concatenação.

Questão 3

Faça uma máquina de Turing calculadora que divide uma palavra em três pedaços. Por exemplo, se a palavra de entrada for 001001001, o resultado deverá ser 001'001'001.

Questão 4

Construa uma máquina de Turing que insere um símbolo # em uma posição marcada da palavra. Por exemplo, se a palavra de entrada é 001'001, depois de executar, a fita deverá conter a palavra 001#001.

Questão 5

Classifique as alternativas abaixo como Verdadeiro ou Falso, justificando as falsas.

a) ( ) Para toda linguagem gerada por uma GLC, existe pelo menos um autômato com pilha determinístico que a reconhece.

b) ( ) É possível construir uma máquina de Turing que reconhece a linguagem L = {(2^n)(3^2n)(4^3n) | n ≥ 1}.

c) ( ) O lema do bombeamento para linguagens livres-do-contexto é utilizado para provar que uma linguagem não é livre-de-contexto.

d) ( ) A linguagem A = {ww| w pertence a {0,1}\}* é livre-de-contexto.

e) ( ) O lema do bombeamento para linguagens livres-do-contexto é uma generalização do lema do bombeamento para linguagens regulares.