An equivalence relation, =N, arising in formal language theory. It is defined analogously to the Myhill equivalence by the weaker properties:
for a language L over Σ, u =Nu′ if, for all w in Σ*, uw ∈ L iff u′ w ∈ L and for a function f, u =Nu′ if, for all w in Σ*, f(uw) = f(u′w) Although coarser than the Myhill equivalence, it is finite only if the latter is. Unlike the latter, it gives only a right congruence: u =Nu′ implies uv =Nu′v and thus does not give rise to a semigroup. The number of equivalence classes is the number of states in the minimal machine for L.
uw ∈ L iff u′ w ∈ L
f(uw) = f(u′w)
u =Nu′ implies uv =Nu′v