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 .
An example of this is the Nerode equivalence of (in fact, the largest such relation).
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
One consequence of this is that is accessible (all states are accessible).
In addition, , as iff iff iff .
Constructing the equivalence relation
Conversely, given a deterministic automaton , a binary relation on may be defined:
This binary relation is clearly an equivalence relation, and it satisfies the two conditions above, with :
-
•
,
-
•
if , then clearly iff .
So .
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.
Characterization
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.
Proposition 1.
and is isomorphic to .
Proof.
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, .
-
•
Finally, .
Thus, is a homomorphism from to , together with the fact that is a bijection, is isormorphic to . ∎
Proposition 2.
If is the Nerode equivalence of , then the is a reduced automaton. If is reduced, then is the Nerode equivalence of .
Proof.
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.
Combining from what we just discussed above, we see that a language is regular iff its Nerode equivalence is a Myhill-Nerode relation, which is the essence of Myhill-Nerode theorem.
Title | constructing automata from regular languages |
---|---|
Canonical name | ConstructingAutomataFromRegularLanguages |
Date of creation | 2013-03-22 19:02:09 |
Last modified on | 2013-03-22 19:02:09 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 11 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03D10 |
Classification | msc 68Q42 |
Classification | msc 68Q05 |
Defines | Myhill-Nerode relation |