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
Insoluble , in·sol·u·ble / inˈsälyəbəl/ • adj. 1. impossible to solve: the problem is not insoluble. 2. (of a substance) incapable of being dissolved: once dry,… U , U, u [Called ‘you’]. The 21st LETTER of the Roman ALPHABET as used for English. It originated in the Phoenician consonant symbol waw, the common ance… Eliphelet , Eliphal (ĕl´īfăl, ēlī´fəl), the same as Eliphelet4.
Eliphalet (ēlĬf´əlĕt), in the Bible, name of two sons of David. Alternate forms are Eliphelet and… Chichimec , Chichimec •beck, bedeck, check, cheque, Chiang Kai-shek, crosscheck, Czech, deck, dreck, exec, fleck, heck, hitech, keck, lek, neck, peck, Québec, re… waffle , waf·fle1 / ˈwäfəl; ˈwô-/ inf. • v. [intr.] 1. fail to make up one's mind: Joseph had been waffling over where to go. 2. chiefly Brit. speak or write,… lact- , lact- stem of L. lac, lact- milk (cf. Gr. gála, galakt-; see GALAXY) in derivs.: lactation XVII(f. L. lactāre), lacteal XVII (f. L. lacteus), lacteou…
You Might Also Like
NEARBY TERMS
Myhill equivalence