LINGUAGENS FORMAIS E AUTÔMATOS - ATIVIDADE 04

Prévia do material em texto

• Pergunta 1 
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 2 
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 3 
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 4 
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 5 
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 foiassumida 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 6 
1 em 1 pontos 
 
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 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. 
Resposta Selecionada: 
V, V, F, F. 
Resposta Correta: 
V, V, F, F. 
Comentário 
da resposta: 
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 
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 8 
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. 
 
 
• Pergunta 9 
1 em 1 pontos 
 
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. 
 
Resposta 
Selecionada: 
 
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 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. 
Comentário 
da resposta: 
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 10 
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.