# 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$,

• $u\equiv v$ implies that $u\in R$ iff $v\in R$.

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 well-defined, 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}\;\lx@stackrel{{\scriptstyle f}}{{\mapsto}}A\lx@stackrel{{% \scriptstyle 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})\lx@stackrel{{\scriptstyle g}}{{% \mapsto}}\;\equiv\;\lx@stackrel{{\scriptstyle 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 well-defined 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 Myhill-Nerode relation for $R\subseteq\Sigma^{*}$ is an equivalence relation $\equiv$ that satisfies the two conditions above, and that $\Sigma^{*}/\equiv$ 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.

Title constructing automata from regular languages ConstructingAutomataFromRegularLanguages 2013-03-22 19:02:09 2013-03-22 19:02:09 CWoo (3771) CWoo (3771) 11 CWoo (3771) Definition msc 03D10 msc 68Q42 msc 68Q05 Myhill-Nerode relation