Myhill equivalence

Show Summary Details

Quick Reference

An equivalence relation arising in formal language theory. If L is a language over alphabet Σ (see word) then its Myhill equivalence is the relation =M on Σ* defined as follows:

u =Mu

if, for all w1,w2 in Σ*,

w1uw2L iff w1uw2L

Similarly (and more generally), if f is a function from Σ* to any set, its Myhill equivalence is defined by:

u =Mu

if, for all w1,w2 in Σ*,

f(w1uw2) = f(w1uw2)

See also Nerode equivalence.

An important fact is that L is regular iff the equivalence relation =M is of finite index (i.e. there are finitely many equivalence classes). Indeed, L is regular iff it is a union of classes of any equivalence relation of finite index. In addition =M is a congruence on Σ*, i.e.

u =Mu′ and v =Mv′ implies

uv =Muv

The equivalence classes therefore can be concatenated consistently and form a semigroup. This is in fact the semigroup of the minimal machine for L (or f).

Subjects: Computing.

Reference entries

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