constructing automata from regular languages (original) (raw)
Constructing the automaton
Let Σ be an alphabet and R a subset of Σ*, the set of all words over Σ. Consider an equivalence relation ≡ on Σ* satisfying the following two conditions:
An example of this is the Nerode equivalence 𝒩R of R (in fact, the largest such relation
).
We can construct an automaton A=(S,Σ,δ,I,F) based on ≡. Here’s how:
- •
S=Σ*/≡, the set of equivalence classesof ≡; elements of S are denoted by [u] for any u∈Σ*,
- •
δ:S×Σ→S is given by δ([u],a)=[ua], - •
I is a singleton consisting of [λ], the equivalence class consisting of the empty word - •
F is the set consisting of [u], where u∈R.
By condition 1, δ is well-defined, so A is a deterministic automaton. By the second condition above, [u]∈F iff u∈R.
By induction, we see that δ([u],v)=[uv] for any word v over Σ. So
| u≡v iff δ([u],λ)=δ([v],λ). |
|---|
One consequence of this is that A is accessible (all states are accessible).
In addition, R=L(A), as u∈L(A) iff δ([λ],u)∈F iff [u]∈F iff u∈R.
Constructing the equivalence relation
Conversely, given a deterministic automaton A=(S,Σ,δ,{q0},F), a binary relation ≡ on Σ* may be defined:
| u≡v iff δ(q0,u)=δ(q0,v). |
|---|
This binary relation is clearly an equivalence relation, and it satisfies the two conditions above, with R=L(A):
- •
δ(q0,uw)=δ(δ(q0,u),w)=δ(δ(q0,v),w)=δ(q0,vw), - •
if δ(q0,u)=δ(q0,v), then clearly u∈L(A) iff v∈L(A).
So [u]={v∈S∣δ(q0,v)=δ(q0,u)}.
Remark. We could have defined the binary relation u≡v to mean δ(q,u)=δ(q,v) for all q∈S. 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 u≡v, then δ(q,wu)=δ(δ(q,w),u)=δ(δ(q,w),v)=δ(q,wv) so that wu≡wv. In this entry, only the weaker assumption that ≡ is a right congruence is needed.
Characterization
Fix an alphabet Σ and a set R⊆Σ*. Let X the set of equivalence relations satisfying the two conditions above, and Y the set of accessible deterministic automata over Σ accepting R. Define f:X→Y and g:Y→X such that f(≡) and g(A) are the automaton and relation constructed above.
Proposition 1.
Proof.
Suppose ≡1↦fA↦g≡2. Then u≡1v iff δ([u],λ)=δ([v],λ) iff δ([λ],u)=δ([λ],v) iff u≡2v.
Conversely, suppose A1=(S1,Σ,δ1,q1,F2)↦g≡↦fA2=(S2,Σ,δ2,q2,F2). Then S2=Σ*/≡, q2=[λ], and F2 consists of all [u] such that u∈L(A1). As a result, u∈L(A2) iff δ2([λ],u)=δ2(q2,u)∈F2 iff [u]=δ2([u],λ)∈F2 iff u∈L(A1). This shows that A1 is equivalent to A2.
To show A1 is isomorphic to A2, define ϕ:S2→S1 by ϕ([u])=δ1(q1,u). Then
- •
ϕ is well-defined by the definition of ≡, and it is injective - •
ϕ(q2)=ϕ([λ])=δ1(q1,λ)=q1. - •
ϕ([u])∈F1 iff δ1(q1,u)∈F1 iff u∈L(A1)=L(A2) iff [u]∈F2. Therefore, ϕ(F2)=F1. - •
Finally, ϕ(δ2([u],a))=ϕ([ua])=δ1(q1,ua)=δ1(δ1(q1,u),a)=δ1(ϕ([u]),a).
Thus, ϕ is a homomorphism from A1 to A2, together with the fact that ϕ is a bijection, A1 is isormorphic to A2. ∎
Proposition 2.
If ≡ is the Nerode equivalence of R, then the f(≡) is a reduced automaton. If A is reduced, then g(A) is the Nerode equivalence of R.
Proof.
Suppose ≡ is the Nerode equivlance. If f(≡) is not reduced, reduce it to a reduced automaton A. Then ≡⊆g(A). Since g(A) satisfies the two conditions above and ≡ is the largest such relation, ≡=g(A). Therefore f(≡)=f(g(A)) is isomorphic to A. But A is reduced, so must f(≡).
On the other hand, suppose A is reduced. Then g(A)⊆𝒩R. Conversely, if u𝒩Rv, then uw∈R iff vw∈R for any word w, so that δ(q0,uw)=δ(q0,vw), or δ(δ(q0,u),w)=δ(δ(q0,v),w), which implies δ(q0,u) and δ(q0,v) are indistinguishable. But A is reduced, this means δ(q0,u)=δ(q0,v). As a result ug(A)v, or g(A)=𝒩R. ∎
Definition. A Myhill-Nerode relation for R⊆Σ* 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 R is regular
iff its Nerode equivalence is a Myhill-Nerode relation, which is the essence of Myhill-Nerode theorem.