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 ${\mathcal{N}}_{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 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 $\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 ({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 {\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 {\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 MyhillNerode relation, which is the essence of MyhillNerode theorem.
Title  constructing automata from regular languages 

Canonical name  ConstructingAutomataFromRegularLanguages 
Date of creation  20130322 19:02:09 
Last modified on  20130322 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  MyhillNerode relation 