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 $\mathrm{\Sigma }$ be an alphabet and $R$ a subset of ${\mathrm{\Sigma }}^{*}$, the set of all words over $\mathrm{\Sigma }$. Consider an equivalence relation $\equiv$ on ${\mathrm{\Sigma }}^{*}$ satisfying the following two conditions:

• $\equiv$ is a right congruence: if $u\equiv v$, then $uw\equiv vw$ for any word $w$ over $\mathrm{\Sigma }$,

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

An example of this is the Nerode equivalence ${𝒩}_R$ of $R$ (in fact, the largest such relation).

We can construct an automaton $A=(S,\mathrm{\Sigma },\delta ,I,F)$ based on $\equiv$. Here’s how:

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

• $\delta :S\times \mathrm{\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 $\mathrm{\Sigma }$. So

$$u\equiv v\mathit{\hspace{1em}\hspace{1em}}\text{iff}\mathit{\hspace{1em}\hspace{1em}}\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,\mathrm{\Sigma },\delta ,\{q_0\},F)$, a binary relation $\equiv$ on ${\mathrm{\Sigma }}^{*}$ may be defined:

$$u\equiv v\mathit{\hspace{1em}\hspace{1em}}\text{iff}\mathit{\hspace{1em}\hspace{1em}}\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 $\mathrm{\Sigma }$ and a set $R\subseteq {\mathrm{\Sigma }}^{*}$. Let $X$ the set of equivalence relations satisfying the two conditions above, and $Y$ the set of accessible deterministic automata over $\mathrm{\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\mathit{}\mathrm{(}g\mathit{}\mathrm{(}A\mathrm{)}\mathrm{)}$ 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,\mathrm{\Sigma },{\delta }_1,q_1,F_2)\stackrel{g}{\mapsto }\equiv \stackrel{f}{\mapsto }{A}_2=(S_2,\mathrm{\Sigma },{\delta }_2,q_2,F_2)$. Then $S_2={\mathrm{\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 $\varphi :S_2\to S_1$ by $\varphi ([u])={\delta }_1(q_1,u)$. Then

• $\varphi$ 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 $\varphi ([u])=s$. This shows that $\varphi$ is a bijection.

• $\varphi (q_2)=\varphi ([\lambda ])={\delta }_1(q_1,\lambda )=q_1$.

• $\varphi ([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, $\varphi (F_2)=F_1$.

• Finally, $\varphi ({\delta }_2([u],a))=\varphi ([ua])={\delta }_1(q_1,ua)={\delta }_1({\delta }_1(q_1,u),a)={\delta }_1(\varphi ([u]),a)$.

Thus, $\varphi$ is a homomorphism from $A_1$ to $A_2$, together with the fact that $\varphi$ is a bijection, $A_1$ is isormorphic to $A_2$.∎

Proposition 2.

If $\mathrm{\equiv }$ is the Nerode equivalence of $R$, then the $f\mathit{}\mathrm{(}\mathrm{\equiv }\mathrm{)}$ is a reduced automaton. If $A$ is reduced, then $g\mathit{}\mathrm{(}A\mathrm{)}$ 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 {𝒩}_R$. Conversely, if $u{𝒩}_{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)={𝒩}_R$.∎

Definition. A Myhill-Nerode relation for $R\subseteq {\mathrm{\Sigma }}^{*}$ is an equivalence relation $\equiv$ that satisfies the two conditions above, and that ${\mathrm{\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.