Myhill equivalence

views updated

Myhill equivalence 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 =M u

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 =M u

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 =M u′ and v =M v′ implies uv =M uv

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).