Myhill equivalence
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 Σ*, w1uw2 ∈ L iff w1u′w2 ∈ L
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(w1u′w2)
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 u′v′
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).
if, for all w1,w2 in Σ*, w1uw2 ∈ L iff w1u′w2 ∈ L
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(w1u′w2)
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 u′v′
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).
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
Myhill equivalence