The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
78 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
92 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 ...
0
votes
1answer
84 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). ...
0
votes
1answer
29 views

How can I solve this Functional Dependency?

Consider R(A, B, C) with FDs F ={A→B, B→C, A→C} Prove or disprove F |= C → A There are 7 inference rules from Armstrong's Axiom. Which one is to use here?
0
votes
0answers
91 views

How to remove null-productions in a CFG?

I have the CFG $\begin{array}{lll} S &\to &BB\mid 0A0 \mid 1B1\\ A &\to &C\\ B & \to & S \mid \varepsilon\\ C & \to & S \mid A \end{array}$ And understand that when ...
4
votes
2answers
227 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
119 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
65 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
115 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($...
0
votes
0answers
301 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
105 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
32 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, ...
-1
votes
1answer
173 views

Chomsky Normal Form-remove unit production

In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, ...
-3
votes
1answer
40 views

Chomsky Normal Form of |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...
0
votes
0answers
20 views

Chomsky Normal Form |a|<|b| [closed]

Hello Everyone I was hoping I could ask you to check to my work on this CNF, These are a pain to me and I want to make sure I'm doing it right the first time ...
0
votes
1answer
70 views

Database normalization impractical

After third form normalization, extra tables shall be created. And the functional determinant are used as primary key in the new table, as foreign key in the modified old table. My question is that ...
7
votes
1answer
765 views

DNF to CNF conversion: Easy or Hard

In relation to the thread CNF to DNF — conversion is NP Hard (and a related Math thread): How about the other direction, from DNF to CNF? Is it easy or hard? On Page 2 of this paper, they seem to ...
1
vote
1answer
47 views

Term rewrite system is non-confluent, but cannot find different normal forms of term

I wrote a simple TRS that I believe is non-confluent, but I'm not able to find a term with two normal forms for it. The TRS is defined on the signature $\mathcal F=\{f,\ l,\ s,\ o\}$ and the rewrite ...
3
votes
2answers
127 views

Skolemization with multiple arguments — how to unify

Edit: answerers keep finding (valid!) problems with my example. I'll try again. The older version is below the horizontal line. Thanks to Klaus below for pointing out the last problem. My ...
2
votes
2answers
257 views

What does normalizing with hidden bit really mean?

I have a question related to representing numbers in base 2 with floating point. For example, if I have such a number $$0.000011 \cdot 2^3$$ then is its normalized form this? $$1.1\cdot 2^{-2}$$ ...
2
votes
3answers
228 views

Does the normal form theorem imply that every partially computabe function is primitive recursive?

This is Normal Form Theorem (Second Edition of Computability, Complexity, and Languages written by Martin Davis page 75): Let $f(x_1,...,x_n)$ be a partially computable function. Then there is a ...
0
votes
1answer
456 views

BCNF Decomposition: Confusion regarding given answer

I encountered the following question: Given a relation R(A, B, C, D) with the following functional dependencies: A -> B, C -> D, B -> C. The BCNF Decomposition of R is: A) {(A,B), (C,D), (B,C)} B) {...
3
votes
1answer
99 views

Does Herbrand's theorem mean any first-order logic formula can be expressed in CNF?

Herbrand's theorem shows that any formula of first-order logic can be expressed as a disjunction of quantifier-free formulas of first-order logic. Is this equivalent to saying that Herbrand's theorem ...
3
votes
1answer
7k views

Difference between data duplication and data redundancy

My Computing teachers talk about data duplication and data redundancy in terms of databases as different things, but I'm struggling to differentiate them. The context is database normalisation, and in ...
2
votes
1answer
91 views

Can every DCFG be converted to DGNF?

I know you can convert every context-free grammar into Greibach normal form grammar. But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?
1
vote
2answers
219 views

Can we move quantifiers to the left in predicate logic?

Say I have part of a query in the form: ∃xa(...)∧∃xb(...)∧∃xc(...), where a, b, and c are attributes and the ellipses can be anything (I'm looking for a general rule). Is this equivalent to saying ∃xa,...
0
votes
1answer
522 views

Boyce-Codd Normal Form vs. 3rd Normal Form

Any schema that satisfies BCNF also satisfies 3NF. But how can this be true if BCNF does not necessarily guarantee dependency preservation, whereas 3NF guarantees dependency preservation?
1
vote
1answer
151 views

Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form. I have S -> abC | babS | de C -> aCa |b I know what to do with the case ...
-3
votes
2answers
528 views

Boolean algebra fast CNF convertion

I have been solving a "hard" boolean formula today and found a nice shortcut. So just wanted to share. When given the next formula how would you convert it to CNF? $\lnot(x \oplus y \oplus z\...
0
votes
1answer
85 views

conversion of this grammar to CNF

My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$ after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$ after removing unit productions: $S\to ...
1
vote
1answer
629 views

Normal form Lambda calculus expression

I need a little help with a lambda calculus reduction to normal form: $$(\lambda xxxx.xx)(\lambda x.xx)(\lambda x.x)y((\lambda x.x)x)$$ It should be solved like this: $$xx(\lambda x.x)y((\lambda x.x)x)...
3
votes
1answer
525 views

Are all databases reducible to this ultimate abstract database design?

I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those ...
2
votes
1answer
39 views

Chomsky form for language of single alphabet member

I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a} My approach was ...
6
votes
3answers
3k views

The importance of normal forms like Chomsky normal form for CFGs

I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
1
vote
1answer
3k views

CFG to Chomsky normal form

I've read this part like 3-4 times and I'm not understanding what is going on. Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The ...
6
votes
2answers
4k views

“Applicative order” and “Normal order” in lambda-calculus

Applicative order: Always fully evaluate the arguments of a function before evaluating the function itself , like - $(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. x^2(2+1))\...
4
votes
1answer
375 views

3CF 3-conjunctive form satisfiability

I am self studying discrete math and I am going through MIT Mathematics for CS lecture notes but they do not have solutions available. I got stuck at Problem 3.14 (pages 64-65 of this document). The ...
10
votes
1answer
1k views

Proving that the conversion from CNF to DNF is NP-Hard

How can I prove that the conversion from CNF to DNF is NP-Hard? I'm not asking for an answer, just some suggestions about how to go about proving it.