Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [normal-forms]

Questions about normal forms in various contexts, for example normal forms of context-free grammars (Chomsky normal form, Greibach normal form), of formulas (conjunctive normal form, disjunctive normal form), and others.

2
votes
2answers
78 views

Proof that POSITIVE-3-SAT is in the complexity class P

I have the following language: $$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of ...
0
votes
1answer
68 views

Why “ every non-prime attribute of R is non-transitively dependent on every key of R” in the original def of 3NF?

I have read the definition in of Third_normal_form here , which shows The third normal form (3NF) is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971.[2]...
3
votes
1answer
57 views

Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following: Let $F(x)$ be given as a product $F(x) = \prod_{...
0
votes
1answer
30 views

Normal form after decomposition of a relation

I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF. I felt a bit ...
1
vote
1answer
26 views

Efficiency/Redundancy in Chomsky normal form

I have a context-free grammar with the following production rules, $S$ being the start symbol: $$\begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*}$$ Is this in Chomsky normal ...
0
votes
1answer
41 views

Normal form of relation R

It is given that for a relation R all the attributes of the relation appear in some of the candidate keys. It is also given that there is only one compound candidate key which exists for a relation, ...
2
votes
2answers
46 views

When are you supposed to eta-reduce?

Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$: If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ ...
0
votes
0answers
74 views

How are these two definitions of the Third Normal Form (3NF) equivalent?

According to the textbook by Silberschatz, A relation schema R is in third normal form with respect to a set $F$ of functional dependencies if, for all functional dependencies in $F^+$ of the form $\...
0
votes
1answer
37 views

Context free grammar to Chomsky's normal form

\begin{align*} S&\to AACD\\ A&\to aAb\\ C&\to aC\mid a\\ D&\to aDa\mid bdb\mid\varepsilon \end{align*} I think that this grammar is infinite so it is not possible to convert it into ...
0
votes
1answer
41 views

Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $

I'm trying to find the CNF of the $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q))$, and afterwards proving it's validity. As i'm new to CNF i wanted to ensure i've ...
0
votes
1answer
53 views

Reusing variable in converting grammar to Chomsky Normal Form

I'm not sure if reusing variable is allowed in CNF. For example, I have this grammar not in CNF. So I have to convert it to CNF. ...
0
votes
1answer
14 views

Confusion regarding dependencies

Let say we have a relation with 5 attributes {A, B, C, D, E}. Let say we have two candidate keys as A and ...
-1
votes
1answer
116 views

Convert grammar to Greibach form

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
1
vote
0answers
23 views

Confluence versus the property of every term having at most one normal form

If a term rewriting system is confluent, then every term has at most one normal form. Is the converse also true, or is confluence a strictly stronger property? I.e. if every term has at most one ...
0
votes
0answers
42 views

Strong normalization and concatenative programming language

Are there some references about concatenative programming languages with the normalization property?
2
votes
1answer
28 views

Identifying/equating constants in a term rewrite system

Suppose we have a term rewrite system $\mathcal{R} = (R, \Sigma)$ with basic rewrite rules $R$ over a signature $\Sigma$. Suppose also that this rewrite system $\mathcal{R}$ is confluent and ...
5
votes
2answers
304 views

Why is the start symbol “not allowed” on the right hand side in Chomsky normal form?

I had a question regarding CNF (Chomsky normal form) in formal language theory. I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow ...
2
votes
0answers
60 views

Term for weak head normal forms that cannot be reduced in any environment

In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (...
0
votes
1answer
307 views

Transitive dependency in 3NF

Came across this question : State whether True or False A prime attribute can be transitively dependent on a key in 3NF Answer: True How could this be true? Because as far as I know, A relation ...
2
votes
2answers
1k views

Is the empty string a terminal symbol?

I ask this question with regards to a grammar in Chosmky Normal Form. The definition states that the rules must be of the following forms: A $\rightarrow$ BC A $\rightarrow$ a S $\rightarrow$ $\...
-4
votes
1answer
376 views

Can any ambiguous context-free grammar be converted into Chomsky normal form? [closed]

Can an ambiguous context-free grammar be converted into Chomsky normal form? I think the answer is yes.
0
votes
1answer
278 views

Can every CFG be converted into an equivalent CFG of this form?

Question: Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables. ...
2
votes
1answer
2k views

Chomsky or Greibach Normal Form?

I tried to solve this exercise: Discuss the normal forms (CNF or GNF) of a grammar with productions: $S\rightarrow BC | CB$ $B\rightarrow cB | c$ $C\rightarrow cC | \epsilon$ Same request with ...
4
votes
1answer
61 views

Can minimal CNF contain clause longer than initial CNF?

Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$. Can $\Phi_{min}$ contain a clause of size $m > k$? What ...
2
votes
0answers
88 views

Growth of non-terminating beta reductions in lambda calculus

There are some terms in lambda calculus that don't really have a normal term. My question is for a term like the following: $$T \overset{def}{=} \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$ $T$ ...
2
votes
1answer
321 views

Proof any CFG can be converted to GNF

I studied algorithm for converting grammars to GNF and was wondering about a proof that any CFG can be converted into GNF. I found this paper - ENGELFRIET, Joost. An Elementary Proof of Double ...
0
votes
1answer
351 views

For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?
2
votes
0answers
65 views

Construct skolemform of: $\forall X.((\forall Y.\exists Z. R(X,Y,Z)) \land \forall S. \exists T. R(X, S,T))$

This question is not asking for a solution, but rather as a check / validation of my thought process. Given the form: $W = \forall X.((\forall Y.\exists Z. R(X,Y,Z)) \land \forall S. \exists T. R(X,...
0
votes
1answer
306 views

How do I normalize a push down automaton?

Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q_1$ to $q_1$, because I know a transition must either push OR pop from the stack. Does ...
0
votes
0answers
38 views

Why are the 1st 2nd and 3rd normal forms ignored in some database books/courses?

Why are the 1st 2nd and 3rd normal forms ignored in some Database books/courses? specifically: https://lagunita.stanford.edu/courses/Engineering/db/2014_1/about and https://www.amazon.com/Database-...
6
votes
1answer
431 views

Convert PEG to BNF

Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences: The ordered choice operator ...
0
votes
1answer
19 views

term vs clause in the context of normal forms

In the context of disjunctive normal forms, which terminology do you use for the conjunction of atoms? E.g., for the disjunctive normal form $(x₁ ∧ ¬x₂ ∧ x₃) ∨ (¬x₁ ∧ x₂ ∧ x₃)$, how are the ...
2
votes
1answer
87 views

Write the conjunctive or disjunctive normal form of an expression $f$ [closed]

Write the conjunctive or disjunctive normal form of an expression $f$ that is true if the number $t=(xyz)_2$ is a zero of the following polynomial: $$p(t)=(t-6)(t-5)(t-4)(t-2)t(t+1)(t+3)(t+7)$$ The ...
1
vote
1answer
303 views

Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?

A CFG is in strong GNF when all rewrite rules are in the following form: $A \rightarrow aA_1...A_n$ where $n \leq 2$.
0
votes
0answers
50 views

Stuck on Converting to Chomsky Normal Form,

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...
0
votes
1answer
151 views

Is converting boolean formulas to sum-of-products a hard problem?

My reasoning is as follows. Every boolean formula can be expressed as a sum-of-products. Every sum-of-produts is a list of minterms. For each minterm, there is 1 combination of inputs that satisfy ...
6
votes
2answers
86 views

CNF form of variable assignment problem

There are n variables $x_1$, $x_2$,..., $x_n$ and each one of them takes values from 1 to k (k>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying ...
3
votes
1answer
4k views

When is relation in 3NF but not in BCNF?

A book by Korth et al. defines BCNF as follows: A relation schema $R$ is in BCNF with respect to a set F of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, ...
6
votes
1answer
77 views

When is ε-removal from a CFG idempotent?

For which context-free grammars is it idempotent to remove $\varepsilon$-productions? Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\...
1
vote
1answer
354 views

Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V_t$ and $A,B,C \in V_n $ with rewriting rules of ...
2
votes
2answers
4k views

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3): The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters ...
1
vote
2answers
863 views

Converting context-free grammar to Chomsky/Greibach Normal Form

Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). ...
2
votes
0answers
4k views

Converting CNF to GNF

I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly ...
4
votes
2answers
413 views

Canonical representation of programs

I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume ...
-1
votes
1answer
1k views

Convert a CFG into CNF

I'm still new to CFG and CNF and have trouble sometimes understanding the concepts. I'm trying to convert this CFG into Chomsky Normal Form: ...
2
votes
0answers
102 views

how to compute functional dependencies and MVDs after decomposition?

Let's say we have a relation $R$ with a set of functional and multivalued dependencies $F$, and we found a dependency that violates some normal form. Then we decompose $R$ into $R_1$ and $R_2$. How to ...
0
votes
1answer
425 views

Does removal of unit production from the grammar may increase number of total production?

There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) (b) O($m^2$) (c) O($k^m$) (d) O($...
-1
votes
1answer
871 views

Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
2
votes
2answers
266 views

Why is there more frequent overflow in normalised Floating Point

I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised ...
3
votes
0answers
47 views

A syntactic property of computing systems: is non-coding DNA universal?

One of the surprising aspect of the genome for lay-people is that it contains important non-coding DNA parts, which does not mean that they are all useless. I never paid so much attention to the fact, ...