constructing automata from regular languages


In this entry, we describe how a certain equivalence relationMathworldPlanetmath on words gives rise to a deterministic automaton, and show that deterministicMathworldPlanetmath automata to a certain extent can be characterized by these equivalence relations.

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:

  • is a right congruenceMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath: if uv, then uwvw for any word w over Σ,

  • uv implies that uR iff vR.

An example of this is the Nerode equivalence 𝒩R of R (in fact, the largest such relationMathworldPlanetmathPlanetmathPlanetmath).

We can construct an automaton A=(S,Σ,δ,I,F) based on . Here’s how:

  • S=Σ*/, the set of equivalence classesMathworldPlanetmath of ; 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 wordPlanetmathPlanetmathPlanetmath λ,

  • F is the set consisting of [u], where uR.

By condition 1, δ is well-defined, so A is a deterministic automaton. By the second condition above, [u]F iff uR.

By inductionMathworldPlanetmath, we see that δ([u],v)=[uv] for any word v over Σ. So

uv  iff  δ([u],λ)=δ([v],λ).

One consequence of this is that A is accessiblePlanetmathPlanetmath (all states are accessible).

In additionPlanetmathPlanetmath, R=L(A), as uL(A) iff δ([λ],u)F iff [u]F iff uR.

Constructing the equivalence relation

Conversely, given a deterministic automaton A=(S,Σ,δ,{q0},F), a binary relation on Σ* may be defined:

uv  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 uL(A) iff vL(A).

So [u]={vSδ(q0,v)=δ(q0,u)}.

Remark. We could have defined the binary relation uv to mean δ(q,u)=δ(q,v) for all qS. 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 uv, then δ(q,wu)=δ(δ(q,w),u)=δ(δ(q,w),v)=δ(q,wv) so that wuwv. In this entry, only the weaker assumptionPlanetmathPlanetmath 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:XY and g:YX such that f() and g(A) are the automaton and relation constructed above.

Proposition 1.

gf=1X and f(g(A)) is isomorphicPlanetmathPlanetmathPlanetmath to A.

Proof.

Suppose 1fAg2. Then u1v iff δ([u],λ)=δ([v],λ) iff δ([λ],u)=δ([λ],v) iff u2v.

Conversely, suppose A1=(S1,Σ,δ1,q1,F2)gfA2=(S2,Σ,δ2,q2,F2). Then S2=Σ*/, q2=[λ], and F2 consists of all [u] such that uL(A1). As a result, uL(A2) iff δ2([λ],u)=δ2(q2,u)F2 iff [u]=δ2([u],λ)F2 iff uL(A1). This shows that A1 is equivalentMathworldPlanetmathPlanetmathPlanetmath to A2.

To show A1 is isomorphic to A2, define ϕ:S2S1 by ϕ([u])=δ1(q1,u). Then

  • ϕ is well-defined by the definition of , and it is injectivePlanetmathPlanetmath for the same reason. Now, let sS, then since A1 is accessible, there is a word u such that δ1(q1,u)=s, so that ϕ([u])=s. This shows that ϕ is a bijection.

  • ϕ(q2)=ϕ([λ])=δ1(q1,λ)=q1.

  • ϕ([u])F1 iff δ1(q1,u)F1 iff uL(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 homomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 uwR iff vwR 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 languagePlanetmathPlanetmath R is regularPlanetmathPlanetmath 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