is recognized by a deterministic finite automaton.
Moreover, the number of classes of is the smallest number of states of a DFA recognizing .
Then is well defined because implies . It is also straightforward that recognizes .
On the other hand, let be a DFA that recognizes . Extend to by putting and for every , , . Define as
Then is well defined. In fact, suppose : then either , or there are such that . But in the latter case, for any , hence since recognizes . Finally, for any we have so every class of has a preimage according to ; consequently, .
|Date of creation||2013-03-22 18:52:13|
|Last modified on||2013-03-22 18:52:13|
|Last modified by||Ziosilvio (18733)|
|Synonym||Myhill-Nerode theorem for languages|