Atividade Objetiva 3 - Linguagens Formais e Autômatos - Nota 0.6 de 1.0

Prévia do material em texto

Atividade 3
Iniciado: 6 mai em 19:31
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 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
 
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:
A+
A
A-
NOTA: 0.6 de 1.0

Pergunta 2 0,2 pts
 
| 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:
G é uma gramática linear se todas as suas produções encontram-se nas duas formas, considerando GLD: A→wB
e A→w.
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.
Na Gramática linear à esquerda, ou GLD, todas as regras de produção são da forma: A→Bw ou A→w.
Na Gramática Linear Unitária à direita, ou GLUE, todas as regras de produção são como na gramática linear à
esquerda.
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.
A+
A
A-
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
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
única 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.
A+
A
A-
https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql

Pergunta 3 0,2 pts
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:
II e IV, apenas.
I, II e IV, apenas.
III e IV, apenas.
I, II e III, apenas.
I e III, apenas.
A+
A
A-
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 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.
A+
A
A-

Pergunta 4 0,2 pts
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
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:
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 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 verdadeiras, mas a II não é uma justificativa da I.
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 eC 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
A+
A
A-
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);
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³).
A+
A
A-
Fonte: MENEZES, P. B. Linguagens Formais e Autômatos: Volume 3. 6. ed. Bookman. 2010. [Minha Biblioteca], p.
168.
 
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.
II e III, apenas.
I e III, apenas.
A+
A
A-

Pergunta 5 0,2 pts
I e II, apenas.
I, 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
 
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.
A+
A
A-
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao/
Salvo em 10:55 
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 Pushdown Automata, ou autômatos de pilha, reconhecem gramáticas de tipo 1.
Os AFN, ou Autômatos Finitos não Determinísticos, reconhecem gramáticas de tipo 0.
As relacionadas às Máquinas de Turing, que reconhecem as gramáticas de tipo 0.
Os Linear Bound Automata, ou Autômatos Limitados Linearmente, reconhecem gramáticas de tipo 3.
Os AF, denominados como Autômatos Finitos, que reconhecem gramáticas de tipo 2.
Enviar teste
A+
A
A-