“Myhill equivalence”的概念、定义、翻译、参考文献-科学参考

Myhill equivalence

Computer

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 w₁,w₂ in Σ‎*,
$w_{1} u w_{2} \in L iff w_{1} u' w_{2} \in 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 w₁,w₂ in Σ‎*,
$f (w_{1} u w_{2}) = f (w_{1} u' w_{2})$
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.
$\begin{array}{l} u =_{M} u' and v =_{M} v' implies \\ u v =_{M} u' v' \end{array}$
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).

单词	Myhill equivalence
释义	Myhill equivalence Computer 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 w₁,w₂ in Σ‎, $w_{1} u w_{2} \in L iff w_{1} u' w_{2} \in 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 w₁,w₂ in Σ‎, $f (w_{1} u w_{2}) = f (w_{1} u' w_{2})$ 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. $\begin{array}{l} u =_{M} u' and v =_{M} v' implies \\ u v =_{M} u' v' \end{array}$ 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).
随便看	Döbereiner, Johann Wolfgang Döbereiner’s triads Dönitz, Karl (1891–1981) Dühring, Eugen Karl (1833–71) Dōgen Kigen (1200–53) D’Alembertian D’Alembert, Jean-Baptiste le Rond (1717–83) d’Alembert, Jean le Rond (1717–83) D’Alembert’s Principle d’Arrest d’Arsonval galvanometer E e E1P-2 E1 reaction, E2 reaction E2E EA EAC Eadie–Hofstee plot EADS Eagle eagle Eagle Nebula EAN EAPROM