Modulo2

Prévia do material em texto

30/04/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 1/4
 
Exercício 2:
Uma Linguagem aceita por uma Máquina de Turing é dita:
A)
Recursivamente enumerável;
B)
 Dinâmica;
C)
Regularmente Recursiva;
D)
 Regularmente Adaptável;
 
E)
Adaptável;
O aluno respondeu e acertou. Alternativa(A)
Comentários:
A) Enumerável deriva do fato de que as palavras de qualquer linguagem
enumerável recursivamente podem ser enumeradas ou listadas por uma Máquina
de Turing.
Exercício 3:
Para a classe das Linguagens Recursivas:
 
A)
não existe uma Máquina de Turing que a reconheça;
B)
existe pelo menos uma Máquina de Turing reconhecedora que sempre para qualquer que seja a entrada;
C)
https://online.unip.br/Arquivo?id=63518.pdf
30/04/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 2/4
existe uma classe equivalente de linguagens dinâmicas;
D)
existe pelo menos um autômato finito que sempre para qualquer que seja a entrada;
E)
existe uma classe equivalente de linguagens irregulares;
O aluno respondeu e acertou. Alternativa(B)
Comentários:
B) Equivalentemente, uma linguagem é recursiva se existe uma máquina de
Turing que sempre pára quando recebe uma sequência finita de símbolos do
alfabeto da linguagem como entrada e que aceita exatamente as palavras do
alfabeto da linguagem que são parte da linguagem e rejeita todas as outras
palavras.
Exercício 4:
A Classe das Linguagens Recursivas:
 
A)
está contida propriamente na Classe das Linguagens Enumeráveis Recursivamente;
B)
não pode ser reconhecida por uma máquina de Turing;
C)
não pode ser reconhecida por uma máquina de Turing que sempre para qualquer que seja a
entrada;
D)
 é sempre reconhecida por um autômato finito;
E)
é sempre reconhecida por um autômato de pilha;
O aluno respondeu e acertou. Alternativa(A)
Comentários:
A) Todas as linguagens recursivas também são recursivamente enumeráveis.
Exercício 7:
Considere as seguintes afirmativas:
30/04/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 3/4
I - Dada uma máquina de Turing M com alfabeto de entrada S e uma string w não se sabe se a
computação de M com entrada w vai não parar.
II -Máquinas de Turing aceitam quaisquer linguagens do Universo de todas as Linguagens;
III – Existe pelo menos uma Linguagem L que não é Recursivamente Enumerável. 
São corretas as afirmações:
A)
I, II, III;
 
B)
 Apenas I;
C)
 Apenas I e III;
D)
 Apenas II e III;
E)
 Apenas I e II;
 
O aluno respondeu e acertou. Alternativa(C)
Comentários:
E) Todas as linguagens são recursivamente enumeráveis.
A) Todas estão corretas
C) Nem todas as linguagens são aceitas;
Exercício 11:
A configuração de uma Máquina de Turing é indicada por um tripla, constituída dos seguintes
elementos:
A)
o estado inicial, o estado final e o estado vazio
B)
O estado corrente, o estado inicial e o estado final;
C)
A porção do conteúdo da fita de trabalho que se encontra à esquerda do cursor de acesso, porção
do conteúdo da fita de trabalho que se encontra à direita do cursor de acesso, incluindo a
posição correntemente apontada por ele e o estado corrente.
D)
Conjunto não vazio de estados, fita de trabalho e cadeia de entrada.
30/04/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 4/4
E)
Conjunto de estados, função parcial e alfabeto de entrada.
O aluno respondeu e acertou. Alternativa(C)
Comentários:
A) Esses são os 3 estados da tripla
B) Esses são os 3 estados da tripla
C) Esses são os 3 estados da tripla