almostequivalent

Almostequivalent, sometimes written as almost equivalent, is a notion used in formal language theory and related areas to describe objects that agree on all but finitely many inputs. Two languages L1 and L2 over the same alphabet are almost equivalent if their symmetric difference L1 Δ L2 is finite; equivalently, they contain exactly the same words except for a finite set of exceptions. The concept extends to functions f and g from strings to a common codomain by requiring that the set of inputs where they differ is finite.

Formally, L1 and L2 are almost equivalent if L1 Δ L2 = (L1 \ L2) ∪ (L2 \ L1) is finite. For functions, f: Σ* → D and g: Σ* → D are almost equal when {w ∈ Σ* | f(w) ≠ g(w)} is finite. Almost equivalence is an equivalence relation: if A ≈ B and B ≈ C, then A ≈ C, because the symmetric difference A Δ C is contained in (A Δ B) ∪ (B Δ C), which is finite.

Examples illustrate the idea. If L1 is the set of all strings over {a,b} except the single string "ab", and L2 is all strings except "ba", then L1 Δ L2 = {"ab","ba"}, a finite set, making L1 and L2 almost equivalent. In automata theory, two automata are almost equivalent if the languages they recognize differ by only finitely many words.

Context and significance: almostequivalence captures equality up to finite differences, a useful abstraction for asymptotic or coarse-grained analyses. It is related to the idea of equality modulo finite differences and to the Fréchet filter of cofinite sets.