GRA0823 LINGUAGENS FORMAIS E AUTÔMATOSsemana 4

Prévia do material em texto

08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 1/7
Pergunta 1
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
F, V, F, F.
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 2
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.
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 2/7
Resposta
Selecionada:
 
Resposta
Correta:
 
Comentário
da resposta:
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
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:
“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, 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, 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 4
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 3/7
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 5
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 ao vale 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.
Pergunta 6
Leia o excerto a seguir:
“Uma máquina de Turing é um autômato cuja fita não possui tamanho máximo e
pode ser usada, simultaneamente, como dispositivo de entrada, como
dispositivo de saída e como memória de trabalho. Partindo desse pressuposto,
temos que as linguagens recursivamente enumeráveis ou linguagens tipo 0, por
sua vez, são fundamentais na aplicabilidade da máquina de Turing.
 
MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015.
p. 167.
 
A respeito da teoria das linguagens recursivas e de sua aplicabilidade quanto a
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_14/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
máquina de Turing, analise as afirmativas a seguir e assinale V para a(s)
Verdadeira(s) e F para a(s) Falsa(s).
 
I. ( ) Podemos considerar que, segundo a hipótese de Church, a máquina de
Turing é o dispositivo computacional mais geral.
II. ( ) Algumas classes de linguagens podem representar as linguagens
recursivamente enumeráveis usando um formalismo axiomático.
III. ( ) Uma gramática irrestrita possuirá qualquer restrição quanto à forma das
produções, conforme o modelo de Turing.
IV. ( ) O formalismo gramatical não possui o mesmo poder computacional que o
formalismo da máquina de Turing.
 
Assinale a alternativa que apresenta a sequência correta.
V, V, F, F.
V, V, F, F.
Resposta correta. A sequência está correta. De fato, a hipótese ou modelo de
Church, ao tratar da máquina de Turing, tem ela como o dispositivo computacional
mais geral e algumas classes de linguagens podem receber a designação de
recursivamente enumeráveis, tratando-se, então, de um formalismo axiomático,
essa é a definição científica por trás do formalismo axiomático.
Pergunta 7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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:
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.
1 em 1 pontos
08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 5/7
Pergunta 8
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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.
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 9
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:
1 em 1 pontos
1 em 1 pontos
08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 6/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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: htt
ps://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.
V, V, F, V.
V, V, F, V.
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.
Pergunta 10
Leia o trecho a seguir:
“O teorema da não completude apresenta que todas as formulações axiomáticas
1 em 1 pontos
08/12/2021 17:52 GRA0823 LINGUAGENS FORMAIS E AUTÔMATOS GR1864-212-9 - 202120.ead-17613.01
https://anhembi.blackboard.com/webapps/late-course_engine_soap-BBLEARN/Controller?COURSE_ID=_736312_1 7/7
Resposta Selecionada: 
Resposta Correta: 
Comentário
da resposta:
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 deum 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.