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 ...
D.W.♦
- 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 ...
- 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 ...
- 333
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 ...
- 270k
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 ...
- 17.3k
6
votes
Difference between data duplication and data redundancy
(1) Duplication
When you create tables in a database, you may want to create duplication:
...
- 225
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 ...
D.W.♦
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 270k
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 ...
D.W.♦
- 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 ...
- 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$ ...
- 1,175
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 ...
- 270k
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 ...
- 270k
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 ...
- 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.
...
- 31
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?
- 270k
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 ...
- 270k
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 ...
- 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.
- 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 = (-...
- 270k
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 ...
- 270k
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, ...
- 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) ...
- 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 ...
- 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$ ...
- 521
Only top scored, non community-wiki answers of a minimum length are eligible