Minimal automaton

EQUIVALENCE OF WORDS MODULO A LANGUAGE. Let L $\subseteq$ $\Sigma^{{\ast}}_{{}}$ be a language over the alphabet $\Sigma$. Let u, v $\in$ $\Sigma^{{\ast}}_{{}}$ be two words (that may belong or not to the language L). We say that the language L SEPARATES u et v if

$$\left\{\vphantom{ \begin{array}{l} u \in L \\ v \not\in L \end{array} }\right. \begin{array}{l} u \in L \\ v \not\in L \end{array} \left\{\vphantom{ \begin{array}{l} u \not\in L \\ v \in L \end{array} }\right. \begin{array}{l} u \not\in L \\ v \in L \end{array}$$ (14)

We say that u et v are equivalent modulo L and we write u $\equiv$ v mod L if for every w $\in$ $\Sigma^{{\ast}}_{{}}$ the language L does not separate the words u w and v w. In other words we have

$$\equiv \iff \forall \in \Sigma^{{\ast}}_{{}} \left(\vphantom{ u \, w \in L \ \ \iff \ \ v \, w \in L }\right. \in \iff \in \left.\vphantom{ u \, w \in L \ \ \iff \ \ v \, w \in L }\right)$$ (15)

The relation u $\equiv$ v mod L is an equivalence relation (since it is reflexive, symmetric and transitive) and thus defines equivalence classes called the equivalence classes (or residue classes) associated with L.

EQUIVALENCE OF WORDS MODULO AN AUTOMATON. Let $\cal {A}$ = ($\Sigma$, S, i, F,$\delta$) be a DFA. Let u, v $\in$ $\Sigma^{{\ast}}_{{}}$ be two words We say that u et v are equivalent modulo $\cal {A}$ and we write u $\equiv$ v mod $\delta$ if after reading u the DFA is in the same state than after reading v. Let us denote by $\delta$(i, u) and $\delta$(i, v) the state of the automaton $\cal {A}$ after reading u and v respectively. Then we have

$$\equiv \delta \iff \delta \delta$$ (16)

Again the relation u $\equiv$ v mod $\delta$ is an equivalence relation and thus defines residue classes associated with the automaton $\cal {A}$.

Example 6   The DFA over $\Sigma$ = {a, b} on Figure 20 has three residue classes:

• that of the words with no a,
• that of the words with no b after an a,
• that of the words with a factor ab.

Figure 20: A DFA whith three classes of equivalence.

Proposition 8   Let L $\subseteq$ $\Sigma^{{\ast}}_{{}}$ be a language over $\Sigma$ recognized by the DFA $\cal {A}$ = ($\Sigma$, S, i, F,$\delta$). For every words u and v we have

$$\equiv \delta \Longrightarrow \equiv$$ (17)

Remark 4   Proposition 8 expresses the fact that every residue class modulo the automaton $\cal {A}$ is entirely contained in a residue class modulo its associated language L. Therefore the number of classes modulo L is upper bounded by the number of classes modulo $\cal {A}$ and thus by the number of states of $\cal {A}$. It follows from the following theorem that having a finite number of residue classes is a necessary and sufficient condition for a language to be recognized by FA.

Theorem 4   Let L $\subseteq$ $\Sigma^{{\ast}}_{{}}$ be a language over the alphabet $\Sigma$. Let n be a positive integer. If there exist exactly n residue classes modulo L then there exists a DFA with n states that recognizes L.

MINIMAL AUTOMATON. Let L $\subseteq$ $\Sigma^{{\ast}}_{{}}$ be a language over the alphabet $\Sigma$

• recognized by FA and
• with n residue classes.

It follows from Proposition 8 and Theorem 4 that

• every DFA recognizing L has at least n states,
• there exists a DFA with n states recognizing L.

Therefore we can call minimal automaton every DFA with n states and recognizing L.

Remark 5   The number of residue classes of a language is rarely known (until one gets a minimal DFA accepting this language). So one needs a way to characterize minimal automata.

Then one needs an algorithm to compute from a given DFA (minimal or not) recognizing L a minimal automaton recognizing L too. Such an algorithm will group states that do essentially the same job. This leads to the following notions.

EQUIVALENCE OF STATES IN A DFA. Let $\cal {A}$ = ($\Sigma$, S, i, F,$\delta$) be a DFA. We say that two states p, q $\in$ S are equivalent and we write p $\equiv$ q if for every word w $\in$ $\Sigma^{{\ast}}_{{}}$ we have

$$\delta \in \iff \delta \in$$ (18)

Let k be a non-negative integer. We say that two states p, q $\in$ S are equivalent at order k and we write p $\equiv_{{k}}^{{}}$ q if for every word w $\in$ $\Sigma^{{\ast}}_{{}}$ with length | w |

$$\left(\vphantom{\mid w \mid \leq k }\right. \leq \left.\vphantom{\mid w \mid \leq k }\right) \Longrightarrow \left(\vphantom{ ({\delta}(p,w) \in F) \ \ \iff \ \ ({\delta}(q,w) \in F) }\right. \delta \in \iff \delta \in \left.\vphantom{ ({\delta}(p,w) \in F) \ \ \iff \ \ ({\delta}(q,w) \in F) }\right)$$ (19)

CHARACTERIZATION OF A MINIMAL AUTOMATON. Among other properties, Theorem 5 states that for a minimal automaton, each residue class of states contains only one state.

Theorem 5   Let L $\subseteq$ $\Sigma^{{\ast}}_{{}}$ be a language recognized by FA and let n be its number of residue classes. Let $\cal {A}$ = ($\Sigma$, S, i, F,$\delta$) be a minimal DFA recognizing L. Then we have the following properties

• for every words u, v $\in$ $\Sigma^{{\ast}}_{{}}$ we have u $\equiv$ v mod $\delta$  $\iff$  u $\equiv$ v mod L.
• for every q $\in$ F there exists a word u $\in$ $\Sigma^{{\ast}}_{{}}$ such that $\delta$(i, u) = q.
• for every states p, q $\in$ S we have p $\equiv$ q  $\iff$  p = q.

CONSTRUCTION OF THE EQUIVALENCE CLASSES FOR STATES. Proposition 9 suggests an algorithm for constructing the equivalence classes of states.

Proposition 9   Let $\cal {A}$ = ($\Sigma$, S, i, F,$\delta$) be a DFA and k be a non-negative integer. If the relations $\equiv_{{k}}^{{}}$ and $\equiv_{{{k+1}}}^{{}}$ have the same residue classes then $\equiv_{{k}}^{{}}$ and $\equiv$ have the same residue classes too.

The method is follows.

• Compute $\equiv_{{0}}^{{}}$ which consists of two classes:
  • the set of the final states,
  • the set of the non final states.
• Compute $\equiv_{{1}}^{{}}$ and set k to 0
• Whhile $\equiv_{{k}}^{{}}$ and $\equiv_{{{k+1}}}^{{}}$ are different $\equiv_{{{k+2}}}^{{}}$ and set k to k + 1.

In practice one construct a table that gives the transition from each state after reading any word of length 0, any word of length 1, any word of length 2, etc... In these tables we underline final states in order to detect classes more easily. Quite often computations can be simpler. For instance, in Example 7 computations can be stopped after computing the third column. Explain why!

THE CONSTRUCTION OF A MINIMAL AUTOMATON $\overline{{{\cal A}}}$ = ($\Sigma$, S', i', F',$\delta$^$\prime$) from a given DFA $\cal {A}$ = ($\Sigma$, S, i, F,$\delta$) can be down as follows (where the class of a state s $\in$ S is denoted by $\overline{{s}}$).

• Compute the equivalence classes of states. From Theorem 5 they provide S', also denoted by $\overline{{S}}$.
• Let s, s' $\in$ S such that $\overline{{s}}$ = $\overline{{s'}}$. Let x $\in$ $\Sigma$. We have $\overline{{{\delta}(s,x)}}$ = $\overline{{{\delta}(s',x)}}$. Hence we can define $\delta$^$\prime$($\overline{{s}}$, x) as

  $$\delta \prime \overline{{s}} \overline{{{\delta}(s',x)}}$$ (20)

  
  

• We choose i'  =  $\overline{{i}}$.
• We define F'  =  {$\overline{{s}}$  |  s $\in$ F}.

Example 7  

Figure 21: A DFA whith three classes of equivalence.

$$\varepsilon$$	a	b	aa	ab	ba	bb
1	2	1	2	1	2	1
2	2	$$\underline{{3}}$$	2	$$\underline{{3}}$$	$$\underline{{4}}$$	$$\underline{{3}}$$
$$\underline{{3}}$$	$$\underline{{4}}$$	$$\underline{{3}}$$	$$\underline{{4}}$$	$$\underline{{4}}$$	$$\underline{{4}}$$	$$\underline{{3}}$$
$$\underline{{4}}$$	$$\underline{{4}}$$	$$\underline{{3}}$$	$$\underline{{4}}$$	$$\underline{{4}}$$	$$\underline{{4}}$$	$$\underline{{3}}$$

Figure 22: Minized automaton.

Example 8  

$$\varepsilon$$	a	b	aa	ab	ba	bb
1	2	6	7	$$\underline{{3}}$$	$$\underline{{3}}$$	7
2	7	$$\underline{{3}}$$
$$\underline{{3}}$$	1	$$\underline{{3}}$$	2	6	1	$$\underline{{3}}$$
5	8	6	7	$$\underline{{3}}$$	$$\underline{{3}}$$	7
6	$$\underline{{3}}$$	7	1	$$\underline{{3}}$$	7	$$\underline{{3}}$$
7	7	5	7	5	8	6
8	7	$$\underline{{3}}$$

Figure 23: Another DFA to minize.

Figure 24: Minized Automaton.