Linguagens Formais e Automatos - Atividade 4

Prévia do material em texto

Parte superior do formulário
Informações do teste
	Descrição
	
	Instruções
	
	Várias tentativas
	Não permitido. Este teste só pode ser feito uma vez.
	Forçar conclusão
	Este teste pode ser salvo e retomado posteriormente.
 Estado de Conclusão da Pergunta:
PERGUNTA 1
1. A máquina de Turing é um dispositivo teórico, conhecido como máquina universal, concebido pelo matemático britânico Alan Turing e que foi fundamental para o desenvolvimento da teoria da computação, tendo em vista ter sido o marco que deu origem aos primeiros dispositivos computacionais.
 
Considerando o texto apresentado, que aborda a implementação de uma das primeiras máquinas de Turing sob a ótica de sua essencialidade, analise as afirmativas a seguir e assinale V para a(s) verdadeira(s) e F para a(s) falsa(s).
 
I. (  ) A máquina de Turing foi inicialmente implementada como uma máquina automatizada capaz de calcular qualquer algoritmo e processar instruções.
II. (  ) Podemos dividir a aplicabilidade da máquina de Turing em problemas solucionáveis e problemas não solucionáveis ou não processáveis.
III. (  ) Para a máquina de Turing, uma das características de um algoritmo processável é ter uma descrição infinita e executável.
IV. (  ) Para a máquina de Turing, uma das características de um algoritmo processável é ter uma sequência de passos discretos.
 
Assinale a alternativa que apresenta a sequência correta.
	
	
	V, V, F, V.
	
	
	V, V, F, F.
	
	
	V, F, F, V.
	
	
	F, V, F, V.
 
	
	
	F, F, V, F.
1 pontos   
PERGUNTA 2
1. Na matemática, uma equação diofantina é uma equação polinomial que permite que duas ou mais variáveis assumam apenas valores inteiros. Uma equação linear diofantina é uma equação entre duas somas de monômios de grau zero ou um. Observe, a seguir, a equação diofantina:
 
 Diofantinas
ax + by = c
Solução inteira
 
Considerando o exposto, a fim de apresentar o funcionamento da equação diofantina, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
 
I. (  ) Equações diofantinas são equações algébricas com coeficientes inteiros.
II. (  ) Problemas diofantinos têm menos equações que variáveis desconhecidas e se resumem a achar soluções inteiras que deverão funcionar corretamente para todas as equações.
III. (  ) Ao se desenvolver um conhecimento sobre as equações diofantinas lineares em duas ou mais variáveis não será possível solucionar problemas.
IV. (  ) Dada uma equação diofantina P(a0,...,an) = 0, em que P é um polinômio com coeficientes inteiros, quer-se saber se existe um procedimento efetivo que seja capaz de determinar, em um tempo finito, se suas raízes são inteiras.
 
Assinale a alternativa que apresenta a sequência correta.
	
	
	V, V, F, V.
	
	
	F, V, F, V.
	
	
	V, F, F, V.
	
	
	F, F, V, F.
	
	
	V, V, F, F.
1 pontos   
PERGUNTA 3
1. O problema de decisão, o qual questionava a existência de um procedimento mecânico (baseado no trabalho de Gottfried Leibniz, que buscava um mecanismo mecânico de manipulação de fórmulas) capaz de decidir se, dado um enunciado (proposição) da lógica de primeira ordem, ele seria válido ou não, em um tempo finito.
 
Assinale a alternativa que indica a definição do problema de decisão.
	
	
	Yuri Matiyasevich provou que tal procedimento efetivo já existia.
	
	
	Alan Turing transforma-o em um problema de parada em sua máquina.
	
	
	Trata-se de obter uma teoria aritmética envolvendo resultados.
	
	
	Alonzo Church provou que já existia um algoritmo que deriva funções recursivas.
	
	
	Trata-se de usar resultados desconhecidos para obter resolução de problemas.
1 pontos   
PERGUNTA 4
1. Leia o trecho a seguir:
“O estudo da computabilidade tem como objetivo determinar a solucionabilidade de problemas, a partir da existência de algoritmos. Portanto, investiga os limites do que pode ser implementado em um computador, evitando a pesquisa de soluções inexistentes. A abordagem da compatibilidade é centrada nos problemas de decisão (do tipo sim/não)”.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 103.
 
A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas.
 
I. O estudo da computabilidade usa com frequência o princípio da redução.
Pois:
II. Ele analisa e determina as soluções de problemas a partir de algoritmos computacionais.
 
A seguir, assinale a alternativa correta.
 
	
	
	As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	
	
	As asserções I e II são proposições falsas.
	
	
	A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa.
	
	
	A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
	
	
	As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
1 pontos   
PERGUNTA 5
1. Leia o trecho a seguir:
“O modelo abstrato de computação, proposto por Turing em 1936 e conhecido como máquina de Turing, tinha como objetivo explorar os limites da capacidade de expressar soluções de problemas. Trata-se de uma proposta de definição formal da noção intuitiva de algoritmo. Diversos outros trabalhos, como Cálculo Lambda e funções recursivas, resultaram em conceitos equivalentes ao da máquina de Turing”.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 114.
 
A respeito da hipótese de Church, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
  
I. (  ) A hipótese de Church apresenta-se demonstrável como na noção computável ou na função de algoritmo.
II. (  ) A capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação.
III. (  ) A hipótese de Church não consegue afirmar que qualquer outra forma de expressar algoritmos terá a mesma capacidade computacional da máquina de Turing.
IV. (  ) A nomenclatura hipótese de Church não é assumida como verdadeira na ciência da computação.
 
Assinale a alternativa que apresenta a sequência correta.
	
	
	F, V, F, F.
	
	
	V, V, F, V.
	
	
	F, V, F, V.
	
	
	V, V, F, F.
	
	
	V, F, V, V.
1 pontos   
PERGUNTA 6
1. Leia o excerto a seguir:
Uma linguagem recursiva é uma linguagem formal, capaz de indicar se determinada palavra w pertence ou não à linguagem, ou seja, para uma dada linguagem L , existirá uma máquina de Turing que é determinada por w ∈ L ou w ∈ ~L, logo, teremos entradas finitas, onde se uma dada palavra pertencer a linguagem, esta é aceita, se não, esta é recusada.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 157.
 
A respeito das linguagens recursivas e dos autômatos e suas classes, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s).
 
I. (  ) Se w ∈ L, o algoritmo não pode identificar a palavra que pertence à linguagem.
II. (  ) Se w ∈ ~L, o algoritmo pode ficar em loop infinito.
III. (  ) As duas classes de linguagem recursiva não contrariam a ideia de algumas pessoas.
IV. (  ) Reconhecer o complemento de uma linguagem não é possível.
 
Assinale a alternativa que apresenta a sequência correta.
	
	
	V, F, V, V.
	
	
	V, V, F, V.
	
	
	F, V, F, V.
	
	
	V, V, F, F.
	
	
	F, V, F, F.
1 pontos   
PERGUNTA 7
1. Leia o trecho a seguir:
“Em 1936, Alonzo Church demonstrou a tese de Church, na qual afirmou que qualquer função computável poderia ser processada através de uma máquina de Turing, dessa forma, se criou a premissa de que sempre existirá um procedimento definido, no qual uma máquina de Turing processará uma função computacional”.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 159.
 
Considerando o excerto apresentado sobre as propriedades da máquina de Turing, analise as afirmativas a seguir.
 
I. É impossível apresentar formalmente se a máquina de Turing é, de fato, o modelo mais genérico de dispositivo computacional.
II. Todos os modelos conhecidos propostos após a máquina de Turing possuem, no máximo, a mesma capacidadecomputacional da máquina de Turing.
III. A tese de Church não foi assumida como uma hipótese para toda a teoria da computação, razão pela qual não é empregada.
IV. A máquina de Turing é um autômato cuja fita possui tamanho máximo e pode ser usada simultaneamente como dispositivo de entrada e de saída.
 
Está correto o que se afirma em:
	
	
	II e III, apenas.
	
	
	II, III e IV, apenas.
	
	
	I, II e III, apenas.
	
	
	I e II, apenas.
	
	
	I, II e IV, apenas.
1 pontos   
PERGUNTA 8
1. Leia o trecho a seguir:
“O teorema da não completude apresenta que todas as formulações axiomáticas consistentes da teoria dos números incluem proposições indecidíveis, ou seja, que não podem ser provadas como verdadeiras ou como falsas. Portanto, se um sistema formal é consistente, ele não pode ser completo, e a consistência dos axiomas não pode ser provada usando o próprio sistema formal”.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 144.
 
Considerando o excerto apresentado sobre o teorema da não completude e suas formulações, que não poderiam ser provadas como verdadeiras ou como falsas, analise as afirmativas a seguir.
 
 
I. O teorema da não completude é capaz de provar todas as verdades sobre as relações aritméticas.
II. O teorema da não completude estabelece limitação própria a quase todos os sistemas axiomáticos, exceto aos mais triviais.
III. O teorema da não completude pode ser usado para manipular qualquer máquina de Turing de única fita e, assim, a princípio, qualquer computador.
IV. Existe uma derivação formal do teorema da não completude, tal derivação é uma lista finita de passos, em que cada passo é obtido por meio de um axioma ou de regras de inferência básicas aplicadas a passos anteriores.
 
A seguir, assinale a alternativa correta.
	
	
	I e II, apenas.
	
	
	II e III, apenas.
	
	
	I, II e IV, apenas.
	
	
	I, II e III, apenas.
	
	
	II, III e IV, apenas.
1 pontos   
PERGUNTA 9
1. Apesar da sua simplicidade, o modelo máquina de Turing possui, no mínimo, a mesma capacidade, ou seja, o mesmo poder computacional de qualquer computador de propósito geral. O ponto de partida de Turing foi analisar a situação, a partir da qual uma pessoa, com um instrumento de escrita e um apagador, poderia realizar cálculos em uma folha de papel e, a partir disso, derivar resultados lógicos.
 
Assinale a alternativa que indica a sequência correta para essa operação simples.
	
	
	A pessoa é capaz de observar e alterar o símbolo de apenas um quadrado de cada vez, bem como de transferir sua atenção para somente um dos quadrados adjacentes.
	
	
	O conjunto de estados da mente da pessoa durante o processo de cálculo é infinito. Mais ainda, entre os “estado inicial” e “na metade”.
	
	
	O comportamento da pessoa, a cada momento, pode se perder, e sua atenção não está voltada somente para o símbolo.
	
	
	A natureza bidimensional do papel é um requisito essencial para os cálculos. Partindo do pressuposto de que o papel é organizado em quadrados.
 
	
	
	O conjunto de símbolos deve ser infinito e não representa informações complexas, sendo possível utilizar sequências de símbolos.
1 pontos   
PERGUNTA 10
1. Leia o trecho a seguir:
“A unidade de controle apresenta um número finito e predefinido de estados. A cabeça da fita tem a finalidade de ler o símbolo de uma célula, uma a cada vez, e gravar um novo símbolo por vez. Após a leitura/gravação (a gravação é realizada na mesma célula de leitura), a cabeça vai mover uma célula para a direita ou para a esquerda”.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 215.
 
A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas.
 
I. A fita é usada simultaneamente como dispositivo de entrada, de saída e de memória de trabalho.
Pois:
II. Define o estado da máquina e comanda as leituras, as gravações e o sentido de movimento da cabeça.
 
A seguir, assinale a alternativa correta
	
	
	A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
	
	
	As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
	
	
	As asserções I e II são proposições falsas.
 
	
	
	As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
	
	
	A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa.