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.
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 121

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