AO2 - Linguagens Formais e Autômatos - 6 de 6

Prévia do material em texto

AO2
Iniciado: 6 jun em 22:04
Instruções do teste

Pergunta 1 0,6 pts

Pergunta 2 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 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:
A normalização é o processo de estruturar um banco de dados relacional de acordo com as formas normais.
A normalização envolve a organização das colunas com as relações, e tabelas com os atributos.
Se temos um modelo na 3ª forma normal, isso significa que ele também atende aos níveis 4 e 5.
A normalização é realizada sempre ao criar um novo design de banco de dados, o que chamamos de decomposição.
Um modelo hipotético de forma normal de nível 2 é mais normalizado que um de nível 4 ou 5.
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
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 1/8

Pergunta 3 0,6 pts
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 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:
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
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 verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
As asserções I e II são proposições falsas.
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:
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
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 2/8

Pergunta 4 0,6 pts
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.
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:
I, II e III.
I e II.
I.
II.
II e III.
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 pilhapode consumir qualquer quantidade de símbolos da cadeia de entrada e da pilha.
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 3/8

Pergunta 5 0,6 pts

Pergunta 6 0,6 pts
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.
Com base nas asserções, assinale a opção correta:
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.
As asserções I e II são proposições falsas.
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.
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).
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:
Compilador.
Estados.
Modelo computacional.
Linguagem formal.
De pilha.
Analise a imagem abaixo:
De acordo com a hierarquia de Chomsky, as gramáticas são divididas em quatro tipos: 
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 4/8

Pergunta 7 0,6 pts
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:
I, II e IV, apenas.
II e IV, apenas.
I e IV, apenas.
I, II e III, apenas.
II e III, apenas.
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.
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 5/8

Pergunta 8 0,6 pts
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:
Listar a natureza dos símbolos.
Criar computadores digitais.
Verificar jogadas de xadrez.
Ser uma máquina abstrata.
Oferecer um sistema formal.
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.
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 possivelmenteinfinitas, todas sobre o mesmo alfabeto.
Com base nas asserções, assinale a opção 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.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
As asserções I e II são proposições falsas.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 6/8

Pergunta 9 0,6 pts

Pergunta 10 0,6 pts
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 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:
I e III, apenas.
I e II, apenas.
II e III, apenas.
II, apenas.
III, apenas.
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.
 
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 7/8
Salvo em 22:16 
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:
Conhecer o tipo de um conjunto é irrelevante para entender as operações de conjunto apropriadas aplicáveis a esse conjunto específico.
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.
Um conjunto sem elementos ou conjuntos vazios também é chamado de conjuntos nulos e é denotado apenas por Φ.
Um conjunto é a representação de uma coleção de objetos, esses são objetos distintos com uma ou mais propriedades comuns.
Enviar teste
A+
A
A-
06/06/2025, 22:17 Teste: AO2
https://famonline.instructure.com/courses/44680/quizzes/214873/take 8/8
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