You are here
Homeconstructing automata from regular languages
Primary tabs
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 $\Sigma$ be an alphabet and $R$ a subset of $\Sigma^{*}$, the set of all words over $\Sigma$. Consider an equivalence relation $\equiv$ on $\Sigma^{*}$ satisfying the following two conditions:

$\equiv$ is a right congruence: if $u\equiv v$, then $uw\equiv vw$ for any word $w$ over $\Sigma$,
An example of this is the Nerode equivalence $\mathcal{N}_{R}$ of $R$ (in fact, the largest such relation).
We can construct an automaton $A=(S,\Sigma,\delta,I,F)$ based on $\equiv$. Here’s how:

$S=\Sigma^{*}/\equiv$, the set of equivalence classes of $\equiv$; elements of $S$ are denoted by $[u]$ for any $u\in\Sigma^{*}$,

$\delta:S\times\Sigma\to S$ is given by $\delta([u],a)=[ua]$,

$I$ is a singleton consisting of $[\lambda]$, the equivalence class consisting of the empty word $\lambda$,

$F$ is the set consisting of $[u]$, where $u\in R$.
By condition 1, $\delta$ is welldefined, so $A$ is a deterministic automaton. By the second condition above, $[u]\in F$ iff $u\in R$.
By induction, we see that $\delta([u],v)=[uv]$ for any word $v$ over $\Sigma$. So
$u\equiv v\qquad\mbox{iff}\qquad\delta([u],\lambda)=\delta([v],\lambda).$ 
One consequence of this is that $A$ is accessible (all states are accessible).
In addition, $R=L(A)$, as $u\in L(A)$ iff $\delta([\lambda],u)\in F$ iff $[u]\in F$ iff $u\in R$.
Constructing the equivalence relation
Conversely, given a deterministic automaton $A=(S,\Sigma,\delta,\{q_{0}\},F)$, a binary relation $\equiv$ on $\Sigma^{*}$ may be defined:
$u\equiv v\qquad\mbox{iff}\qquad\delta(q_{0},u)=\delta(q_{0},v).$ 
This binary relation is clearly an equivalence relation, and it satisfies the two conditions above, with $R=L(A)$:

$\delta(q_{0},uw)=\delta(\delta(q_{0},u),w)=\delta(\delta(q_{0},v),w)=\delta(q_% {0},vw)$,

if $\delta(q_{0},u)=\delta(q_{0},v)$, then clearly $u\in L(A)$ iff $v\in L(A)$.
So $[u]=\{v\in S\mid\delta(q_{0},v)=\delta(q_{0},u)\}$.
Remark. We could have defined the binary relation $u\equiv v$ to mean $\delta(q,u)=\delta(q,v)$ for all $q\in S$. This is also an equivalence relation that satisfies both of the conditions above. However, this is stronger in the sense that $\equiv$ is a congruence: if $u\equiv v$, then $\delta(q,wu)=\delta(\delta(q,w),u)=\delta(\delta(q,w),v)=\delta(q,wv)$ so that $wu\equiv wv$. In this entry, only the weaker assumption that $\equiv$ is a right congruence is needed.
Characterization
Fix an alphabet $\Sigma$ and a set $R\subseteq\Sigma^{*}$. Let $X$ the set of equivalence relations satisfying the two conditions above, and $Y$ the set of accessible deterministic automata over $\Sigma$ accepting $R$. Define $f:X\to Y$ and $g:Y\to X$ such that $f(\equiv)$ and $g(A)$ are the automaton and relation constructed above.
Proposition 1.
$g\circ f=1_{X}$ and $f(g(A))$ is isomorphic to $A$.
Proof.
Suppose $\equiv_{1}\;\stackrel{f}{\mapsto}A\stackrel{g}{\mapsto}\;\equiv_{2}$. Then $u\equiv_{1}v$ iff $\delta([u],\lambda)=\delta([v],\lambda)$ iff $\delta([\lambda],u)=\delta([\lambda],v)$ iff $u\equiv_{2}v$.
Conversely, suppose $A_{1}=(S_{1},\Sigma,\delta_{1},q_{1},F_{2})\stackrel{g}{\mapsto}\;\equiv\;% \stackrel{f}{\mapsto}A_{2}=(S_{2},\Sigma,\delta_{2},q_{2},F_{2})$. Then $S_{2}=\Sigma^{*}/\equiv$, $q_{2}=[\lambda]$, and $F_{2}$ consists of all $[u]$ such that $u\in L(A_{1})$. As a result, $u\in L(A_{2})$ iff $\delta_{2}([\lambda],u)=\delta_{2}(q_{2},u)\in F_{2}$ iff $[u]=\delta_{2}([u],\lambda)\in F_{2}$ iff $u\in L(A_{1})$. This shows that $A_{1}$ is equivalent to $A_{2}$.
To show $A_{1}$ is isomorphic to $A_{2}$, define $\phi:S_{2}\to S_{1}$ by $\phi([u])=\delta_{1}(q_{1},u)$. Then

$\phi$ is welldefined by the definition of $\equiv$, and it is injective for the same reason. Now, let $s\in S$, then since $A_{1}$ is accessible, there is a word $u$ such that $\delta_{1}(q_{1},u)=s$, so that $\phi([u])=s$. This shows that $\phi$ is a bijection.

$\phi(q_{2})=\phi([\lambda])=\delta_{1}(q_{1},\lambda)=q_{1}$.

$\phi([u])\in F_{1}$ iff $\delta_{1}(q_{1},u)\in F_{1}$ iff $u\in L(A_{1})=L(A_{2})$ iff $[u]\in F_{2}$. Therefore, $\phi(F_{2})=F_{1}$.

Finally, $\phi(\delta_{2}([u],a))=\phi([ua])=\delta_{1}(q_{1},ua)=\delta_{1}(\delta_{1}(% q_{1},u),a)=\delta_{1}(\phi([u]),a)$.
Thus, $\phi$ is a homomorphism from $A_{1}$ to $A_{2}$, together with the fact that $\phi$ is a bijection, $A_{1}$ is isormorphic to $A_{2}$. ∎
Proposition 2.
If $\equiv$ is the Nerode equivalence of $R$, then the $f(\equiv)$ is a reduced automaton. If $A$ is reduced, then $g(A)$ is the Nerode equivalence of $R$.
Proof.
Suppose $\equiv$ is the Nerode equivlance. If $f(\equiv)$ is not reduced, reduce it to a reduced automaton $A$. Then $\equiv\subseteq g(A)$. Since $g(A)$ satisfies the two conditions above and $\equiv$ is the largest such relation, $\equiv=g(A)$. Therefore $f(\equiv)=f(g(A))$ is isomorphic to $A$. But $A$ is reduced, so must $f(\equiv)$.
On the other hand, suppose $A$ is reduced. Then $g(A)\subseteq\mathcal{N}_{R}$. Conversely, if $u\mathcal{N}_{R}v$, then $uw\in R$ iff $vw\in R$ for any word $w$, so that $\delta(q_{0},uw)=\delta(q_{0},vw)$, or $\delta(\delta(q_{0},u),w)=\delta(\delta(q_{0},v),w)$, which implies $\delta(q_{0},u)$ and $\delta(q_{0},v)$ are indistinguishable. But $A$ is reduced, this means $\delta(q_{0},u)=\delta(q_{0},v)$. As a result $ug(A)v$, or $g(A)=\mathcal{N}_{R}$. ∎
Definition. A MyhillNerode relation for $R\subseteq\Sigma^{*}$ is an equivalence relation $\equiv$ that satisfies the two conditions above, and that $\Sigma^{*}/\equiv$ is finite.
Mathematics Subject Classification
03D10 no label found68Q42 no label found68Q05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections