21/06/2021 Avaliação Teórica Individual

Painel / Meus cursos / 2021/1 - 1118001 - 1 - TEORIA DA COMPUTAÇÃO / Semana 15 - 15/06 à 22/06 / Avaliação Teórica Individual

Questão 1
Ainda não respondida

Vale 1,0 ponto(s).

Defina a classe a mais restrita ao qual pertence a seguinte LINGUAGEM:

a. Linguagem Regular (LR)

b. Linguagem Livre de Contexto (LLC)

c. Linguagem Sensível ao Contexto (LSC)

Questão 2
Ainda não respondida

Vale 1,5 ponto(s).

Marque a alternativa do modelo que gera ou reconhece a linguagem a seguir:

a.

b.

c.

https://e-aula.ufpel.edu.br/mod/quiz/attempt.php?attempt=406515&cmid=314941 1/6
21/06/2021 Avaliação Teórica Individual

Questão 3
Ainda não respondida

Vale 1,5 ponto(s).

Descreva informalmente a linguagem reconhecida pelos AP a seguir:

        

https://e-aula.ufpel.edu.br/mod/quiz/attempt.php?attempt=406515&cmid=314941 2/6
21/06/2021 Avaliação Teórica Individual

Questão 4
Ainda não respondida

Vale 1,0 ponto(s).

Uma máquina de Turing consiste em uma máquina com quantidade finita de estados e uma fita finita a esquerda (delimitada pelo símbolo de
início de fita) e ilimitada a direita, dividida em células, cada célula contendo no máximo um símbolo pertencente a alfabetos finitos permitidos.
Em qualquer instante, apenas um número finito de células na fita não está em branco. Aqui são utilizados os símbolos * e B , para denotar os
símbolos de início de fita e branco, respectivamente. A unidade de controle, através de sua cabeça de leitura (que lê e escreve), lê uma célula da
fita por vez. A Figura abaixo ilustra a fita com a palavra de entrada 00.

Dependendo do estado atual da unidade de controle e do símbolo lido, a unidade pára o processamento (ou por chegar num estado final ou por
indefinição da função de transição ou por movimento inválido, tentando mover à esquerda quando a unidade de controle já está na célula mais
a esquerda) ou completa as três seguintes ações: grava um símbolo dos alfabetos na célula lida, vai para o próximo estado e move a cabeça de
leitura uma célula para a esquerda (L) ou para a direita (R).
Considerando a máquina de Turing M, definida a seguir, marque a alternativa que define a regra da função f :ℕ2 →ℕ computada por M.

Obs.: Os números naturais foram codificados usando a codificação unária, isto é, um número natural n é codificado pela sequência 0n, usando
um 1 para separar os argumentos na fita de entrada, quando for o caso. Por exemplo, segue a representação unária de alguns naturais:

0 = 𝜀 (palavra vazia)
1=0
2 = 00
3 = 000
...

https://e-aula.ufpel.edu.br/mod/quiz/attempt.php?attempt=406515&cmid=314941 3/6
21/06/2021 Avaliação Teórica Individual

a.

b.

c.

d.

e.

Questão 5
Ainda não respondida

Vale 1,4 ponto(s).

Marque as funções recursivas parciais que estão bem definidas e estejam sendo aplicadas a um número adequado de argumentos.

Escolha uma ou mais:

a. Comp[succ,Comp[p12,succ,C01]](x)
b. Pr[Comp[succ,C01],Comp[succ,p23]](x,y)
c. Pr[p22,Comp[succ,Pr[p23,C05]]](x,y,z)
d. p34(x,y,z)
e. Mn[Comp[p12,Comp[succ,C03],p23]](x,y,z)

Questão 6
Ainda não respondida

Vale 0,4 ponto(s).

Linguagens Turing-reconhecíveis são reconhecidas por uma máquina de Turing que pára para palavras que pertencem a linguagem.

Escolha uma opção:

Verdadeiro

Falso

Questão 7
Ainda não respondida

Vale 0,4 ponto(s).

A linguagem da aceitação da máquina de Turing AMT é Turing-reconhecível, embora não exista um decisor para AMT.

Escolha uma opção:

Verdadeiro

Falso

https://e-aula.ufpel.edu.br/mod/quiz/attempt.php?attempt=406515&cmid=314941 4/6
21/06/2021 Avaliação Teórica Individual

Questão 8
Ainda não respondida

Vale 0,4 ponto(s).

Como é possível estabelecer uma bijeção entre o conjunto das sequências binárias infinitas B e o conjunto de todas as linguagens L, então L é
infinito e não-enumerável.

Escolha uma opção:

Verdadeiro

Falso

Questão 9
Ainda não respondida

Vale 0,4 ponto(s).

Existe uma linguagem Turing-reconhecível cujo complemento não é Turing-reconhecível.

Escolha uma opção:

Verdadeiro

Falso

Questão 10
Ainda não respondida

Vale 1,0 ponto(s).

Qual das afirmações sobre crescimento assintótico é FALSA?

https://e-aula.ufpel.edu.br/mod/quiz/attempt.php?attempt=406515&cmid=314941 5/6
21/06/2021 Avaliação Teórica Individual

Questão 11
Ainda não respondida

Vale 0,3 ponto(s).

Qualquer problema NP-completo também está na classe NP.

Escolha uma opção:

Verdadeiro

Falso

Questão 12
Ainda não respondida

Vale 0,3 ponto(s).

Uma redução polinomial de um problema A para B é um algoritmo que converte qualquer instância de A em uma instância de B.

Escolha uma opção:

Verdadeiro

Falso

Questão 13
Ainda não respondida

Vale 0,4 ponto(s).

Escolha uma opção:

Verdadeiro

Falso

◄ CLASSES DE PROBLEMAS E PROBLEMAS NP-COMPLETOS

Seguir para...

AVALIAÇÃO DA DISCIPLINA ►

https://e-aula.ufpel.edu.br/mod/quiz/attempt.php?attempt=406515&cmid=314941 6/6