Atividade 4 - Linguagens Formais e Autôamatos - RonieCamiloUAM22092021

Prévia do material em texto

Usuário RONIE CAMILO 
Curso GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-
212-9 - 202120.ead-17613.01 
Teste ATIVIDADE 4 (A4) 
Iniciado 08/09/21 16:42 
Enviado 22/09/21 09:21 
Status Completada 
Resultado da 
tentativa 
8 em 10 pontos 
Tempo decorrido 328 horas, 39 minutos 
Resultados 
exibidos 
Respostas enviadas, Respostas corretas, Comentários 
• Pergunta 1 
1 em 1 pontos 
 
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 capacidade computacional 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: 
 
Resposta Selecionada: 
I e II, apenas. 
 
Resposta Correta: 
I e II, apenas. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, porque é 
impossível apresentar formalmente se a máquina de Turing 
é, de fato, o modelo mais genérico de dispositivo 
computacional, dado que se trata de uma noção intuitiva e 
não matemática, e todos os modelos conhecidos propostos 
após a máquina de Turing possuem, no máximo, a mesma 
capacidade computacional da máquina de Turing, o que, por 
sua vez, indica que as alternativas I e II corretas. As 
alternativas III e IV estão incorretas, quanto a 
impossibilidade de representar formalmente a máquina de 
Turing como modelo mais genérico, bem como a 
capacidade máxima computacional. 
 
• Pergunta 2 
1 em 1 pontos 
 
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. 
 
 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, mas a 
II não é uma justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposições verdadeiras, mas a 
II não é uma justificativa correta da I. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, a asserção I é 
uma proposição verdadeira, já que, de fato, o estudo da 
computabilidade é usado com frequência para o princípio da 
redução, pois investiga a solucionabilidade de um problema 
a partir de outro. A asserção II não é uma justificativa 
 
correta da I, uma vez que a justificativa de analisar soluções 
de problemas não se relaciona ao estudo da 
computabilidade aplicada ao princípio da redução, logo, são 
independentes. 
 
• Pergunta 3 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
I e II, apenas. 
Resposta Correta: 
I e II, apenas. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, porque, 
segundo o matemático Kurt Gödel, a teoria é 
recursivamente enumerável e capaz de expressar verdades 
básicas da aritmética e alguns enunciados da teoria da 
prova, assim, pode provar sua própria consistência se, e 
somente se, for inconsistente, assim, por definição, o 
teorema da não completude estabelece limitação própria a 
quase todos os sistemas axiomáticos, exceto aos mais 
triviais. 
 
 
• Pergunta 4 
1 em 1 pontos 
 
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. 
 
Resposta Selecionada: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Resposta correta. A sequência está correta. A afirmativa I é 
verdadeira, porque a máquina de Turing foi inicialmente 
implementada como uma máquina automatizada capaz de 
calcular qualquer algoritmo e processar instruções. A 
afirmativa II está correta, pois podemos dividir a 
aplicabilidade da máquina de Turing em problemas 
solucionáveis e problemas não solucionáveis ou não 
processáveis. A afirmativa IV é verdadeira, uma vez que, 
para a máquina de Turing, uma das características de um 
algoritmo processável é ter uma sequência de passos 
discretos, logo, somente a alternativa III apresenta erro ao 
definir uma descrição infinita. 
 
 
• Pergunta 5 
1 em 1 pontos 
 
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 grauzero 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. 
Resposta Selecionada: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Resposta correta. A sequência está correta. A afirmativa I é 
verdadeira, porque, de fato, as equações diofantinas são 
equações algébricas com coeficientes inteiros. A afirmativa 
II é verdadeira, uma vez que as variáveis resumem-se a 
achar soluções inteiras, logo, deverão funcionar 
corretamente para todas as equações. A afirmativa IV é 
verdadeira, pois, na situação apresentada, busca-se 
estabelecer fundamentos rigorosos para a aritmética e 
representar todas as leis científicas em equações 
matemáticas. Logo, uma equação diofantina é uma equação 
polinomial que permite que duas ou mais variáveis 
assumam apenas valores inteiros. 
 
 
• Pergunta 6 
1 em 1 pontos 
 
Leia o trecho a seguir: 
“Uma consequência importante do estudo das linguagens recursivamente 
enumeráveis é que, computacionalmente falando, existem mais problemas 
não computáveis (para os quais não existem máquinas de Turing capazes 
de processá-los) do que problemas computáveis (caso contrário)”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 169. 
 
 
A partir do apresentado, analise as asserções a seguir e a relação proposta 
entre elas. 
 
I. A classe das linguagens recursivamente enumeráveis inclui algumas 
linguagens, para as quais é impossível determinar mecanicamente se uma 
palavra não pertence à linguagem. 
Pois: 
II. Um problema computável sempre será um problema parcialmente 
solucionável, todavia, há vários cenários, em que existem problemas não 
computáveis, aos quais a máquina de Turing não se aplica. 
 
A seguir, assinale a alternativa correta. 
 
Resposta 
Selecionada: 
 
A asserção I é uma proposição verdadeira, e a 
asserção II é uma proposição falsa. 
Resposta Correta: 
A asserção I é uma proposição verdadeira, e a 
asserção II é uma proposição falsa. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a asserção 
I é uma proposição verdadeira, já que, de fato, a classe das 
linguagens recursivamente enumeráveis inclui algumas 
linguagens para as quais é impossível determinar, 
mecanicamente, se uma palavra não pertence à 
linguagem. A asserção II é uma proposição falsa, porque 
um problema computável pode ser um problema 
parcialmente solucionável, logo, nem sempre será 
parcialmente solucionavel, uma vez que existem problemas 
não computáveis, aos quais a máquina de Turing não se 
aplica. 
 
 
• Pergunta 7 
0 em 1 pontos 
 
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. 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
F, V, F, F. 
Comentário 
da resposta: 
Sua resposta está incorreta. A sequência está incorreta, 
porque a hipótese de Church é declarada verdadeira para 
toda ciência da computação, logo, não existe exceção à 
aplicação da hipótese de Church. A aplicabilidade da 
hipótese, na máquina de Turing, é reconhecida como classe 
de linguagens recursivamente enumeráveis, logo, não é 
possível demonstrar a hipótese ou atribuir um limite 
máximo, sendo ela teórica e incompatível com 
representação prática, consistindo em um modelo teórico. 
 
 
• Pergunta 8 
0 em 1 pontos 
 
Leia o trecho a seguir: 
“Com o passar do tempo vários modelos surgiram, e a máquina de Turing é 
o modelo mais basilar da teoria da computação, porém, apesar das várias 
modificações, observou-se que, ao mudar as variáveis, os outros modelos 
não se mostraram diferentes em relação à máquina de Turing”. 
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 
2015. p. 114. 
 
Considerando o excerto apresentado sobre a definição do modelo autômato 
com múltiplas pilhas, analise as afirmativas a seguir: 
 
I. As combinações de múltiplas modificações na máquina de Turing aumenta 
o poder computacional da máquina de Turing. 
II. Trata-se de uma nítida proporção entre a máquina de Turing e as pilhas. 
III. Adicionar um maior número de pilhas não gerará aumento da eficácia 
computacional. 
IV. A definição básica é que a máquina de Turing permite que a fita seja 
limitada dos dois lados. 
 
Está correto o que se afirma em: 
 
Resposta Selecionada: 
I e II, apenas. 
Resposta Correta: 
II e III, apenas. 
Comentário 
da resposta: 
Sua resposta está incorreta. A alternativa está incorreta. 
Lembre-se de que são necessárias duas pilhas para que o 
autômato possua o mesmo poder computacional que uma 
máquina de Turing. Além disso, a estrutura de fita é mais 
expressiva que a de pilha, em relação à definição formal do 
autômato com duas pilhas e do autômato com múltiplas 
pilhas e a proporção deles relacionada à máquina de Turing, 
o que faz com que as alternativas I e IV estejam incorretas. 
 
 
• Pergunta 9 
1 em 1 pontos 
 
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 
 
Resposta 
Selecionada: 
 
As asserções I e II são proposições verdadeiras, mas a 
II não é uma justificativa correta da I. 
Resposta Correta: 
As asserções I e II são proposiçõesverdadeiras, mas a 
II não é uma justificativa correta da I. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a asserção 
I é verdadeira, já a fita é finita à esquerda e infinita à direita 
e é tão grande quanto necessário, sendo dividida em 
células, cada uma armazenando um símbolo, logo, as 
asserções I e II, são verdadeiras, mas a II não é razão ou 
justificativa da I. 
 
 
• Pergunta 10 
1 em 1 pontos 
 
O diagrama de transição de estados, ou diagrama de máquina de estados, é uma 
representação do estado ou situação em que um objeto pode se encontrar no 
decorrer da execução de processos de um sistema. Observe a imagem a seguir, 
que apresenta uma ilustração de um diagrama de transição a fim de exemplificar o 
funcionamento da máquina de Turing: 
 
Figura – Exemplo de um diagrama de transição 
Fonte: Adaptada de Passos (2018). 
#PraCegoVer : a imagem está dividida em três círculos, em que dois retornam para 
a direita e uma seta para esquerda, finalizando com uma seta reta para a esquerda, 
no q4, e ela está dividida com setas retas, para esquerda e para a direita, que 
fazem a ligação desses círculos. 
PASSOS, Y. T. dos P. Máquinas de Turing. Slideshare , 2018. Disponível 
em: https://www.slideshare.net/yuripassos58/01-maquinas-de-turing. Acesso em: 27 
jun. 2021. 
 
Considerando a imagem apresentada, ilustrada a fim de apresentar o diagrama de 
transição, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F 
para a(s) Falsa(s). 
 
I. ( ) O q0 é o estado inicial e M entra toda vez que retorna ao 0 restante mais à 
esquerda. 
II. ( ) O q1 indica que deve ir à direita enquanto for 0 ou y, troca 1 por y e anda à 
direita para encontrar novos ys. 
III. ( ) O q2 volta para a direita até encontrar o y, andando à direita, enquanto for x 
ou y. 
IV. ( ) O q3 lê ys até encontrar um b à direita. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
Resposta Selecionada: 
V, V, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Resposta correta. A sequência está correta, pois ao finalizar no q4 
o diagrama indica que foi reconhecida a palavra, travando para 
indicar o reconhecimento. Esse diagrama consiste na sucessiva 
aplicação da função programa, a partir do estado inicial e da 
cabeça posicionada na célula mais à esquerda, até ocorrer uma 
parada. 
 
 
Quarta-feira, 22 de Setembro de 2021 09h22min21s BRT