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

Nerode equivalence

Computer

An equivalence relation, =_N, arising in formal language theory. It is defined analogously to the Myhill equivalence by the weaker properties:
$\begin{array}{l} for a language L over Σ, \\ u =_{N} u' \\ if, for all w in Σ^{*}, \\ u w \in L iff u' w \in L \\ and for a function f, \\ u =_{N} u' \\ if, for all w in Σ^{*}, \\ f (u w) = f (u' w) \end{array}$
Although coarser than the Myhill equivalence, it is finite only if the latter is. Unlike the latter, it gives only a right congruence:
$u =_{N} u' implies u v =_{N} u' v$
and thus does not give rise to a semigroup. The number of equivalence classes is the number of states in the minimal machine for L.

单词	Nerode equivalence
释义	Nerode equivalence Computer An equivalence relation, =_N, arising in formal language theory. It is defined analogously to the Myhill equivalence by the weaker properties: $\begin{array}{l} for a language L over Σ, \\ u =_{N} u' \\ if, for all w in Σ^{}, \\ u w \in L iff u' w \in L \\ and for a function f, \\ u =_{N} u' \\ if, for all w in Σ^{}, \\ f (u w) = f (u' w) \end{array}$ Although coarser than the Myhill equivalence, it is finite only if the latter is. Unlike the latter, it gives only a right congruence: $u =_{N} u' implies u v =_{N} u' v$ and thus does not give rise to a semigroup. The number of equivalence classes is the number of states in the minimal machine for L.
随便看	YACC Yagi aerial Yagi antenna Yahoo yak Yale Bright Star Catalogue Yalow, Rosalyn Sussman Yalta Conference (4–11 February 1945) Yamagata Aritomo (1838–1922) Yamashita Tomoyuki (1888–1946) Yamato Yang, Chen Ning Yang, Chen Ning (1922– ) Yang Chu (c.370–319) Yang Hsiung (53 bc–ad 18) Yang, Liu (1978– ) Yang, Liwei (1965– ) Yangshao Yang–Mills theory Yaoundé Convention yard yardang Yarkovsky effect Yarmouthian Yatalan