constructing automata from regular languages
In this entry, we describe how a certain equivalence relation on words gives rise to a deterministic automaton, and show that deterministic automata to a certain extent can be characterized by these equivalence relations.
Constructing the automaton
Let be an alphabet and a subset of , the set of all words over . Consider an equivalence relation on satisfying the following two conditions:
is a right congruence: if , then for any word over ,
implies that iff .
We can construct an automaton based on . Here’s how:
, the set of equivalence classes of ; elements of are denoted by for any ,
is given by ,
is a singleton consisting of , the equivalence class consisting of the empty word ,
is the set consisting of , where .
By condition 1, is well-defined, so is a deterministic automaton. By the second condition above, iff .
By induction, we see that for any word over . So
In addition, , as iff iff iff .
Constructing the equivalence relation
This binary relation is clearly an equivalence relation, and it satisfies the two conditions above, with :
if , then clearly iff .
Remark. We could have defined the binary relation to mean for all . This is also an equivalence relation that satisfies both of the conditions above. However, this is stronger in the sense that is a congruence: if , then so that . In this entry, only the weaker assumption that is a right congruence is needed.
Fix an alphabet and a set . Let the set of equivalence relations satisfying the two conditions above, and the set of accessible deterministic automata over accepting . Define and such that and are the automaton and relation constructed above.
and is isomorphic to .
Suppose . Then iff iff iff .
Conversely, suppose . Then , , and consists of all such that . As a result, iff iff iff . This shows that is equivalent to .
To show is isomorphic to , define by . Then
iff iff iff . Therefore, .
Thus, is a homomorphism from to , together with the fact that is a bijection, is isormorphic to . ∎
If is the Nerode equivalence of , then the is a reduced automaton. If is reduced, then is the Nerode equivalence of .
Suppose is the Nerode equivlance. If is not reduced, reduce it to a reduced automaton . Then . Since satisfies the two conditions above and is the largest such relation, . Therefore is isomorphic to . But is reduced, so must .
On the other hand, suppose is reduced. Then . Conversely, if , then iff for any word , so that , or , which implies and are indistinguishable. But is reduced, this means . As a result , or . ∎
Definition. A Myhill-Nerode relation for is an equivalence relation that satisfies the two conditions above, and that is finite.
|Title||constructing automata from regular languages|
|Date of creation||2013-03-22 19:02:09|
|Last modified on||2013-03-22 19:02:09|
|Last modified by||CWoo (3771)|