Atividade 3 Linguagens Formais e Automatos

Prévia do material em texto

12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 1 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
Atividade 3
Entrega 26 mai em 23:59
Pontos 1
Perguntas 5
Disponível 12 fev em 0:00 - 26 mai em 23:59
Limite de tempo Nenhum
Tentativas permitidas 2
Instruções
Este teste foi travado 26 mai em 23:59.
Histórico de tentativas
Tentativa Tempo Pontuação
MANTIDO Tentativa 1 16 minutos 0,6 de 1
MAIS RECENTE Tentativa 2 4 minutos 0,2 de 1
Tentativa 1 16 minutos 0,6 de 1
Pontuação desta tentativa: 0,2 de 1
Enviado 26 abr em 15:02
Esta tentativa levou 4 minutos.
 
Pergunta 1
0,2 / 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 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
https://famonline.instructure.com/courses/35817/quizzes/177232/history?version=1
https://famonline.instructure.com/courses/35817/quizzes/177232/history?version=2
https://famonline.instructure.com/courses/35817/quizzes/177232/history?version=1
https://acervolima.com/hierarquia-de-chomsky-em-teoria-da-computacao/
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 2 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
Correto!
 As relacionadas às Máquinas de Turing, que reconhecem as gramáticas de tipo 0.
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.
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:
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 3 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
 Os AFN, ou Autômatos Finitos não Determinísticos, reconhecem gramáticas de tipo 0.
 Os Linear Bound Automata, ou Autômatos Limitados Linearmente, reconhecem gramáticas de tipo 3.
 Os Pushdown Automata, ou autômatos de pilha, reconhecem gramáticas de tipo 1.
 Os AF, denominados como Autômatos Finitos, que reconhecem gramáticas de tipo 2.
A alternativa está correta, pois as Máquinas de Turing reconhecem gramáticas de tipo 0 -
Gramáticas irrestritas. As gramáticas irrestritas são do tipo 0 por serem o tipo mais geral na
hierarquia de classificação de Chomsky. 
 
Pergunta 2
0 / 0,2 pts
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 [...].
https://www.hashtagtreinamentos.com/anomalias-em-bancos-de-dados-sql
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 4 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
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.
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 5 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
 III e IV, apenas.
Resposta correta
 I, II e III, apenas.
Você respondeu
 I, II e IV, apenas.
 II e IV, apenas.
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:
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 6 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
 I e III, apenas.
A alternativa está incorreta, pois apenas as afirmações I, II e III estão corretas.
A afirmação I está correta, pois na dependência funcional completa, o atributo não principal é
funcionalmente dependente da chave candidata, além disso, se removermos qualquer atributo, a
dependência não existirá mais.
A afirmação II está correta, pois a dependência funcional completa equivale ao padrão de
normalização da segunda forma normal. Isso ocorre, pois a dependência funcional melhora a
qualidade dos dados em um banco de dados.
A afirmação III está correta, pois a dependência parcial não melhora a qualidade dos dados. Ela
deve ser eliminada para normalizar na segunda forma normal. Já a dependência funcional parcial
não equivale ao padrão de normalização da segunda forma normal. Em vez disso, a segunda
forma normal elimina a dependência parcial.
A afirmação IV está incorreta, pois na dependência funcional parcial é o atributo não primo que é
funcionalmente dependente de parte de uma chave candidata, enquanto na dependência
funcional completa, o atributo não principal é funcionalmente dependente da chave candidata.
 
Pergunta 3
0 / 0,2 pts
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 projetode 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:
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 7 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
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.
A+
A
A-
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 8 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
Você respondeu
 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.
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
Resposta correta
 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.
A alternativa está incorreta, pois a asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
A asserção I é falsa, pois se uma tabela não for devidamente normalizada e tiver redundância de
dados, ela não apenas consumirá espaço de memória extra, mas também dificultará o manuseio
e a atualização do banco de dados, sem enfrentar a perda de dados. Anomalias de inserção,
atualização e exclusão são muito frequentes se o banco de dados não estiver normalizado.
A asserção II é verdadeira, pois a normalização do banco de dados é uma técnica de organização
dos dados em um banco. A normalização é uma abordagem sistemática de decomposição de
tabelas para eliminar a redundância de dados (repetição), além de características indesejáveis,
como anomalias de inserção, atualização e exclusão. É um processo de várias etapas que coloca
os dados em formato tabular, removendo dados duplicados das tabelas de relação.
 
Pergunta 4
0 / 0,2 pts
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:
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
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 9 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
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);
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)
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 10 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
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.
 
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.
V2=V1:
P2=P1:
para
faça
todaA→X,X2X,EPatalquen≥2
se parar€(1,.,n},X,éumsímboloterminal
então (suponhaX,=a)
V2=V2U{Ca}:
substituiaporCaemA→X,X2...Xn€P2;
P2=P2U{Ca→a}:
figura6.17Algoritmo:formanormaldeChomsky-etapa2.
V3=V2:
Рз=P2:
para
faça
todaA→B,B2...B,EPatalquen≥3
P3=P3-{A→B,B,...B,7:
V3=VzU{D,Dn-2}:
P3=P3U{A→B,D1,D,→B2D2...,
Dn-3→Bn-2₽n-2,Dn-2→Bn-1B,}:
figura6.18Algoritmo:formanormaldeChomsky-etapa3.
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 11 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
Você respondeu
 I e II, apenas.
 II, apenas.
Resposta correta
 I e III, apenas.
 I, apenas.
 II e III, apenas.
A alternativa está incorreta, pois apenas as afirmações I e III estão corretas.
A afirmação I está correta, pois é possível que existam diferentes gramáticas e regras, o que
evidencia a necessidade das transformações gramaticais para aprimorar projetos criados por
meio de um compilador. Muitas vezes é útil transformar as regras originais em uma forma mais
simples, essa descrição simplificada é chamada de forma normal.
A afirmação II está incorreta, pois toda gramática livre de contexto pode ser transformada em uma
equivalente na forma normal de Chomsky por uma sequência de quatrotransformações. A
sequência correta dessas transformações leva a uma gramática na forma normal de Chomsky
que aceita a mesma linguagem da gramática dada.
A afirmação III está correta, pois a transformação de uma gramática livre de contexto para a
forma normal de Chomsky é uma série de etapas em ordem. É sabido que as fases da
transformação das gramáticas para as formas normais estão relacionadas à retirada de algumas
produções, além da inclusão de outras. Isso permite que novos conjuntos de produções
reproduzam a mesma linguagem de forma aperfeiçoada.
 
Pergunta 5
0 / 0,2 pts
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:
Leia o texto a seguir:
 
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 12 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
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:
 
| 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
12/06/2024, 09:20Atividade 3: Linguagens Formais e Autômatos
Página 13 de 13https://famonline.instructure.com/courses/35817/quizzes/177232
 
Na Gramática Linear Unitária à direita, ou GLUE, todas as regras de produção são como na gramática linear à
esquerda.
 
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.
Resposta correta
 
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.
Você respondeu
 Na Gramática linear à esquerda, ou GLD, todas as regras de produção são da forma: A→Bw ou A→w.
A alternativa está incorreta, pois na Gramática linear à esquerda (abreviada por GLE), todas as
regras de produção são da forma: A→Bw ou A→w. Uma gramática linear à esquerda é um tipo de
gramática regular, em que todos os não terminais do lado esquerdo existem no local mais à
esquerda, ou seja, nas extremidades esquerdas. A resposta correta é “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”,
pois existe mais de uma forma de restringir as regras de produção, de forma a definir uma
gramática regular. A forma A→wB ou A→w é uma delas. Isso ocorre porque apenas um não
terminal pode aparecer no lado direito de uma produção, e um não terminal deve aparecer na
extremidade direita e do lado direito.
Pontuação do teste: 0,2 de 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: