Atividade Objetiva 3 - Linguagens Formais e Autômatos - Nota 0 6 de 1 0

Prévia do material em texto

Atividade 3
Iniciado: 11 mai em 10:55
Instruções do teste

Pergunta 1 0,2 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.

Leia o texto e observe as tabelas a seguir:
As Formas Normais são uma série de procedimentos aplicados em um banco de dados para garantir
que as suas tabelas estejam bem estruturadas e não contenham nenhum tipo de anomalia, seja de
inclusão, atualização ou exclusão.
O que são anomalias? Anomalias são inconsistências
(https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql) em um banco de dados.
Damos a essa série de procedimentos o nome de Normalização.
Mas antes de dar início à apresentação das formas normais, vamos abordar [...] conceitos necessários
para uma melhor compreensão. Os conceitos que falaremos agora serão:
Dependência Funcional
Dependência Funcional Parcial [...].
Conceito 1: Dependência Funcional
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 1/10
https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql
https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql
https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql
https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql
Uma dependência funcional é um relacionamento entre dois ou mais atributos, de forma que o valor de
um atributo identifica o valor do outro atributo, ou seja, um atributo está relacionado a outro, se nós
sabemos qual o CPF de uma pessoa também vamos descobrir o nome, por exemplo.
Conceito 2: Dependência Funcional Parcial:
Uma dependência funcional parcial ocorre quando os atributos não chave (não identificadores) não
dependam de toda a chave primária quando ela for composta.
Chave primária: Consideramos como chave primária toda coluna da tabela que identifica de forma únic
cada linha da tabela.
No caso deste boletim temos três colunas que a sua composição de valores identifica o aluno de forma
única. Essas colunas são Matrícula_Aluno, Cod_Disciplina e Período.
Perceba também que o nome da disciplina depende somente do código da disciplina, ou seja, depende
de parte da chave primária (dependência funcional parcial) enquanto, a nota, depende da matrícula do
aluno, código da disciplina e do período em que o aluno está matriculado.
Fonte: ARAÚJO, R. O que são formas normais em bancos de dados?. Hashtag, 20 dez. 2022. Disponível em:
https://www.hashtagtreinamentos.com/o-que-sao-formas-normais-em-bancos-de-dados-sql. Acesso em: 05 ago. 2023.
Considerando as informações apresentadas, avalie as afirmações abaixo:
I. Na dependência funcional, o atributo não principal é funcionalmente dependente da chave candidata
II. A dependência funcional equivale ao padrão de normalização da segunda forma normal.
III. A dependência funcional parcial não melhora a qualidade dos dados. Ela deve ser eliminada para
normalizar na segunda forma normal.
IV. Na dependência funcional parcial, o atributo primo é funcionalmente dependente de parte de uma
chave candidata.
É correto o que se afirma em:
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 2/10

Pergunta 2 0,2 pts
I e III, apenas.
I, II e IV, apenas.
III e IV, apenas.
I, II e III, apenas.
II e IV, apenas.
Leia o texto e analise a imagem a seguir:
Noam Chomsky dividiu a gramática em quatro tipos (https://acervolima.com/hierarquia-de-
chomsky-em-teoria-da-computacao/) :
Modelo Nome
0 Gramática Irrestrita
1 Gramática sensível ao contexto
2 Gramática livre de contexto
3 Gramática Regular
 
Hierarquia de Chomsky
 
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 3/10
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao/
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao/
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao/
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao/

Pergunta 3 0,2 pts
1. Gramática livre de contexto:
A linguagem gerada pelo Context Free Grammar é aceita pelo Pushdown Automata.
É um subconjunto da gramática do Tipo 0 e do Tipo 1 e um superconjunto da gramática do Tipo 3.
Também chamada de gramática estruturada em fases.
Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto.
A classificação da Gramática Livre de Contexto é feita com base no número de árvores de análise.
Apenas uma árvore de análise-> Não ambígua.
Mais de uma árvore de análise-> Ambígua.
Fonte: DIFERENÇA entre gramática livre de contexto e gramática regular. Acervo Lima, [s. d]. Disponível em:
https://acervolima.com/diferenca-entre-gramatica-livre-de-contexto-e-gramatica-regular/. Acesso em: 05 ago. 2023.
Considerando o conceito de gramática livre de contexto, assinale a alternativa que relaciona os
tipos de gramática e linguagens que as aceitam corretamente:
Os AFN, ou Autômatos Finitos não Determinísticos, reconhecem gramáticas de tipo 0.
Os Pushdown Automata, ou autômatos de pilha, reconhecem gramáticas de tipo 1.
As relacionadas às Máquinas de Turing, que reconhecem as gramáticas de tipo 0.
Os AF, denominados como Autômatos Finitos, que reconhecem gramáticas de tipo 2.
Os Linear Bound Automata, ou Autômatos Limitados Linearmente, reconhecem gramáticas de tipo 3.
Leia o texto e analise a imagem a seguir:
 
Normalização de dados é o processo formal e passo a passo que examina os atributos de uma
entidade, com o objetivo de evitar anomalias observadas na inclusão, exclusão e alteração de
registros. 
 
O conceito de entidade é muito importante neste processo, ou seja, devemos identificar quais são as
entidades que farão parte do projeto de banco de dados. Entidade é qualquer coisa, pessoa ou objeto
que abstraído do mundo real torna-se uma tabela para armazenamento de dados. Normalmente usa-se
o Modelo de Entidade e Relacionamento para criar o modelo do banco.
Veja um exemplo de várias entidades já normalizadas:
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 4/10
A regra de ouro que devemos observar no projeto de um banco de dados baseado no Modelo
Relacional de Dados é a de "não misturar assuntos em uma mesma Tabela". Por exemplo: na Tabela
Clientes devemos colocar somente campos relacionados com o assunto Clientes. Não devemos
misturar campos relacionados com outros assuntos, tais como Pedidos, Produtos, etc. Essa "Mistura de
Assuntos" em uma mesma tabela acaba por gerar repetição desnecessária dos dados bem como
inconsistência dos dados.
Fonte: O QUE é a normalização de dados e as formas normais 1FN, 2FN e 3FN?. Utilidade Pública, [s.d.]. Disponível em:
https://www.luis.blog.br/normalizacao-de-dados-e-as-formas-normais.html. Acesso em: 05 ago. 2023.
 
Refletindo sobre normalização, avalie as seguintes asserções e a relação proposta entre elas:
I. Se uma tabela não for devidamente normalizada e tiver redundância de dados, ela apenas
consumirá espaço extra de memória. Anomalias de inserção são muito frequentes se o banco de
dados não estiver normalizado.
PORQUE
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 5/10

Pergunta 4 0,2 pts
II. A normalização do banco de dados é uma técnica de organização dos dados. Ela consiste na
decomposição de tabelas para eliminar a repetição de dados e envolve diversas etapas,
resultando em dados no formato de tabelas.
A respeito dessas asserções, assinale a opção correta:
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, mas a II não é uma justificativa da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
A asserção I é uma proposiçãofalsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições falsas.
Leia o texto a seguir:
 
Usando o conceito de gramáticas [...] é possível definir tanto linguagens regulares como linguagens não
regulares. Entretanto, é possível estabelecer restrições nas regras de produção, de tal forma a definir
exatamente a classe das linguagens regulares. Existe mais de uma forma de restringir as regras de
produção de forma a definir uma gramática regular. A seguir, são apresentadas quatro dessas formas,
denominadas gramáticas lineares.
 
Definição 3.23 — Gramáticas lineares
Seja G = (V, T, P, S) uma gramática. Sejam A e B elementos de V e w uma palavra de T*. Então G é
uma gramática linear se todas as suas produções encontram-se em uma e em somente uma das
seguintes formas:
 
a. Gramática linear à direita (abreviada por GLD). Todas as regras de produção são da forma:
 
A→wB ou A→w
 
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 6/10
b. Gramática linear à esquerda (abreviada por GLE). Todas as regras de produção são da forma:
 
A→Bw ou A→w
 
c. Gramática linear unitária à direita (abreviada GLUD). Todas as regras de produção são como na
gramática linear à direita e, adicionalmente:
 
| w | ≤ 1
 
d. Gramática linear unitária à esquerda (abreviada por GLUE). Todas as regras de produção são como
na gramática linear à esquerda e, adicionalmente:
 
| w | ≤ 1
 
Note-se que as gramáticas lineares possuem forte restrição no formato de suas produções:
o lado esquerdo possui exatamente uma variável;
o lado direito de uma produção é constituído por, no máximo, uma variável. Adicionalmente, esta
variável, se existir, sempre antecede (linear à esquerda) ou sucede (linear à direita) qualquer
subpalavra (eventualmente vazia) de terminais [...] (MENEZES, 2010, p. 98).
Fonte: MENEZES, P. B. Linguagens Formais e Autômatos: Volume 3. 6. ed. Bookman. 2010. [Minha Biblioteca].
Considerando as informações apresentadas, assinale a opção correta:
Na Gramática Linear Unitária à direita, ou GLUE, todas as regras de produção são como na gramática linear à
esquerda.
A forma A→wB ou A→w pode ser usada para restringir as regras de produção de forma a definir uma gramática
regular.
As gramáticas lineares apresentadas na definição 3.23 apresentam sutis restrições no formato de suas produções.
G é uma gramática linear se todas as suas produções encontram-se nas duas formas, considerando GLD: A→wB e
A→w.
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 7/10

Pergunta 5 0,2 pts
Na Gramática linear à esquerda, ou GLD, todas as regras de produção são da forma: A→Bw ou A→w.
Leia o texto a seguir:
Uma gramática livre do contexto G = ( V, T, P, S ) é dita estar na Forma normal de Chomsky se todas as
suas produções são da forma (suponha que A, B e C são variáveis de V e a é terminal de T):
A→BC ou A→a
Portanto, a palavra vazia não pertence à linguagem gerada por uma gramática na Forma normal de
Chomsky.
O algoritmo a seguir transforma uma gramática livre do contexto qualquer, cuja linguagem gerada não
possua a palavra vazia, em uma gramática na Forma normal de Chomsky. O algoritmo é dividido em
três etapas, como segue:
1. Etapa 1: simplificação da gramática. Simplifica a gramática, excluindo as produções vazias (como a
linguagem não possui a palavra vazia, todas as produções da forma A→ɛ podem ser excluídas),
produções da forma A→B (se o lado direito de alguma produção tiver somente um símbolo, este
será terminal) e, opcionalmente, os símbolos inúteis;
2. Etapa 2: transformação do lado direito das produções de comprimento maior ou igual a dois.
Garante que o lado direito das produções de comprimento maior ou igual a dois é composto
exclusivamente por variáveis. A exclusão de um terminal a pode ser realizada, substituindo-se este
por uma variável intermediária Cₐ e incluindo a produção Cₐ→a;
3. Etapa 3: transformação do lado direito das produções de comprimento maior ou igual a três, em
produções com exatamente duas variáveis. Garante que o lado direito das produções de
comprimento maior do que um é composto exatamente por duas variáveis. Após a execução da
etapa acima, o lado direito das produções da forma A→B¹B²...ⁿ(n≥2) é composto exclusivamente por
variáveis. Portanto, para concluir a transformação, é suficiente garantir que o lado direito é composto
por exatamente duas variáveis. Isto é possível, gerando-se B¹B²...ⁿ em diversas etapas, e usando-se
variáveis intermediárias.
Definição 6.13 - Algoritmo: forma normal de Chomsky
Seja G = (V, T, P, S) uma gramática livre do contexto tal que ɛ ∉ GERA(G). O algoritmo para transformar
na forma normal de Chomsky é como segue:
Etapa 1: simplificação da gramática. As seguintes simplificações:
produções vazias;
produções que substituem variáveis;
símbolos inúteis (opcional);
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 8/10
devem ser realizadas usando os algoritmos de simplificação descritos anteriormente, resultando na
gramática:
G¹ = (V¹, T¹, P¹, S)
Etapa 2: transformação do lado direito das produções de comprimento maior ou igual a dois. A
gramática resultante desta etapa é:
G² = (V², T¹, P², S)
na qual V² e P² são construídos conforme o algoritmo apresentado na figura 6.17 (para cada variável a,
suponha Cₐ ∉ V²);
Etapa 3: transformação do lado direito das produções de comprimento maior ou igual a três em
produções com exatamente duas variáveis. A gramática resultante desta etapa é:
G³ = (V³, T¹, P³, S)
na qual V³ e P³ são construídos conforme o algoritmo apresentado na figura 6.18 (a cada ciclo, suponha
D¹ ∉ V³,...,Dⁿˉ² ∉ V³).
Fonte: MENEZES, P. B. Linguagens Formais e Autômatos: Volume 3. 6. ed. Bookman. 2010. [Minha Biblioteca], p. 168.
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 9/10
Salvo em 11:26 
 
Considerando o texto e as imagens, analise as afirmações a seguir.
I. Pode haver gramáticas diferentes usando regras diferentes, portanto as transformações servem
para facilitar o projeto de um compilador.
II. Algumas gramáticas livres de contextos podem ser transformadas em uma equivalente na
forma normal de Chomsky por uma sequência de quatro transformações.
III. Cada etapa envolve a remoção de certas produções ou a adição de novas, de modo que o
novo conjunto gere a mesma linguagem que o antigo.
É correto o que se afirma em:
II, apenas.
I, apenas.
II e III, apenas.
I e III, apenas.
I e II, apenas.
Enviar teste
A+
A
A-
5/11/25, 11:26 AM Teste: Atividade 3
https://famonline.instructure.com/courses/44680/quizzes/214834/take 10/10