Nerode equivalence

'Nerode equivalence' can also refer to...


More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

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 Σ*, uwL iff uwL and for a function f, u =Nu′ if, for all w in Σ*, f(uw) = f(uw) 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 =Nuv 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.

u =Nu

uwL iff uwL

u =Nu

f(uw) = f(uw)

u =Nu′ implies uv =Nuv

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.