5
votes
Equivalence relation between two CFG's
$G_1$ and $G_2$ are equivalent if and only if $L_{G_1} = L_{G_2}$.
Since the relation $=$ is an equivalence relation over languages, so is the equivalence between grammars.
- 7,193
2
votes
Accepted
Complexity of string comparison vs whitespace-trimmed string comparison
From the viewpoint of complexity theory, comparing two strings, with or without surrounding whitespace, takes time linear in the lengths of the strings, because there is no computational model, ...
- 11.3k
1
vote
Accepted
Is the equality of Bloom filters analogous to set equivalence?
It is possible to find an upper bound on the probability of a collision in the fingerprint. Suppose the Bloom filter uses $k$ hash functions and maps into a bit array of size $m$.
The case $k=1$ is ...
D.W.♦
- 143k
1
vote
Accepted
Equivalence relation between two CFG's
Let $\mathcal{G}$ be the set of all context-free grammars and let $\rho \subseteq \mathcal{G}^2$ denote the binary relation "being equivalent to".
Let $G$ be a CFG grammar. Clearly it holds ...
- 23.9k
1
vote
Algorithm best compare similarities between two data sets in percentage
You'll need two algorithms (definitions, actually) here:
one to define a distance between answers with in questions
one to define a distance between complete questionnaires
It makes working with 2 ...
- 121
Only top scored, non community-wiki answers of a minimum length are eligible