16
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 the original DNF formula: the CNF formula will be satisfiable if and only if the original DNF formula was satisfiable. See also https://en.wikipedia.org/wiki/...
7
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 construct a string containing $n$ non-terminal symbols.
Then on each non-terminal symbol of said string of length $n$ we apply a rule of form $(non-terminal) \...
7
Chomsky normal form enables a polynomial time algorithm to decide whether a string can be generated by a grammar.
The algorithm is pretty slick if you know dynamic programming...
If the length of your input ($I$) is $n$ then you take a 2d array ($A$) of dim $n$x$n$.
$A[i,j]$ denotes all the symbols in the grammar $G$ that can derive the sub-string $I(i,j)$...
7
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 relation $V \rightarrow (V \cup \Sigma)^*$ - the star covers all productions of the form $A \rightarrow \epsilon$; in all other contexts, it can be omitted because ...
7
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 allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.
Suppose for a moment that the production $S \to \epsilon$...
6
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 methods using De Morgan's laws (or Karnaugh maps or the Quine–McCluskey algorithm) to find an equisatisfiable CNF that does not introduce any new variables, but ...
6
(1) Duplication
When you create tables in a database, you may want to create duplication:
CREATE TABLE user (name TEXT, id INTEGER);
CREATE TABLE friends (name TEXT, friend_of_id INTEGER);
Here you would duplicate the name of the user in both tables. That way when you display the list of friends, you do not have to access the user table to read the name. ...
6
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 includes non-context-free languages.
Proof: The classic example language $a^nb^nc^n$ is not context-free,
but we can recognize it with a PEG $G = (\{A, B, D\}, \{a,...
5
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 same variable (name) in the original formula, but they may not in the normal form.
5
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 be "1". Since the mantissa of a normalized binary floating point number is always 1, we don't need to store the 1. The first mantissa bit is hidden in the ...
5
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 loop.)
$L(\min \_)$ in that theorem is also called the $\mu$-operator. It can not be expressed with primitive recursion.
This theorem states that one ...
5
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 constantly false function for instance would cause minimization to loop infinitely. As you likely know primitive recursion is guaranteed to terminate.
What does seem ...
4
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 what Herbrand's theorem does and doesn't imply.
I suspect I know what you are thinking. You are thinking, given a statement $\varphi$ of first-order logic, ...
4
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 language may be given a
strict deterministic grammar which is also in Greibach normal form.
EDIT
Here is a paper outlining the technique to do the conversion Strict ...
4
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 that represent sequences of old nonterminals, for instance $[A_1A_2\dots A_k]$ is a single symbol that represents the sequence $A_1A_2\dots A_k$ when $k\ge 2$.
...
4
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$ here is a set $\{000,001,010,011,...,111\}$ of $8$ elements which forms a ring.
In particular, it supports two binary operation $+$ and $\times$ where both ...
4
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 when defining the formal syntax of context-free grammars. Either we ask that $\epsilon \notin \Sigma$, or we encode $\epsilon$-rules as $A \to$ rather than as $A ...
4
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 sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately.
How does the $\epsilon$-removal work? Suppose that we ...
3
Hint: Consider the grammar
$$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$
What happens when you remove unit productions?
3
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 generates the same language as the original grammar). A given algorithm might require you first to remove lambda productions, or first to convert to Chomsky ...
3
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 terminals. In all, $2 n - 1$ steps.
3
Yes, the grammar you noww have is still illegal. For CFG you can only have two types of productions $A\to BC$ and $A\to a$ where $A,B,C$ are nonterminals (variables) and $a$ terminal.
It is best to add additional variables that introduce the brackets $A\to ($ and $B\to )$.
Now you can use $S\to AB$ instead of your production $S\to ()$.
Finally, try to get ...
3
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 are distinct by renaming them. For example, starting with
$$(\forall x P(x)) \lor (\forall x Q(x)),$$
we first rename the second variable to $y$,
$$(\forall x P(...
3
Let us consider an simple example.
A -> BC
B -> b
C -> c
String to be generated is bc.
Then the steps are.
A -> BC
-> bC
-> bc
Thus no of steps required is 3.
That is $2n-1$.
3
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 such that
$L(G) = L(G') - \{\varepsilon\}$.
So now we have two choices.
Either to accept the loss of the empty string, which in practise is not a big deal. Or ...
3
Any context free grammar can be converted into the equivalent Chomsky Normal Form. It does not matter if it is ambiguous or not.
3
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 = (-cb_0) x^0 + \sum_{i=1}^d (b_{i-1}-cb_i)x^i + b_dx^d.
$$
If you compute $(x-a_1)\cdots(x-a_n)$ by successively multiplying the terms, i.e. by computing $P_1 = x-...
2
Because they are two different concepts.
A schema satisfies 3NF iff for every functional dependency in the relation such as X -> A, X is a key or A is prime (part of the key).
A schema satisfies BCNF iff for every functional dependency in the relation such as
X -> A, X is a key.
You can clearly see from these definitions that every BCNF must also ...
2
Let's work it out through the conversion algorithm given in
Wikipedia.
input:
$S \to abC \mid babS \mid de$
$C\to aCa \mid b$
Introduce $S_0$:
$S_0 \to S$
$S \to abC \mid babS \mid de$
$C\to aCa \mid b$
remove $\epsilon$ rules: there are no $\epsilon$ rules, so nothing changes.
eliminate unit rules: Originally, there are none, but we added one, ...
2
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 enumeration $f_n$ of the primitive recursive functions, the function $n \mapsto f_n(n) + 1$ is computable but not primitive recursive.
Only top voted, non community-wiki answers of a minimum length are eligible