# Tag Info

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 ...
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 ...
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 ...
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 ...
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 ...

### Difference between data duplication and data redundancy

(1) Duplication When you create tables in a database, you may want to create duplication: ...
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 ...
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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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 ...
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 ...
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$ ...
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 ...
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 ...

### 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 ...

### 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. ...
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?
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 ...
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 ...

### 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.

### 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 = (-...

### 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 ...

### 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, ...

### 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) ...
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$ ...