“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).
随便看	translation of axes(in Cartesian space) translation(of Cartesian space) translation table translator translator writing system translocation translucent translucidus translunar injection transmembrane domain transmigration of souls transmission transmission channel transmission coefficient Transmission Control Protocol transmission control unit transmission electron microscope transmission gain transmission grating transmission level transmission line transmission line matrix transmission loss transmission mechanism transmission mode