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

Aviso!

As questões apresentadas a seguir são descrições baseadas em relatos de um ou mais alunos que fizeram tal avaliação. Logo, não há garantia de que os enunciados sejam iguais aos originais, tampouco que estejam livres de erros. Esteja ciente dessas considerações ao utilizar esse material!

Questões

Questão 1

Dadas três linguagens (A, B e C), decide-se criar uma quarta linguagem L, tal que L é formada por todas as palavras que são de A e B ou que são de A e C mas que não pertencem às três linguagens simultaneamente. Sobre a linguagem L, o que é possível afirmar sobre ela se as três linguagens forem decidíveis E se uma das linguagens originais for reconhecível?

• Observação: Analise se L é decidível/reconhecível/irreconhecível para cada cenário.

Questão 2

Dê um exemplo de linguagem com as seguintes características:

a) A linguagem é decidivel, mas não reconhecível.

b) A linguagem é reconhecível, mas não decidivel.

c) A linguagem é irreconhecivel.

Questão 3

Assinale com verdadeiro (V) ou falso (F) e discuta o motivo de sua escolha, em cada caso.

a) ( ) O complemento de uma linguagem reconhecivel, pode ser ou não irreconhecível.

b) ( ) Verificar se dois autômatos possuem a mesma linguagem é um problema irreconhecível, já que seria necessário executar infinitos casos para esta provar.