Nerode Equivalence Definition/Meaning:
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 = N u'
if, for all w in ∑*,
uw € L iff u'w
€ L
for a function ƒ
u = N u'
if, for all w in ∑*,
ƒ(uw) =
ƒ(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 = N u' implies uv = N u' 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.
|
