# Tag Info

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