Myhill-Nerode theorem for semigroups
Theorem 1 (Myhill-Nerode theorem for semigroups)
Theorem 1 generalizes Myhill-Nerode theorem for languages to subsets of generic, not necessarily free, semigroups. In fact, as a consequence of Theorem 1, a language on a finite alphabet is recognizable in the sense given above if and only if it is recognizable by a DFA.
Proof of Theorem 1.
Since is a morphism, is a congruence; moreover, means that is union of classes of -equivalence. By the maximality property of syntactic congruence, the number of classes of does not exceed the number of classes of , which in turn does not exceed the number of elements of .
Since iff for every , determining is the same as determining as varies in , plus the class . (This additional class takes into account the possibility that for any , which cannot be excluded a priori: do not forget that is not required to be a monoid.)
But since implies , if then as well. To determine it is thus sufficient to determine the for , plus .
We can thus identify the class with the sequence Then the number of classes of cannot exceed that of -ples of classes of , which is .
|Title||Myhill-Nerode theorem for semigroups|
|Date of creation||2014-05-14 17:29:14|
|Last modified on||2014-05-14 17:29:14|
|Last modified by||Ziosilvio (18733)|
|Defines||recognizable subset of a semigroup|