Algorithms on 
Finite Automata

Part II. Minimization and Boolean Operations

by Jaime Rangel Mondragón

Facultad de Informática
Universidad Autónoma de Querétaro
División de Estudios de Posgrado

Centro Universitario
Cerro de las Campanas s/n
C.P. 76010 Querétaro, Qro.
Mexico

jrangel@sunserver.uaq.mx

Copyright  ©1999, UAQ, Facultad de Informática

This is the second of four parts on the implementation of algorithms on FA. To activate the different functions comprising the previous part, open it and choose the Kernel-Evaluate-Evaluate Initialization menu path. Do the same for this folder.

7 MINIMIZATION OF AUTOMATA

Minimizing FA is a crucial step in any manipulation of automata. The amount of redundant states proliferates as we apply boolean operations on them and so its use will be fully  required at section 8. It has beeen proved that there is a unique minimum state FA corresponding to any FA (Myhill-Nerode theorem) and this correspondence will be profitable in the counting of automata we perform in the fourth part.

7.1 Innaccesible states removal

Firstly, we remove inaccesible states, i.e., those reachable from the initial state: We use the "blue paint" technique, which consists in painting the inital state blue and transmiting  the paint to adjacent states. The coloring of a state is accomplish by negating its label. After the removal of inaccesible states, a renumbering of states is done so that the labels remain consecutive. Note that the final automaton might not accept any word.

\(connected[{δ_, F_}] := 
      Module[{nStates = First[Dimensions[δ]], s, i, f1, 
          δ1 = δ, z}, 
		s = Range[2, nStates]; 
		
        PrependTo[s, \(-1\)]; 
		
        While[\((
              i = Select[s, 
                  Negative[#]\  && \ 
                      Or\ @@\ Positive[
                          s[[δ[[\(-#\)]]]]]&, 1])\) ≠ {}, 

          			Map[
            \((s[[#]] = 
                  \(-Abs[s[[#]]]\))\)&, 
            δ[[\(-First[i]\)]]]]; 
        
	
		f1 = \(-\((\(-F\)\  ⋂ \ s)\)\); 
	\ \ 
        δ1 = 
          δ1
            [[\(-
              Select[s, Negative]\)]]; 
		
		z = 0; 
        
		Map[
          If[Positive[#], \ \(z++\), 
				
              δ1 = δ1\  /. \ \(-#\) -> \(-#\) - z; 

              				f1 = f1\  /. \ \ \(-#\) -> \(-#\) - z]&, s]; 

        		{δ1, f1}]\)

showFA[connected[{(({{3, 4}, {3, 4}, {3, 8}, {3, 8}, {3, 4}, {3, 4}, {3, 8}, {8, 8}})),{8}}]]

m={(({{3, 1}, {2, 4}, {1, 3}, {2, 4}})),{2, 3, 4}};
drawFA[m];
drawFA[connected[m]]

7.2 Classes of equivalent states

Then we compute the classes to which the equivalent states belong and from which we will select a representative.

\(classes[{δ_, F_}] := 
      Module[{n, alphSize, i, j, pairs, lv}, 

        			{n, alphSize} = Take[Dimensions[δ], 2]; 
		
        pairs = Flatten[Table[{i, j}, {i, n - 1}, {j, i + 1, n}], 1]; \ 
		
        pairs = Select[pairs, 
            Not[\((MemberQ[F, First[#]] && \ \(! MemberQ[F, Last[#]]\)\ )
                    \) || \ \((
                    \(! MemberQ[F, First[#]]\)\  && \ MemberQ[F, Last[#]])
                    \)]&]; 

		
        pairs = FixedPoint[#\  //. 
                \ {a___, {p_, q_}, b___}\  /; \ 
                    \(! And\ @@\ 
                        Table[\((
                              δ[[p, i
                                  ]] == 
                                δ[[q, i
                                  ]])\) || \ 
                            MemberQ[#, 
                              Sort[{δ[[p, i
                                    ]], 
                                  δ[[q, i
                                    ]]}]], {i, alphSize}]
                          \)\  -> {a, b}&, \ pairs]; \ 
		
        pairs = Join[pairs, Map[{#, #}&, Range[n]]]; 

		
        lv = {h, a, x, b, u, p, q, t}; 
		Clear[h, a, x, b, u, p, q, t]; 

        		pairs = 
          pairs\  //. 
            \ {h___, {a___, x_, b___}, u___, {p___, x_, q___}, t___} 
              -> {h, {a, x, b, p, q}, u, t}; 

        		{h, a, x, b, u, p, q, t} = lv; 
		
        Sort[Map[Union, pairs, 1], First[#2] > First[#1]&]]\)

classes[{(({{11, 2}, {3, 1}, {4, 7}, {6, 5}, {12, 4}, {4, 12}, {8, 9}, {12, 2}, {10, 7}, {6, 1}, {5, 9}, {5, 6}})),(({{1}, {4}, {5}, {6}, {8}, {12}}))}]

m1={(({{2, 6}, {7, 3}, {1, 3}, {3, 7}, {8, 6}, {3, 7}, {7, 5}, {7, 3}})),{3}};
classes[m1]

m2={(({{2, 3}, {1, 4}, {5, 6}, {5, 6}, {5, 6}, {6, 6}})),{3, 4, 5}};
classes[m2]

m3={(({{2, 1}, {1, 3}, {4, 2}, {4, 1}, {4, 6}, {7, 5}, {6, 7}, {7, 4}})),{4}};
classes[m3]

m4={(({{2, 6}, {1, 6}, {7, 1}, {8, 2}, {1, 7}, {8, 3}, {1, 4}, {1, 3}})),{6, 7, 8}};
classes[m4]

m5={(({{6, 2}, {4, 3}, {7, 2}, {5, 1}, {4, 1}, {1, 7}, {3, 8}, {1, 8}})),{4, 6, 7, 8}};
classes[m5]

7.3 Minimization

\(minimize[automaton_] := 
      Module[{m = connected[automaton], c, d, f, i}, 
		c = classes[m]; \ 
        
		{d, f} = m; 
		
        d = d[[First\ /@\ c]]; 
		
        Do[
			
          Map[\((d = d\  /. \ # -> i; f = f\  /. \ # -> i; )\)&, 
            c[[i]]], {i, Length[c]}]; 

        		{d, Union[f]}]\)

showFA[minimize[{(({{2, 1}, {3, 1}, {3, 3}})),(({{1}, {2}, {3}}))}]]

showFA[minimize[{(({{11, 2}, {3, 1}, {4, 7}, {6, 5}, {12, 4}, {4, 12}, {8, 9}, {12, 2}, {10, 7}, {6, 1}, {5, 9}, {5, 6}})),(({{1}, {4}, {5}, {6}, {8}, {12}}))}]]

showFA[minimize[{(({{3, 4}, {3, 4}, {3, 8}, {3, 8}, {3, 4}, {3, 4}, {3, 8}, {8, 8}})),{8}}]]

The following examples refer to the FA introduced at section 7.2 above.

drawFA[m1]drawFA[minimize[m1]]

drawFA[m2]drawFA[minimize[m2]]

drawFA[m3]drawFA[minimize[m3]]

drawFA[m4]drawFA[minimize[m4]]

drawFA[m5]drawFA[minimize[m5]]

8 OPERATIONS ON AUTOMATA

According to Kleene´s theorem, regular languages are closed under boolean operations, juxtaposition and the Kleene star operation. In the following we design these operators.

8.1 Complement

compl[{δ_, F_}] := {δ, 
        Complement[Range[Length[δ]], F]}

mod5compl[mod5]

8.2 Parallel (OR) Connection

\(parallel[{δ1_, F1_}, {δ2_, F2_}] := 
      Module[{f, s, currentRow, newStates = {{1, 1}}, m = {}, t, final}, 

        		While[newStates ≠ {}, 

          								{f, s} = First[newStates]; 
								
          currentRow = 
            Thread[{δ1[[f]], 
                δ2[[s]]}]; 

          								AppendTo[m, {{f, s}, currentRow}]; 

          								
          newStates = Complement[Join[newStates, currentRow], First\ /@\ m]]; 
        

		newStates = First\ /@\ m; 
		
        final = Map[\((MemberQ[F1, First[#]]\  || \ MemberQ[F2, Last[#]])\)&, 
            newStates]; 
		final = Flatten[Position[final, True]]; 
		
        t = Thread[\((#1 -> #2&)\)[newStates, Range[Length[m]]]]; 
		
        minimize[{\((Last\ /@\ m)\)\  /. \ t, \ final}]]\)

drawFA[parallel[aa, evenEven]]

drawFA[parallel[dif, aa]]

drawFA[parallel[aa, compl[aa]]]

8.3 Intersection

intersec[A1_, A2_] := compl[parallel[compl[A1], compl[A2]]]

intersec[aa, compl[aa]]

drawFA[intersec[aa, evenEven]]

drawFA[intersec[aa, dif]]

8.4 Difference

difference[A1_, A2_] := intersec[A1, compl[A2]]

drawFA[difference[aa, oddA]]

8.5 Equivalence

equivalentQ[A1_, A2_] := 
      (Last[difference[A1, A2]] == {})  &&  
        (Last[difference[A2, A1]] == {})

equivalentQ[aa, parallel[aa, aa]]

equivalentQ[intersec[aa, dif], {{{2, 1}, {1, 1}}, {}}]

(Actually, it is faster to use acceptedWords on both automata and compare.)

8.6 Juxtaposition (Serial) Connection

\(serial[m1_, m2_] := 
	
      Module[{δ1, F1, δ2, F2, nStates, m, newM = {}, newRow, 
          s}, 
		{δ1, F1} = m1; 
		{δ2, F2} = m2; 
		
        nStates = First[Dimensions[δ1]]; 

        		{δ2, F2} = {δ2, F2}\  /. \ 
            x_Integer -> x + nStates; 

        		{δ1, δ2} = {δ1, δ2}\  /. 
            x_Integer -> {x}; 
		
        δ1 = 
          δ1\  /. \ Map[\(({#} -> {#, nStates + 1})\)&, F1]\ ; 

        		m = Join[δ1, δ2]\ ; 

		
        s = {If[MemberQ[F1, 1], {1, nStates + 1}, {1}]}; \ 
		
        While[\ s ≠ {}, 
			s = First[s]; 
			
          AppendTo[newM, \ 
            Join[{s}, 
              \(Union[Flatten[#]]&\)\ /@\ 
                Thread[m[[s]]]]]; 

          			s = 
            Select[Flatten[newM, 1], Not[MemberQ[First\ /@\ newM, #]]&, 1]]; 
        
		
		
        s = Select[First\ /@\ newM, 
            \((# ⋂ F2 ≠ {})\)&]; 

        		{δ1, s} = {Rest\ /@\ newM, s}\  /. \ 
            Thread[\(\((#1 -> #2)\)&\)[First\ /@\ newM, 
                Range[Length[newM]]]]; 
		\ 
		minimize[{δ1, s}]]
        \)

\(m1 = {{{2, 1}, {3, 1}, {3, 3}}, {3}}; 
m2 = {{{1, 2}, {1, 2}}, {2}}; 

    showFA[serial[m1, m2]]\)

drawFA[serial[aa, dif]]

8.7 Kleene´s star Operation

\(kleene[m_] := 
      Module[{δ, F, nStates, newM = {}, newRow, s = {{1}}}, 

        		{δ, F} = m; 
		F = Select[F, # > 1&]; 
		
        nStates = First[Dimensions[δ]]; 
		
        δ = δ\  /. x_Integer -> {x}; 
		
        δ = δ\  /. \ Map[\(({#} -> {#, 1})\)&, F]\ ; 
		
        
		While[\ s ≠ {}, 
			s = First[s]; 
			
          AppendTo[newM, \ 
            Join[{s}, 
              \(Union[Flatten[#]]&\)\ /@\ 
                Thread[δ[[s]]]]]; 
          
			s = 
            Select[Flatten[newM, 1], Not[MemberQ[First\ /@\ newM, #]]&, 1]]; 
        
		
		
        s = Select[First\ /@\ newM, 
            \((# ⋂ F ≠ {})\)&]; 

        		{δ, s} = {Rest\ /@\ newM, s}\  /. \ 
            Thread[\(\((#1 -> #2)\)&\)[First\ /@\ newM, 
                Range[Length[newM]]]]; 
		\ 
		
        minimize[{
            If[MemberQ[Last[m], 1], δ, 

              			{δ, s} = {δ, s}\  /. 
                  x_Integer -> x + 1; 
			
              Join[{First[δ]}, δ]], Join[{1}, s]}]]\)

showFA[kleene[{{{2, 2, 2}, {2, 2, 2}}, {2}}]]

showFA[kleene[{{{2, 4}, {2, 3}, {4, 4}, {4, 4}}, {1, 2, 3}}]]

showFA[kleene[{{{2, 4}, {2, 3}, {4, 4}, {4, 4}}, {2, 3}}]]

showFA[kleene[{{{2, 3}, {2, 4}, {3, 3}, {3, 4}}, {4}}]]

showFA[kleene[oddA]]

equivalentQ[evenEven, kleene[evenEven]]

equivalentQ[secondB, kleene[secondB]]

equivalentQ[evenEvenABC, kleene[evenEvenABC]]

equivalentQ[aa, kleene[aa]]

equivalentQ[oddA, kleene[oddA]]

showFA[kleene[dif]]

showFA[kleene[mod5]]

showFA[kleene[difABC]]

showFA[kleene[evenEvenABC]]

drawFA[modMxN[3, 1, 3]]drawFA[kleene[modMxN[3, 1, 3]]]

9 TREE AUTOMATA

Tree automata are those that do not possess loops. Function wordsFA below construct a particular FA of this family. Given a list of words and the size of the alphabet we are working with, it delivers an FA which only accepts the given words.  The word  "ε" means the null word, which can also be entered as "". Note that the lists {} and {"ε"} are different and that the FA is minimized before delivery.

\(wordsFA[{}, alphSize_] := {Table[1, {alphSize}], {}}
\)\(wordsFA[{"ε"}, alphSize_] := {
        Table[2, {2}, {alphSize}], {1}}
\)\(wordsFA[{a_String, b__}, alphSize_] := 
      parallel[wordsFA[{a}, alphSize], wordsFA[{b}, alphSize]]
\)\(wordsFA[{a_String}, alphSize_] := 
      Module[{
		nStates = StringLength[a] + 2, c = Characters[a], i, m}, 
        
	
		
        m = Partition[Table[nStates, {alphSize\ nStates}], alphSize]; 
		

        		Do[
			
          m[[i, 
              ToCharacterCode[c[[i]]] - 
                ToCharacterCode["a"] + 1]] = i + 1, {
            i, Length[c]}]; \ 
		minimize[{m, {nStates - 1}}]]\)

showFA[wordsFA[{""}, 3]]

showFA[wordsFA[{"ε"}, 3]]

drawFA[wordsFA[{"a"}, 2]]

drawFA[wordsFA[{"a", "aa"}, 2]]

showFA[wordsFA[{"a", "b"}, 2]]

showFA[wordsFA[{"a", "aa", "ab", "ba", "bb"}, 2]]

showFA[kleene[wordsFA[{"a", "b"}, 2]]]

\(m = 
      serial[kleene[wordsFA[{"a", "b"}, 2]], 
        serial[wordsFA[{"aa"}, 2], 
          kleene[wordsFA[{"a", "b"}, 2]]]]; 
equivalentQ[aa, m]\)

9.1 PREFIX AUTOMATA

Prefix automata are members of the family of tree automata. Given a lists of words and the size of the working alphabet, a prefix FA is that which accepts only those words starting with a member of the given list.

\(prefixFA[{"ε"}, alphSize_] := {
        Table[1, {1}, {alphSize}], {1}}
\)\(prefixFA[{a_String, b__}, alphSize_] := 
      parallel[prefixFA[{a}, alphSize], prefixFA[{b}, alphSize]]
\)\(prefixFA[{a_String}, alphSize_] := 
      Module[{
		nStates = StringLength[a] + 2, c = Characters[a], i, m}, 
        
	
		
        m = Partition[Table[nStates, {alphSize\ nStates}], alphSize]; 
		

        		Do[m[[i, 
              ToCharacterCode[c[[i]]] - 
                ToCharacterCode["a"] + 1]] = i + 1, {
            i, Length[c]}]; 
			
        m = ReplacePart[m, 
            m[[\(-2\)]] - 1, \(-2\)]; 

        		minimize[{m, {nStates - 1}}]]\)

drawFA[prefixFA[{""}, 2]]

drawFA[prefixFA[{"a"}, 2]]

drawFA[prefixFA[{"ab", "ba"}, 2]]

drawFA[prefixFA[{"aa", "ab", "ba", "bb"}, 2]]

drawFA[prefixFA[{"a", "aa", "ab", "aaa"}, 2]]

this FA must be the same as:

drawFA[prefixFA[{"a", "aaa"}, 2]]

10 SUFFIX AUTOMATA

Suffix FA are the reverse of prefix FA. Given a list of words and the size of the working alphabet, function suffixFA below will construct an FA accepting only those words ending with one (or more) of the given words and acting over an alphabet of given size. To this end we need to precompute the failure function of a word. Note there is no need to minimize the suffix automata.

\(failure[w_String] := 
      Module[{c, i, u}, 
		
        c = Table[StringTake[w, i], {i, 2, StringLength[w]}]; 
		
		
        Join[{0}, 
          Map[\((i = StringLength[#] - 1; 
					
                While[\((i > 0)\) && 
                    Not[StringMatchQ[#, "*"<>StringTake[#, i]]], 
                  \(i--\)]; 
				i)\)&, c]]]\)

failure["aabbaab"]

\(suffixFA[{a_String, b__}, alphSize_] := 
      parallel[suffixFA[{a}, alphSize], suffixFA[{b}, alphSize]]
\)suffixFA[{"ε"}, alphSize_] := {
        Table[1, {1}, {alphSize}], {1}}suffixFA[{""}, alphSize_] := {Table[1, {1}, {alphSize}], {1}}\(suffixFA[{a_String}, alphSize_] := 
      Module[{
		nStates = StringLength[a] + 1, c = Characters[a], i, j, 
          k, m, f = failure[a]}, 
	
		
        m = Partition[Table[1, {alphSize\ nStates}], alphSize]; 
		
		
        Do[\ 
			
          k = ToCharacterCode[c[[i]]] - 
              ToCharacterCode["a"] + 1; 
			
          m[[i, k]] = i + 1, 

          			{i, nStates - 1}]; 
	
		
        Do[
			
          k = ToCharacterCode[c[[i]]] - 
              ToCharacterCode["a"] + 1; 
			
          Do[
				
            If[{j} ≠ k, 
              m[[i, j]] = 
                m[[f
                      [[i - 1]] + 1, j
                  ]]], {j, alphSize}], 		

          			{i, 2, \ nStates - 1}]; 
		
		
        Do[
			
          m[[nStates, j]] = 
            m[[f
                  [[nStates - 1]] + 1, j
              ]], {j, alphSize}]; 
		{m, {nStates}}]
        \)

drawFA[suffixFA[{"aabbaab"}, 2]]

drawFA[suffixFA[{"abcabcab"}, 3]]

\(m = 
      serial[kleene[wordsFA[{"a", "b"}, 2]], wordsFA[{"aa"}, 2]]; 
    
equivalentQ[m, suffixFA[{"aa"}, 2]]\)

10.1 FRAME AUTOMATA

Combining the characteristics of prefix and suffix automata we construct frame FA as shown below

frameFA[pref_, suff_, alphSize_] := 
      intersec[prefixFA[pref, alphSize], suffixFA[suff, alphSize]]

drawFA[frameFA[{"a"}, {"b"}, 2]]Table[acceptedWords[frameFA[{"a"}, {"b"}, 2], i], {i, 4}]

Finally, let us show how to design an FA m that accepts only those words that begin with a or end in bab but not both.

\(m1 = parallel[prefixFA[{"a"}, 2], suffixFA[{"bab"}, 2]]; 

    Table[acceptedWords[m1, i], {i, 4}]\)\(m2 = frameFA[{"a"}, {"bab"}, 2]; 

    Table[acceptedWords[m2, i], {i, 6}]\)\(m = difference[m1, m2]; 
Table[acceptedWords[m, i], {i, 4}]		\)drawFA[m]