• 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

Projete o autômato de pilha para a linguagem formada pelas palavras que tem o seguinte formato: (0^n)#111#(1^(n+2)).

Questão 2

Para as linguagens abaixo, justifique quais são livres-de-contexto e quais não são. Para uma das linguagens que não for livre-de-contexto, utilize o lema do bombeamento em sua justificativa.

a) (0^n)(1^n)(2^m)(3^m), onde n,m >= 1.

b) (0^n)(1^m)(2^m)(3^n), onde n,m >= 1.

c) (0^n)(1^m)(2^n)(3^m), onde n,m >= 1.

d) (0^n)(1^m)(2^n)(3^m), onde n >= 1 >= m >= 0.

Questão 3

Discuta as seguites alternativas:

a) A classe das LLC é fechada pela operação de concatenação?

b) A classe das LLC é fechada pela operação de intersecção?

c) A classe das LLC é fechada pela operação de complemento?

d) A intersecção de uma linguagem regular com uma linguagem livre-de-contexto resulta em uma linguaguem de qual classe (regular, livre-de-contexto ou sensível-ao-contexto)? Por quê?