Atividade 4 - Linguagens Formais E Autômatos

Prévia do material em texto

20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 1/7
Pergunta 1
Resposta
Selecionada:
Resposta
Correta:
Comentário
da resposta:
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.
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.
Resposta correta. A alternativa está correta, pois, quando for encontrada alguma
representação satisfatória no resultado, encontra-se a resposta desejada, e a
pessoa finalizará seus cálculos, e isso viabilizará esse procedimento, por isso,
essas hipóteses são aceitáveis.
Pergunta 2
Resposta
Selecionada:
Resposta
Correta:
Comentário
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
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 verdadeiras, mas a II não é uma
justificativa correta da I.
Resposta correta. A alternativa está correta, pois a asserção I é verdadeira, já a
1 em 1 pontos
1 em 1 pontos
20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 2/7
da resposta: 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 3
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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:
I e II, apenas.
I e II, apenas.
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 4
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.
 
1 em 1 pontos
1 em 1 pontos
20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 3/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
F, V, F, F.
F, V, F, F.
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 5
Resposta
Selecionada:
Resposta Correta:
Comentário
da resposta:
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.
A asserção I é uma proposição verdadeira, e a asserção II é uma
proposição falsa.
A asserção I é uma proposição verdadeira, e a asserção II é uma
proposição falsa.
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çãoII é uma proposição falsa,
porque um problema computável pode ser um problema parcialmente
1 em 1 pontos
20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 4/7
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 6
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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 Fpara 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.
V, V, F, V.
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 7
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
1 em 1 pontos
1 em 1 pontos
20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 5/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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:
II e III, apenas.
II e III, apenas.
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 8
Resposta Selecionada:
 
Resposta Correta: 
Comentário
da resposta:
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.
F, V, F, V. 
 
V, V, F, V.
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.
0 em 1 pontos
20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 6/7
Pergunta 9
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
I e II, apenas.
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 10
Resposta Selecionada: 
Resposta Correta:
Comentário
da resposta:
A ciência da computação trata da evolução do conhecimento matemático
desenvolvido ao longo da história humana, desde a Mesopotâmia, passando
pela Grécia, até chegar aovale do silício, e boa parte dessa evolução ocorreu
em 1936, com o formalismo desenvolvido por Alan Turing, que depois passou a
ser a famosa máquina de Turing.
 
Assinale a alternativa que indica a definição de máquina de Turing.
Expressa a construção de um procedimento computável.
Expressa a construção de um procedimento computável.
Resposta correta. A alternativa está correta, pois a definição dada à máquina de
Turing é bem simples, ela é um formalismo que expressa a construção de um
procedimento computável, essa é a definição formal de uma máquina de Turing. O
resultado desse formalismo foi a fundamentação teórica para o desenvolvimento
do computador.
1 em 1 pontos
1 em 1 pontos
20/09/2021 19:37 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-29780731.06
https://fmu.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_738194_1 7/7