AO2_ Linguagens Formais e Autômatos

Prévia do material em texto

AO2
Entrega 7 de dez de 2023 em 23:59
Pontos 6
Perguntas 10
Disponível 28 de nov de 2023 em 0:00 - 7 de dez de 2023 em 23:59
Limite de tempo Nenhum
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 13 minutos 5,4 de 6
Pontuação deste teste: 5,4 de 6
Enviado 5 de dez de 2023 em 22:04
Esta tentativa levou 13 minutos.

Pergunta 1
0,6 / 0,6 pts
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
Analise as informações a seguir:
Uma gramática regular pode ser "esquerda" ou "direita".
Uma gramática esquerda regular é um conjunto de regras da forma:
onde, são símbolos não terminais e um símbolo terminal. 
Uma gramática correta regular é um conjunto de regras da forma:
https://famonline.instructure.com/courses/31552/quizzes/158026/history?version=1
onde, são símbolos não terminais e um símbolo terminal. Além disso, como para todas as
gramáticas, consideramos um determinado não terminal chamado axioma e anotamos. 
Exemplo
A gramática a seguir é uma gramática correta regular:
Com a gramática anterior, podemos gerar a palavra. De fato: 
Equivalência entre autômatos finitos e gramáticas regulares
Podemos efetivamente transformar uma gramática regular correta em um autômato finito
determinístico e vice-versa. Os não terminais correspondem aos estados do PLC.
Exemplo
Considere a gramática acima. O autômato correspondente é o seguinte:
A sequência de derivações corresponde à leitura da palavra no autômato onde se passa
sucessivamente nos estados: S, A, S, A, S, C, S.
 I e II.
Correto!
 I, II e III.
 II.
 I.
 II e III.
A alternativa está correta. É correto apenas o que se afirma em I, II e III.
A afirmação I está correta, pois uma linguagem regular pode ser expressa usando um autômato finito
determinístico ou não determinístico, uma expressão regular ou uma gramática regular. Uma
gramática regular é aquela que é linear à direita ou linear à esquerda.
A afirmação II está correta, pois gramáticas regulares são outra maneira de descrever linguagens
regulares. Uma gramática é composta por terminais, variáveis e regra de produção. Como o nome
indica, uma gramática regular é um tipo especial de gramática.
A afirmação III está correta, pois para qualquer linguagem existe uma gramática regular que a
descreve. Gramáticas regulares representam exatamente o conjunto de linguagens regulares para
mostrar que podemos converter qualquer autômato finito não determinístico em uma gramática
regular.

Pergunta 2
0,6 / 0,6 pts
Fonte: GRAMÁTICA regular. Frwiki, [s.d.]. Disponível em:
https://pt.frwiki.wiki/wiki/Grammaire_r%C3%A9guli%C3%A8re. Acesso em: 10 mar. 2023.
Considerando os aspectos relacionados às gramáticas regulares, avalie as afirmações abaixo:
I. Uma linguagem regular pode ser expressa usando um autômato finito determinístico ou não
determinístico, uma expressão regular ou uma gramática regular.
II. Gramáticas regulares é outra maneira de descrever linguagens regulares. Uma gramática é
composta por terminais, variáveis e regra de produção.
III. Gramáticas regulares representam exatamente o conjunto de linguagens regulares para
mostrar que podemos converter qualquer autômato finito não determinístico em uma gramática
regular.
É correto, apenas, o que se afirma em:
Analise a imagem abaixo:
De acordo com a hierarquia de Chomsky, as gramáticas são divididas em quatro tipos: 
 I e IV, apenas.
Correto!
 I, II e III, apenas.
 II e IV, apenas.
 II e III, apenas.
 I, II e IV, apenas.
A alternativa está correta. É correto o que se afirma em I, II e III, apenas.
A afirmação I está correta, pois as linguagens gramaticais do tipo 0 são reconhecidas pela Máquina
de Turing. Essas linguagens também são conhecidas como linguagens recursivamente enumeráveis.
Não há restrição nas regras gramaticais desses tipos de linguagens. A gramática do tipo 0 também é
conhecida como gramática irrestrita.
A afirmação II está correta, pois as gramáticas do tipo 3 geram linguagens regulares. Linguagens
regulares são aquelas linguagens que podem ser descritas usando expressões regulares. Essas
linguagens podem ser modeladas por AFN ou AFD.
A afirmação III está correta, pois as gramáticas do tipo 2 geram linguagens livres de contexto. A
linguagem gerada pela gramática é reconhecida por um autômato de pilha. Já a gramática do tipo 1
é conhecida como gramática sensível ao contexto e é usada para representar a linguagem sensível
ao contexto.
A afirmação IV está incorreta, pois são as gramáticas do tipo 3 as formas mais restritas de
gramática. As gramáticas do tipo 1 geram linguagens sensíveis ao contexto. Além disso, é a
gramática do tipo 0 que é conhecida como gramática irrestrita.

Fonte: HIERARQUIA de Chomsky em teoria da computação. Acervo Lima, [s. d.] Disponível em:
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao-1/. Acesso em: 21 mar. 2023.
Considerando o texto sobre a hierarquia de Chomsky, avalie as afirmações abaixo:
I. As linguagens gramaticais do tipo 0 são reconhecidas pela Máquina de Turing, pois não há
restrição nas regras gramaticais desses tipos de linguagens.
II. As gramáticas do tipo 3 geram linguagens regulares, que são aquelas linguagens que
podem ser descritas usando expressões regulares. 
III. As gramáticas do tipo 2 geram linguagens livres de contexto e a gramática do tipo 1 é
conhecida como gramática sensível ao contexto.
IV. As do tipo 1 são a forma mais restrita de gramática, pois as gramáticas do tipo 1 são
conhecidas como gramáticas irrestritas.
É correto o que se afirma em:
Pergunta 3
0,6 / 0,6 pts
 
A normalização é realizada sempre ao criar um novo design de banco de dados, o que chamamos de
decomposição.
 A normalização envolve a organização das colunas com as relações, e tabelas com os atributos.
Analise o texto abaixo sobre normalização e formas normais:
[...] Uma forma normal, no contexto de bancos de dados, refere-se à uma diretriz, uma convenção
com o objetivo de prevenir anomalias e inconsistências em meio às atualizações frequentes que uma
base irá sofrer, minimizando a redundância ao preço de uma menor eficiência entre consultas [...]. 
A normalização é um fator que toma como pressuposto que a base sofrerá constantes atualizações.
Se trata-se de uma base estática e muito consultada, não há fortes motivos para se normalizar.
Primeira Forma Normal
A Primeira Forma Normal (ou 1FN) refere-se ao formato de um registro. Esta diretriz exclui a
possibilidade de haver campos que possuem mais de um atributo, ou seja, um vetor ou grupo de
atributos [...].
Segunda Forma Normal
Esta forma normal refere-se ao relacionamento entre atributos dentro de uma determinada tabela,
mais especificamente entre atributos chave e não-chave, tomaremos daqui em diante “chave” como
chave primária, não considerando chaves estrangeiras [...].
Terceira Forma Normal
A Terceira Forma Normal (3FN) é bastante semelhante a segunda e também se refere a chaves.
Além disso, ela também requer que antes a Primeira Forma Normal seja satisfeita. Esta diretriz é
violada quando um atributo não chave refere-se a outro atributo que também não é chave dentro de
uma tabela [...].
Quarta Forma Normal
Até este ponto nosso banco de dados já está bastante organizado e eliminamos diversos débitos
técnicos que poderiam nos gerar dores de cabeça. Porém ainda podemos ir mais longe [...].
Quinta Forma Normal
Por fim, a Quinta Forma Normal. Direto ao ponto, para que um esquema se enquadre nesta diretriz,
primeiramente ele deve estar em todas as formas normais vistas anteriormente e, se estiver na 4FN,
muito provavelmente estará também na quinta [...].
Fonte: ROSA, L. G. F. As cinco formas normais e porque você deve utilizá-las. Medium, 22 set. 2017. Disponível em:
https://medium.com/@luizguilhermefr/cinco-formas-normais-8f238bc30189. Acesso em:14 mar. 2023.
Considerando as informações apresentadas acima, assinale a opção correta sobre
normalização e formas normais:
 Se temos um modelo na 3ª forma normal, isso significa que ele também atende aos níveis 4 e 5.
Correto!
 A normalização é o processo de estruturar um banco de dados relacional de acordo com as formas normais.
 Um modelo hipotético de forma normal de nível 2 é mais normalizado que um de nível 4 ou 5.
Esta alternativa está correta, pois a normalização é o processo de estruturar um banco de dados
relacional de acordo com as formas normais, a fim de reduzir a redundância de dados e melhorar a
integridade deles.

Pergunta 4
0,6 / 0,6 pts
Correto!
 Ser uma máquina abstrata.
 Verificar jogadas de xadrez.
Veja as informações abaixo:
A máquina de Turing não se destina a ser uma tecnologia de computação funcional; em vez disso,
pretende ser uma máquina hipotética que representa uma máquina de computação. A máquina de
Turing pode ajudar os cientistas da computação a compreender os limites da computação mecânica.
As máquinas de Turing modelam matematicamente um dispositivo que é executado mecanicamente
usando uma fita. Esta fita inclui símbolos, que a máquina pode escrever e ler, um após o outro, com
a ajuda de uma cabeça de fita.
Mais especificamente, uma máquina de Turing inclui o seguinte:
Fita: Uma fita que é dividida em células, uma ao lado da outra. Cada célula inclui um símbolo de
um determinado alfabeto finito. O alfabeto inclui um símbolo em branco exclusivo, bem como um
ou mais outros símbolos. O volume de fita necessário para o cálculo é sempre incluído na
máquina de Turing.
Cabeça: Uma cabeça capaz de escrever e ler símbolos na fita. Em alguns modelos, a cabeça se
move enquanto a fita está fixada.
Registro de estado: um registro de estado para armazenar o estado da máquina de Turing. Há
um estado inicial especial através do qual o registro de estado é inicializado.
Tabela finita: uma tabela finita (às vezes chamada de função de transição ou tabela de ação) de
instruções, que geralmente são quíntuplos, mas ocasionalmente quádruplos.
 
Fonte: O QUE é uma máquina de turing? Theastrology Page, 2023. Disponível em:
https://pt.theastrologypage.com/turing-machine. Acesso em: 21 mar. 2023.
 
Assinale a alternativa que representa o principal objetivo das máquinas de Turing:
 Oferecer um sistema formal.
 Listar a natureza dos símbolos.
 Criar computadores digitais.
Alternativa correta. As Máquinas de Turing encontram aplicações em teoria da informação
algorítmica e estudos de complexidade, teste de software, computação de alto desempenho,
aprendizado de máquina, engenharia de software, redes de computadores e cálculos evolutivos.
Portanto, seu principal objetivo está na aplicação hipotética e não na funcional.

Pergunta 5
0,6 / 0,6 pts
Analise as informações abaixo:
Definição formal
Um autômato de pilha é formalmente definido por uma 6-upla:
Onde:
• é um conjunto finito de estados.
• é um conjunto finito de símbolos, denominado alfabeto de entrada.
• é um conjunto finito de símbolos, denominado alfabeto da pilha.
• é a relação de transição.
• é o estado inicial.
• é o conjunto de estados finais (ou de aceitação).
Um elemento (p,a,α,q,β) é uma transição de M. Ela significa que M, estando no estado p, com o
símbolo a na cadeia de entrada e com o símbolo α no topo da pilha, pode consumir o símbolo a,
transitar para o estado q e desempilhar α substituindo-o por β.O ∑* e o Γ* denotam o fecho de
Kleene do alfabeto de entrada e da pilha, respectivamente. Portanto, estes componentes são
utilizados para formalizar que o autômato de pilha pode consumir qualquer quantidade de símbolos
da cadeia de entrada e da pilha.
Fonte: AUTÔMATO de pilha. In: Dicionário Sensagent. On-line, 2022. Disponível em:
http://dicionario.sensagent.com/Aut%C3%B4mato%20de%20pilha/pt-pt/. Acesso em: 09 mar. 2023.
Com base nas informações sobre os autômatos de pilha, avalie as seguintes asserções e a relação
proposta entre elas.
I. Um autômato pushdown, ou autômato de pilha, é uma máquina de estado infinito que possui
um armazenamento de pilha adicional.
PORQUE
II. Um autômato de pilha é um autômato com estados infinitos que também pode usar uma
pilha limitada de memória.
 As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
Correto!
 As asserções I e II são proposições falsas.
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A alternativa está correta. As asserções I e II são proposições falsas.
A asserção I é falsa, pois um autômato pushdown, ou autômato de pilha, é uma máquina de estado
finito que possui um armazenamento de pilha adicional. As transições que uma máquina faz são
baseadas não apenas na entrada e no estado atual, mas também na pilha.
A asserção II é falsa, pois um autômato de pilha é um autômato com muitos estados finitos que
também pode usar uma pilha ilimitada de memória. O autômato só pode empurrar, estourar ou ler o
topo da pilha.

Pergunta 6
0 / 0,6 pts
Com base nas asserções, assinale a opção correta:
Leia o texto:
Impacto no tempo de computação
O conceito de máquina de Turing não determinística não estende a noção de computabilidade.
Portanto, as máquinas de Turing não determinísticas computam exatamente as mesmas funções
que as máquinas de Turing determinísticas, porque uma máquina de Turing não determinística pode
ser simulada por uma máquina de Turing determinística. No entanto, a complexidade dos cálculos
difere: a classe de complexidade polinomial associada a eles é a classe de complexidade NP, que
contém a classe correspondente para máquinas de Turing determinísticas. É por isso que uma
denominação desta classe, a saber NP, vem de seu nome e significa N em olinômio P determinístico,
ou seja, classe de problemas que podem ser resolvidos em um tempo polinomial por máquinas de
Turing não determinísticas. Note que não sabemos se esta classe NP é ou não igual à classe P de
problemas que podem ser resolvidos em um tempo polinomial por máquinas de Turing
determinísticas: este é o famoso problema P = NP.
Fonte: MÁQUINA de Turing não determinística. Frwiki, [s.d]. Disponível em:
https://pt.frwiki.wiki/wiki/Machine_de_Turing_non_d%C3%A9terministe. Acesso em: 13 fev. 2023.
Com base nas informações sobre a máquina de Turing não determinística, avalie as seguintes
asserções e a relação proposta entre elas.
I. Uma máquina de Turing não determinística é uma generalização de uma máquina de Turing
determinística padrão, em que passamos de uma sequência de etapas de computação
Você respondeu
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 As asserções I e II são proposições falsas.
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
Resposta correta
 As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A alternativa está incorreta. As asserções I e II são proposições verdadeiras, mas a II não é uma
justificativa da I.
A asserção I é verdadeira, pois uma máquina de Turing não determinística é uma generalização de
uma máquina de Turing determinística padrão, em que passamos de uma sequência de etapas de
computação determinada para várias sequências possíveis. O processo de computação de uma
máquina de Turing não determinística é interpretado como uma máquina de Turing determinística
com a capacidade de criar e iniciar outras máquinas de Turing processando ramificações alternativas
do cálculo.
A asserção II é verdadeira, pois reduzir a quantidade de trabalho computacional do paradigma
determinístico permite que as máquinas de processamento não determinísticas abram caminho para
a computação artificialmente inteligente, por meio daqual os computadores aprendem a resolver
problemas complexos e a pensar mais como humanos. Logo, a II não justifica a I, ainda que seja
verdadeira.

Pergunta 7
0,6 / 0,6 pts
determinada para várias sequências possíveis.
PORQUE
II. Reduzir a quantidade de trabalho computacional do paradigma determinístico permite que as
máquinas de processamento não determinísticas abram caminho para a computação
artificialmente inteligente.
Com base nas asserções, assinale a opção correta:
Leia o texto abaixo:
Conjuntos
Um conjunto é uma coleção de símbolos, também denominados átomos ou elementos, em que não
são consideradas ocorrências múltiplas dos mesmos nem há relação de ordem entre eles.
Exemplo 1.1 A inclusão do símbolo ♦ no conjunto {♣,♦,♥,♠} resulta no próprio conjunto{♣,♦,♥,♠}, pois
o mesmo já faz parte do conjunto e, portanto, não deve ser considerado novamente. Por outro lado,
o conjunto {♣,♦,♥,♠} é igual ao conjunto {♦,♣,♠,♥}, uma vez que não existe relação de ordem entre os
elementos que os compõem.
Um símbolo corresponde a uma representação gráfica única e indivisível. Se formado por
caracteres, um símbolo pode ser composto por um número arbitrário deles.
 
Exemplo 1.2 São exemplos de símbolos: “a”, “abc”, “♠”, “1” etc.
Alguns conjuntos podem ser especificados através da simples enumeração de todos os seus
elementos, denotados entre chaves e separados por vírgulas.
 
Exemplo 1.3 O conjunto formado pelos elementos 0, 1, 2, 3 é representado por {0, 1, 2, 3}. O
conjunto {a, b, c, d, e, f } é formado pelas seis primeiras letras do alfabeto romano. O conjunto {01,
231, 33, 21323} contém os elementos 01, 231, 33 e 21323.
Conjuntos podem ser referenciados através de nomes, arbitrariamente escolhidos.
 
Exemplo 1.4 X = {0, 1, 2, 3}, Y = {a, b, c, d, e, f }. Assim, os nomes X e Y passam a denotar os
conjuntos correspondentes. 2
O número de elementos contido em um conjunto A é denotado por |A|.
 
Exemplo 1.5 No exemplo 1.4, |X| = 4, |Y| = 6. 2
Os símbolos ∈ e 6∈ servem para denotar se um determinado elemento pertence ou não pertence a
um conjunto, respectivamente.
 
Exemplo 1.6 No exemplo 1.4, 0 ∈ X, 5 6∈ X, 2 6∈ Y , b 6∈ X, c ∈ Y, h 6∈ Y.
Conjuntos podem conter um número finito ou infinito de elementos. No primeiro caso, o conjunto
pode ser denotado enumerando-se (relacionando-se explicitamente) todos os elementos que o
compõem, como foi feito para os conjuntos X e Y do exemplo 1.4, que são conjuntos finitos.
Fonte: INTRODUÇÃO às Linguagens Formais e Autômatos/Fundamentos Matemáticos. Wikiversidade, [s. d.].
Disponível em: https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%A
(https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A)
0s_Linguagens_Formais_e_Aut%C3%B4matos/Fundamentos_Matem%C3%A1ticos. Acesso em: 08 mar. 2023.
Considerando as informações sobre conjuntos em linguagens formais, assinale a opção
correta:
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
https://pt.wikiversity.org/wiki/Introdu%C3%A7%C3%A3o_%C3%25A
 
Um conjunto é geralmente representado por letras minúsculas e um elemento do conjunto por letras maiúsculas.
 
Agrupar os objetos em um conjunto é um ato de unir esses objetos com os membros ou elementos de outro
conjunto.
Correto!
 
Um conjunto é a representação de uma coleção de objetos, esses são objetos distintos com uma ou mais
propriedades comuns.
 
Um conjunto sem elementos ou conjuntos vazios também é chamado de conjuntos nulos e é denotado apenas por
Φ.
 
Conhecer o tipo de um conjunto é irrelevante para entender as operações de conjunto apropriadas aplicáveis a
esse conjunto específico.
Esta alternativa está correta, pois um conjunto é a representação de uma coleção de objetos. Esses
são objetos distintos com uma ou mais propriedades comuns. Podemos usar os termos elementos
ou membros de um conjunto em vez do termo objetos.

Pergunta 8
0,6 / 0,6 pts
Leia o texto a seguir:
[...] Autômato finito é um sistema de estados finitos (portanto possui um número finito e predefinido
de estados) o qual constitui um modelo computacional do tipo sequencial muito comum em diversos
estudos teórico-formais da computação e informática, com destaque para linguagens formais,
compiladores, semântica formal e modelos para concorrência. Trata-se de um formalismo
operacional ou reconhecedor, o qual pode ser: 
• determinístico: para o estado corrente e o símbolo lido da entrada, o sistema assume um
único estado bem determinado; 
• não determinístico: para o estado corrente e o símbolo lido da entrada, o sistema assume
um estado Pertencente a um conjunto de estados alternativos: 
• com movimentos vazios: para o estado corrente e, independentemente de ler um símbolo
ou não da entrada, o sistema assume um estado pertencente a um conjunto de estados
alternativos (portanto é não determinístico). O movimento é dito movimento vazio se o sistema
muda de estado sem uma correspondente leitura de símbolo. Movimentos vazios podem ser
vistos como transições encapsuladas nas quais, excetuando-se por uma eventual mudança de
estado, nada mais pode ser observado, de forma análoga à noção de encapsulação das
linguagens orientadas a objetos. 
Prova-se que os três tipos de autômatos acima são equivalentes em termos de poder computacional
[...](MENEZES, 2010, p. 69).
 Compilador.
 Linguagem formal.
Correto!
 De pilha.
 Modelo computacional.
 Estados.
Alternativa correta, pois os autômatos podem ser determinísticos, não determinísticos, com
movimentos vazios e de pilha.

Pergunta 9
0,6 / 0,6 pts
Fonte: MENEZES, P. B. Linguagens Formais e Autômatos: Volume 3. 6. ed. Bookman. 2010. [Minha Biblioteca].
Com base nos conceitos sobre autômatos, assinale a alternativa que apresenta um de seus
tipos:
Leia o trecho a seguir:
Teoria das Linguagens Formais e dos autômatos é o estudo de modelos matemáticos que
possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas
classificações, estruturas, propriedades, características e inter-relacionamentos.
Uma linguagem formal é um conjunto de palavras, isto é, um conjunto finito de letras ou símbolos
com um conjunto de regras para combinar estes elementos. O inventário destas letras é chamado de
alfabeto na qual esta linguagem é definida. O modo formal como uma linguagem é definida é
chamada de gramática formal.
Assim, podemos dizer que "Linguagens formais" são mecanismos formais para representação e
especificação de linguagens, baseados na chamada "Teoria da Computação". As representações
podem ser feitas por reconhecedores e geradores. Os reconhecedores são dispositivos formais que
servem para verificar se uma sentença pertence ou não à determinada linguagem. São os
autômatos: autômatos finitos, autômatos de pilha e Máquina de Turing. Os sistemas geradores são
dispositivos formais que permitem a geração sistemática de todas as sentenças de uma linguagem.
Os principais sistemas geradores disponíveis são as gramáticas, onde se destacam as gramáticas
de Chomsky. Então, linguagens formais podem ser representadas de maneira finita e precisa através
de sistemas com sustentação matemática.
Fonte: CONSTRUÇÃO de compiladores/Teoria das linguagens formais. Wikilivros, [s.d.]. Disponível em:
https://pt.wikibooks.org/wiki/Constru%C3%A7%C3%A3o_de_
compiladores/Teoria_das_linguagens_formais. Acesso em: 08 mar. 2023.
Com base nas informações sobre a teoria das Linguagens Formais, avalie as seguintes asserções e
a relação proposta entre elas.
 As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
Correto!
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 As asserções I e II são proposições falsas.
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
A alternativa estácorreta. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é verdadeira. Um alfabeto consiste em um grupo finito de símbolos. Nesses casos,
cada símbolo consiste em um bloco de construção principal, que é normalmente um dígito ou um
caractere.
A asserção II é falsa. Uma string, ou cadeia de caracteres, consiste em uma sequência finita de
símbolos do alfabeto, e não infinita como afirma a asserção. Uma linguagem formal é normalmente
um conjunto de cadeias de caracteres que presumivelmente são infinitas, e todas elas são sobre o
mesmo alfabeto.

Pergunta 10
0,6 / 0,6 pts
I. Um símbolo é o nosso bloco de construção básico nas linguagens formais, geralmente um
caractere ou um dígito, pois um alfabeto é um conjunto finito de símbolos.
PORQUE
II. Uma string é uma sequência infinita de símbolos do alfabeto, pois uma linguagem formal é
um conjunto de strings possivelmente infinitas, todas sobre o mesmo alfabeto.
Com base nas asserções, assinale a opção correta:
Leia o texto a seguir:
[...] A beleza do trabalho de Turing foi ter definido com rigor matemático o que é um programa, na
forma da máquina de Turing, configurado como transições entre estados finitos. E o conceito de uma
máquina universal que consegue executar quaisquer máquinas de Turing, que é o que ele chama de
máquina de Turing Universal e na prática chamamos isso de computador. Uma máquina Universal
de Turing é uma máquina de Turing cuja tarefa é simular outra máquina de Turing arbitrária, com
uma entrada de dados arbitrária.
O que chamamos de computador moderno tem uma característica muito importante: ela consegue
carregar e armazenar configurações, ou o que chamamos de programas. Essa é uma distinção que
eu considero importante. Recentemente me perguntaram isso: o que diferencia um ábaco ou uma
calculadora mecânica de um "computador" de verdade? A definição é se ela é ou não é uma
máquina universal de Turing, particularmente com a característica de não distinção entre programa e
 III, apenas.
 I e III, apenas.
 I e II, apenas.
 II, apenas.
Correto!
 II e III, apenas.
A alternativa está correta. É correto o que se afirma em II e III, apenas.
A afirmação I está incorreta, pois uma máquina Universal simularia a máquina observando a entrada
na fita e o estado da máquina. O que determina como o conteúdo da fita muda é uma máquina de
estado finito (também chamada de autômato finito) dentro da máquina de Turing. A máquina de
estado finito é determinada pelo número de estados que possui e pelas transições entre eles.
A afirmação II está correta, pois o modelo da máquina de Turing consiste em uma entrada e uma
saída. A entrada é fornecida em formato binário na fita da máquina e a saída consiste no conteúdo
da fita quando a máquina para. O problema com as Máquinas de Turing é que uma diferente deve
dados no armazenamento, na tal fita infinita, o que permite a universalidade dele poder simular outra
máquina de Turing.
Antes de Turing existem diversos experimentos que alguns chamam de "computador" mas que na
realidade seria mais correto chamar de máquinas de calcular grandes. E aqui eu vou usar trechos do
artigo "Quem Inventou o Computador" do site do próprio autor da biografia do Turing, o Andrew
Hodges. Ele diz, e eu concordo, por exemplo, que não podemos chamar o Engenho Analítico de
Charles Babbage de computador. Ele não incorpora a ideia vital de armazenar programas da mesma
forma que os dados [...].
Fonte: AKITA, F. O Computador de Turing e Von Neumann: Por que calculadoras não são computadores?. AkitaOnRails,
23 out. 2020. Disponível em: https://www.akitaonrails.com/2020/10/23/akitando-86-o-computador-de-turing-e-von-
neumann-por-que-calculadoras-nao-sao-computadores. Acesso em: 09 mar. 2023.
Com base no trecho sobre as máquinas de Turing universais, avalie as afirmações abaixo:
I. Uma máquina Universal simularia a máquina observando a saída na fita e o estado da
máquina, pois o que determina como o conteúdo da fita muda é uma máquina de estado não
finito dentro da máquina de Turing.
II. O modelo da máquina de Turing consiste em uma entrada e uma saída, e o principal
problema com elas é que uma diferente deve ser construída para cada nova computação a ser
realizada.
III. A máquina de Turing (TM, em inglês) é o nível de máquina equivalente a um computador
digital.
É correto o que se afirma em:
ser construída para cada nova computação e cálculo a ser realizado, para cada relação de entrada e
saída.
A afirmação III está correta, pois a máquina de Turing (TM em inglês) é o nível de máquina
equivalente a um computador digital. Foi sugerida por Turing no ano de 1930 e tornou-se o modelo
de computação mais utilizado na teoria da computação e da complexidade. A cada passo da
máquina de Turing, o estado atual e o caractere lido na fita determinam o próximo estado em que a
máquina de estado finito estará, o caractere que a máquina produzirá na fita e em qual direção a
cabeça se move, esquerda ou direita.
Pontuação do teste: 5,4 de 6