16 votes
Accepted

DNF to CNF conversion: Easy or Hard

If you are willing to introduce additional variables, you can convert from DNF to CNF form in polynomial time by using the Tseitin transform. The resulting CNF formula will be equisatisfiable with ...
user avatar
  • 141k
7 votes
Accepted

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

Let $n$ be the length of a string. We start with the (non-terminal) symbol $S$ which has length $n=1$. Using $n - 1$ rules of form $(non-terminal) \rightarrow (non-terminal)(non-terminal)$ we can ...
user avatar
  • 1,304
7 votes
Accepted

Is the empty string a terminal symbol?

It's true that, in general, definitions don't include the empty string in the set of "terminals", as there's no need for that (e.g. the production rules for a context-free grammar are defined as a ...
user avatar
7 votes
Accepted

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

Recall that in Chomsky normal form, we are allowed productions of three forms: Productions of the form $A \to a$. Productions of the form $A \to BC$. The production $S \to \epsilon$. We have to ...
user avatar
6 votes
Accepted

What does normalizing with hidden bit really mean?

Generally speaking, normalized means "put in scientific notation." That just means, the mantissa should never start with 0, and should be less than the base. In binary that means the mantissa must ...
user avatar
6 votes

Difference between data duplication and data redundancy

(1) Duplication When you create tables in a database, you may want to create duplication: ...
user avatar
6 votes
Accepted

Convert $\lnot(x \oplus y \oplus z\oplus a)$ to CNF

Use the Tseitin transform. It is a standard way to convert to CNF. It introduces additional variables, but keeps the number of clauses and variables relatively small. You can also use very simple ...
user avatar
  • 141k
6 votes
Accepted

Convert PEG to BNF

Are the languages recognized by PEGs all context-free? No, as is pointed out by Brian Ford in his 2004 paper introducing PEGs, from which is the following short quote: Theorem: The class of PELs ...
user avatar
  • 11.2k
5 votes

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

Yes, you can start with ordinary Greibach NF and replace the offending productions. The trick is the same that is usually used to turn a grammar into Chomsky Normal Form. Introduce new nonterminals ...
user avatar
  • 27.6k
5 votes

Can we move quantifiers to the left in predicate logic?

You are looking for prenex normal form in which all quantifiers "come first". It exists for every first-order formula but you have to take care when transforming; multiple quantifiers may use the ...
user avatar
  • 70.9k
5 votes

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

You read the theorem wrong; the right-hand side contains this $L(\min \dots)$ -- this is not primitive recursive! Note that, in particular, such $z$ does not necessarily exist (the "algorithm" will ...
user avatar
  • 70.9k
5 votes
Accepted

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

No it not true. Primitive recursive functions are a subset of computable functions. The minimization operator from $\mu$-calculus is not primitive recursive and not guaranteed to terminate. The ...
user avatar
  • 3,728
5 votes

Is the empty string a terminal symbol?

The empty string is not a terminal symbol. A terminal symbol is an element of the alphabet, but the empty string is not an element of the alphabet. In fact, this is an issue that we have to address ...
user avatar
4 votes

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

Well, that's not really what Herbrand's theorem says. That's not a good way to think about Herbrand's theorem. To understand the answer to your question, you first need to understand a little better ...
user avatar
  • 141k
4 votes
Accepted

Can every DCFG be converted to DGNF?

If by deterministic GNF you mean as a deterministic grammar that is also GNF then yes, here is the paper. Normal forms of deterministic grammars It is shown that every strict deterministic ...
user avatar
  • 1,602
4 votes
Accepted

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

As @DavidRicherby said, it's best if you ask who-gave-you-the-question what he meant by $(xyz)_2$. But if you absolutely can not do that, then you look at the situation mathematically as... $(xyz)_2$ ...
user avatar
4 votes
Accepted

Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make ...
user avatar
3 votes
Accepted

Converting context-free grammar to Chomsky/Greibach Normal Form

You can convert a context-free grammar into Chomsky normal form or Greibach normal form in whatever way you wish (converting a grammar to a normal form means finding a grammar in the normal form which ...
user avatar
3 votes

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

And each of the $A \to B C$ produtions make the sentential form one longer. You start with length $1$, to reach $n$ means $n - 1$ steps. If a string has length $n$, there will be $n$ steps to get the ...
user avatar
  • 13.6k
3 votes

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

Let us consider an simple example. A -> BC B -> b C -> c String to be generated is bc. Then the steps are. ...
user avatar
3 votes
Accepted

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

Hint: Consider the grammar $$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$ What happens when you remove unit productions?
user avatar
3 votes
Accepted

Can we move quantifiers to the left in predicate logic?

If all the quantified variables are distinct, then you can safely move all quantifiers to the left. This is the only obstruction to this procedure. You can always ensure that all quantified variables ...
user avatar
3 votes
Accepted

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

Depends on how strict you interpret "equivalent". A CFG in ChNF cannot generate the empty string. If you want to have a more precise statement: For every CFG $G$ there is a grammar $G'$ in ChNF ...
user avatar
  • 27.6k
3 votes

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

Any context free grammar can be converted into the equivalent Chomsky Normal Form. It does not matter if it is ambiguous or not.
user avatar
  • 9,602
3 votes

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

Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula: $$ (x-c) \sum_{i=0}^d b_i x^i = (-...
user avatar
2 votes

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

The classical example of a computable function which is not primitive recursive is the Ackermann function. You can also construct such a function using diagonalization: given some effective ...
user avatar
2 votes

Boyce-Codd Normal Form vs. 3rd Normal Form

Because they are two different concepts. A schema satisfies 3NF iff for every functional dependency in the relation such as X -> A, ...
user avatar
  • 206
2 votes

Skolemization with multiple arguments -- how to unify

"Everyone has a heart" gets first encoded first as $\forall x. \text{Person}(x) \Rightarrow \exists y. \text{Hart}(y) \wedge \text{Has}(x,y)$. Then you get the Skolemization (that you found in RN) ...
user avatar
  • 1,230
2 votes

What does normalizing with hidden bit really mean?

Shorter Answer (As requested by greybird in the comments) : The gist of "normalizing" in scientific notation, is not to allow the same number to have ...
user avatar
  • 121
2 votes

CNF form of variable assignment problem

If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints: $x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$ which is $n$ ...
user avatar
  • 521

Only top scored, non community-wiki answers of a minimum length are eligible