Prévia do material em texto

01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 1/6
 Exerícios complementares
Exercício 1:
POSCOMP - 2009 Questão 40 - Assinale a alternativa FALSA
 
 
 
 
A)
O conjunto de todas as Máquinas de Turing é enumerável.
 
B)
O conjunto de todas as Expressões Regulares é enumerável.
 
C)
Toda Linguagem Regular é enumerável.
 
 
D)
Todo Conjunto Finito é enumerável.
 
E)
Nenhum Conjunto Infinito é enumerável.
 
O aluno respondeu e acertou. Alternativa(E)
Comentários:
A) Todas as máquinas de touring são eumeráveis
E) sem justificativa
Exercício 2:
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 2/6
 Poscomp 2011Questão 26: A teoria da computabilidade, em conjunto com a álgebra booleana,
garante que é possível construir um processador com um conjunto de instruções unitário que
possua capacidade de resolver qualquer problema solúvel. Suponha que exista uma organização
de computador convencional, dotada de um processador de umainstrução, memória e periféricos
de entrada e saída. Com relação à instrução única que o processador executa, considere as
afirmativas a seguir.
I. Deve obrigatoriamente fazer acesso a um dispositivo de entrada e saída.
II. Deve obrigatoriamente ler e escrever na memória principal do processador.
III. Deve obrigatoriamente calcular uma soma de produtos de literais booleanos.
IV. Deve obrigatoriamente realizar um teste, e sua ação deve ser condicionada ao resultado deste
teste.
Assinale a alternativa correta.
A)
Somente as afirmativas I e II são corretas.
B)
Somente as afirmativas II e IV são corretas.
C)
Somente as afirmativas III e IV são corretas.
D)
 Somente as afirmativas I, II e III são corretas.
E)
Somente as afirmativas I, III e IV são corretas.
O aluno respondeu e acertou. Alternativa(B)
Comentários:
C) sem justificativa
B) sem justificativa
Exercício 3:
Poscomp 2011 - Questão 38: Com relação às linguagens e seus aceitadores,
considere as afirmativas a seguir.
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 3/6
I. {wwrev / w∈{a,b}*} é aceita por autômato de pilha determinístico.
II. {wcwrev / w∈{a,b}*} é aceita por autômato finito não determinístico.
III. {a,b}*-{ww / w∈{a,b}*} é aceita por autômato de pilha não determinístico.
IV. {M / M é M.T. e M para} é aceita for Máquina de Turing não determinística.
Assinale a alternativa correta.
 
 
A)
Somente as afirmativas I e II são corretas
 
 
 
B)
Somente as afirmativas II e IV são corretas.
 
 
 
 
C)
Somente as afirmativas III e IV são corretas.
 
 
 
D)
Somente as afirmativas I, II e III são corretas.
 
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 4/6
E)
Somente as afirmativas I, III e IV são corretas.
 
O aluno respondeu e acertou. Alternativa(C)
Comentários:
D) sem justificativa
E) sem justificativa
C) sem justificativa
Exercício 4:
Fundamentada na questão 26 Poscomp 2011 A teoria da computabilidade, em conjunto com
a álgebra booleana, garante que é possível construir um processador com um conjunto de
instruções unitário que possua capacidade de resolver qualquer problema solúvel. Suponha que
exista uma organização de computador convencional, dotada de um processador de umainstrução,
memória e periféricos de entrada e saída. Com relação à instrução única que o processador
executa, considere as afirmativas a seguir.
I. Deve obrigatoriamente fazer acesso a um dispositivo de entrada e saída.
II. Deve obrigatoriamente ler e escrever na memória principal do processador.
III. A máquina de Turing prevê as operações I e II.
Assinale a alternativa correta.
A)
I e III são corretas;
B)
I e II são corretas.
C)
Apenas II é correta.
D)
Apenas I é correta.
E)
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 5/6
A afirmativa III justifica as afirmativas I e II..
O aluno respondeu e acertou. Alternativa(C)
Comentários:
B) sem justificativa
C) sem justificativa
Exercício 5:
Fundamentada na questão 26 - Poscomp 2011
A teoria da computabilidade, em conjunto com a álgebra booleana,
garante que é possível construir um processador com um conjunt o de
instruções unitário que possua capacidade de resolver qualquer problema
solúvel. Suponha que exista uma organização de computador
convencional, dotada de um processador de umainstrução, memória e
periféricos de entrada e saída. Com relação à instrução única que o
processador executa, considere as afirmativas a seguir.
I. Deve obrigatoriamente ler e escrever na memória principal do processador.
II. Deve obrigatoriamente realizar um teste, e sua ação deve ser condicionada ao resultado deste
teste.
Assinale a alternativa correta.
A)
A máquina de Turing não realiza a operação descrita em I.
B)
A máquina de Turing não realiza a operação enunciada em II.
C)
As operações dos processadores exlcluem o conceito de Máquina de Turing.
D)
A memória, apesar de ser um dispositivo de armazenamento, não pode ser
associada ao dispositivo de armazenamento fita de entrada da máquina de turing.
A fita de entrada da máquina de turing nunca pode ser limitada.
E)
As operações enunciadas em I e II são executadas pela Máquina de Turing.
01/05/2020 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 6/6
O aluno respondeu e acertou. Alternativa(E)
Comentários:
B) sem justificativa
A) sem justificativa
E) sem justificativa