A4 Linguagens formais e Automatos UAM

Prévia do material em texto

Curso GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-
212-9 - 202120.ead-17613.01 
Teste ATIVIDADE 4 (A4) 
Status Completada 
Resultado da 
tentativa 
4 em 10 pontos 
Resultados 
exibidos 
Respostas enviadas, Respostas corretas, Comentários 
• Pergunta 1 
0 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, e a II é 
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: 
Sua resposta está incorreta. A alternativa está incorreta, 
pois a asserção II não justifica a I. Programa, função 
programa ou função de transição vem após a unidade de 
controle que reflete o estado corrente da máquina, que 
possui uma unidade de leitura e gravação, logo, as 
asserções I e II são corretas, mas a II não é razão ou 
justificativa da I. 
 
 
• Pergunta 2 
1 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: 
II e III, apenas. 
Resposta Correta: 
II e III, apenas. 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois, conforme 
citado no estudo das linguagens livres do contexto, o poder 
computacional do autômato com duas pilhas é o mesmo da 
máquina de Turing, por definição. Dessa forma, temos uma 
nítida equivalência entre ambos. Logo, com um maior 
número de pilhas, não se terá aumento na capacidade 
computacional, o que faz com que as alternativas II e III 
estejam corretas. 
 
 
• Pergunta 3 
0 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, e a II é 
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: 
Sua resposta está incorreta. A alternativa está incorreta, 
pois a asserção II não justifica a I, apesar da análise da 
possibilidade de resolução de problemas ser verdadeira, 
infelizmente, muitos desses problemas não são 
solucionáveis. Informalmente falando, existem muito mais 
problemas não solucionáveis do que solucionáveis, logo, 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 4 
1 em 1 pontos 
 
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. 
 
Resposta 
Selecionada: 
 
Alan Turing transforma-o em um problema de parada 
em sua máquina. 
Resposta Correta: 
Alan Turing transforma-o em um problema de parada 
em sua máquina. 
 
Comentário 
da resposta: 
Resposta correta. A alternativa está correta, pois a 
definição do problema de decisão se dá por meio de 
matemáticos que o definem como um sistema formal. 
Pretendia-se obter uma teoria aritmética como um 
sistema formal consistente e completo, o que, 
infelizmente, não foi possível, segundo David Hilbert. 
 
• Pergunta 5 
0 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, F, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Sua resposta está incorreta. A sequência está incorreta, 
pois a afirmativa III é falsa, porque, para definir 
 
formalmente o comportamento dessa transição, é 
necessário entender a definição da função programa e 
usar como argumento um estado e uma palavra, logo, o 
q2 não volta para a direita até encontrar o y, andando à 
direita, enquanto for x ou y. 
 
• Pergunta 6 
1 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: 
F, V, F, F. 
Resposta Correta: 
F, V, F, F. 
Comentário 
da resposta: 
Resposta correta. A sequência está correta, porque, em 
termos de capacidade de expressar computabilidade, que 
é conhecido como tese de Church ou tese de Turing-
Church, os trabalhos elaborados são um forte reforço 
nesse sentido, e a capacidade de computação 
representada pela máquina de Turing é o limite máximo 
que pode ser atingido. 
 
 
• Pergunta 7 
0 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: 
 
As asserções I e II são proposições verdadeiras, mas a 
II não é uma justificativa correta da I. 
Resposta 
Correta: 
 
A asserção I é uma proposição verdadeira, e a asserção 
II é uma proposição falsa. 
Comentário 
da resposta: 
Sua resposta está incorreta. 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 8 
1 em 1 pontos 
 
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. 
Resposta Selecionada: 
F, V, F, F. 
Resposta Correta: 
F, V, F, F. 
Comentário 
da resposta: 
Resposta correta. A sequência está correta, pois sabe-se 
que é chamada de recursiva se é um subconjunto 
recursivo no conjunto de todas as palavras possíveis sobre 
o alfabeto da linguagem. Logo, uma linguagem é uma 
classe recursiva se existe uma máquina de Turing que 
sempre para 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. 
 
 
• Pergunta 9 
0 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: 
II, III e IV, apenas. 
Resposta Correta: 
I e II, apenas. 
Comentário 
da resposta: 
Sua resposta está incorreta. A alternativa está incorreta, 
pois as alternativa III e IV indicam que o teorema da 
completude conceitua regras de inferência da lógica de 
primeira ordem completas, no sentido de que nenhuma 
nova regra de inferência é necessária para derivar todas 
as fórmulas logicamente válidas, o que não é correto, na 
realidade, o que ocorre é o inverso. 
 
 
• Pergunta 10 
0 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, F, F, V. 
Resposta Correta: 
V, V, F, V. 
Comentário 
da resposta: 
Sua resposta está incorreta. A sequência está incorreta, 
pois a afirmativa III é falsa. Para a máquina de Turing, uma 
das características de um algoritmo processável é ter uma 
descrição finita e executável, e não infinita e executável, 
uma vez que, se ela fosse infinita, teríamos um loop sem 
solução, logo, somente a alternativa III apresenta erro ao 
definir uma descrição infinita.