Baixe o app para aproveitar ainda mais
Prévia do material em texto
20/09/2021 18:47 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: 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. 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 2 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 1 em 1 pontos 1 em 1 pontos 20/09/2021 18:47 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 Resposta Selecionada: Resposta Correta: Comentário da resposta: 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 3 Resposta Selecionada: Resposta Correta: Comentário da resposta: 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. Alan Turing transforma-o em um problema de parada em sua máquina. Alan Turing transforma-o em um problema de parada em sua máquina. 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 4 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. 1 em 1 pontos 1 em 1 pontos 20/09/2021 18:47 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: 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 5 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 1 em 1 pontos 20/09/2021 18:47 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 exatamente as palavras do alfabeto da linguagem, que são parte da linguagem, e rejeita todas as outras palavras. Pergunta 6 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. Pergunta 7 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. 1 em 1 pontos 1 em 1 pontos 20/09/2021 18:47 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: 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 8 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 dos autômatos determinísticos. Expressa a construção de um procedimento computável. Sua resposta está incorreta. A alternativa está incorreta, pois, a partir da definição de máquina de Turing como um formalismo que expressa a construção de um procedimento computável, não se infere que ela se trata de uma expressão de uma linguagem regular, da hierarquia de Chomsky, de um autômato determinístico ou de uma árvore de derivação, tendo em vista que esses conceitos não definem a máquina de Turing. Ela é formalmente definida por um formalismo que expressa a construção de um procedimento computável, porque se trata da definição elementar da teoria da computação, referente a um sistema computacional. Pergunta 9 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. 0 em 1 pontos 1 em 1 pontos 20/09/2021 18:47 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 Resposta Selecionada: Resposta Correta: Comentário da resposta: 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çã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 10 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: htt 1 em 1 pontos 20/09/2021 18:47 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_17/7 Resposta Selecionada: Resposta Correta: Comentário da resposta: 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.
Compartilhar