Algorithms on 
Finite Automata

Part I. Generating and Enumerating Words

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 first of four parts on the implementation of algorithms on finite automata (FA). To activate the different functions comprising this folder, choose the Kernel-Evaluation-EvaluateInitialization menu path.

REFERENCES

1 INTRODUCTION

A finite automaton (FA) is described by a 5-tuple M=(Q, Σ, δ, (Subscript[q, 0]), F), wherein Q is a finite set of states, ∑ is an alphabet, δ is the transition function δ: Q x Σ -> Q, (Subscript[q, 0])ϵQ is the initial state and F ⊆ Q is the set of final states. A word (string) made from elements in the alphabet is read one character at a time and forces the automaton to change states accordingly.
If a word  w = (Subscript[w, 1]) (Subscript[w, 2]) ⋯(Subscript[w, n])∈ \(TraditionalForm\`\(Σ\^*\)\) is such that δ(⋯δ(δ((Subscript[q, 0]),(Subscript[w, 1])),(Subscript[w, 2]))⋯,(Subscript[w, n]))∈F, we say that M accepts or recognizes w. FAs are used to accept regular languages, that is, an automaton will accept only those words belonging to a particular regular language. 
Consider, for example, the FA accepting the language \(TraditionalForm\`\(\((a + b)\)\^*\)\)aba. This automaton can be designed using four states. In Mathematica, we can directly input (Subscript[q, 0]),  δ and F as:

(Subscript[q, 0]) = 1;

δ[1, "a"] = 2;       δ[1, "b"] = 1;       
δ[2, "a"] = 2;       δ[2, "b"] = 3;    
δ[3, "a"] = 4;       δ[3, "b"] = 1;   
δ[4, "a"] = 2;       δ[4, "b"] = 3;    

F = {4};

We can test whether a given word is recognized by this automaton through function acceptedQ:

acceptedQ[w_String] := 
      MemberQ[F, Fold[δ, (Subscript[q, 0]), Characters[w]]]

acceptedQ["aabababa"]

We can also obtain the list of states traversed by the previous word in traversing the path to being accepted:

FoldList[δ, (Subscript[q, 0]), Characters["aabababa"]]

However, this notation, although correct, makes the input of automata awkward and will not be followed in this work. 
Alternatively, we can describe FA by a list of lists. Consider, for example, the automaton evenEven accepting only those words in \(TraditionalForm\`\(\({0, 1}\^*\)\ \)\) which have an even number of a´s and an even number of b´s defined by :

Q = {1, 2, 3, 4};
Σ = {a, b};
δ = {{{1, a}, 4}, {{1, b}, 2}, {{2, a}, 3}, {{2, b}, 
            1}, {{3, a}, 2}, {{3, b}, 4}, {{4, a}, 1}, {{4, b}, 3}};
(Subscript[q, 0])=1;
F = {1};

which we can encapsulate as:

{Q, Σ, δ, (Subscript[q, 0]), F}

This notation is still cumbersome. Let us adopt the following assumptions in order to expedite the description of FA: 

• The set Q will always comprise consecutive numbers from 1 (assumed to be the initial state) to the number of states. This number can always be obtained from the entries in δ so there will be no need to explicitly provide Q. 
• The previous assumption will also be applied to the alphabet Σ, which will enjoy the same fate as Q with the proviso that when we require to describe transitions (for instance in obtaining the regular expression corresponding to the accepted language) we will assume Σ comprises all lower-case letters in lexicographic order from "a" up to the number of columns of vector δ. 
• δ will be described by a matrix of dimension (number of states)×(alphabet size) wherein δ[[ i, j ]] will correspond to the state to which the automaton goes from state i under transition j.

Hence the previous automaton evenEven is shortly described as:

evenEven = {{{4, 2}, {3, 1}, {2, 4}, {1, 3}}, {1}};

Finally, as Length[First[evenEven]]=4 we know that |Q|=4 and, as Length[First[First[evenEven]]]=2, we know that ∑={a,b}. In other words, for any automaton M, Dimensions[First[M]]={|Q|,|Σ|}.

2 TEST AUTOMATA

Along with the automaton evenEven introduced before, the following automata will be used as test automata for the rest of our work. An alternative to the linear display of an automaton, obtained by just writing its name, is that provided by function showFA below.

showFA[{δ_, F_}] := MatrixForm /@ {δ, F}

for instance:

showFA[evenEven]

ON ∑={a,b}:

• automaton aa recognizing the language \(TraditionalForm\`\(\(\((a + b)\)\^*\) \(\(aa(a + b)\)\^*\)\ \)\) of all words having a double a somewhere is described as:

aa = {{{2, 1}, {3, 1}, {3, 3}}, {3}};

• automaton secondB accepting the language (ab+bb)\(TraditionalForm\`\(\((a + b)\)\^*\)\) of all words whose second character is b is:

secondB = {{{2, 2}, {4, 3}, {3, 3}, {4, 4}}, {3}};

• automaton oddA accepting those words having an odd number of a´s:

oddA = {{{2, 1}, {1, 2}}, {2}};

• automaton dif accepting the language of those words which have no two same letters adjacent (Note this is not the language \(TraditionalForm\`\(\((ab)\)\^*\)\)+\(TraditionalForm\`\(\((ba)\)\^*\)\)):

dif = {{{2, 3}, {4, 3}, {2, 4}, {4, 4}}, {1, 2, 3}};

• automaton mod5 accepting those words that, interpreted as the binary equivalent of a decimal number, are equal to 1 mod 5. For instance, as baabaa=(Subscript[100100, 2])=(Subscript[36, 10])≡1 mod 5, the automaton recognises the word baabaa.

mod5 = {{{1, 2}, {3, 4}, {5, 1}, {2, 3}, {4, 5}}, {2}};

ON ∑={a,b,c}:

• automaton difABC accepting  those words on Σ={a,b,c}  which have no two same letters adjacent:

difABC
       = {{{2, 3, 4}, {5, 3, 4}, {2, 5, 4}, {2, 3, 5}, {5, 5, 5}}, {1, 2, 3, 
          4}};

• automaton evenEvenABC accepting all words on Σ={a,b,c}  having an even number of a´s and an even number of  b´s:

evenEvenABC = {{{4, 2, 1}, {3, 1, 2}, {2, 4, 3}, {1, 3, 4}}, {1}};

ON ∑={a,b,c, ...}:

• automaton modMxN accepting those words that, interpreted as the base M equivalent of a decimal number, are equal to x mod N. For instance, as cbad=(Subscript[2103, 4])=(Subscript[147, 10])≡3 mod 6, automaton modMxN[4,3,6] must accept word cbad. Automaton modMxN[2,1,5] is equal to automaton mod5.

modMxN[m_, x_, n_] := {
        Partition[Flatten[Table[Range[n], {m}]], m], {1 + x}}

showFA[modMxN[2, 1, 5]]

showFA[modMxN[3, 1, 4]]

3 GENERATING WORDS OF LENGTH n ACCEPTED BY A GIVEN AUTOMATON

Given an FA, we want to obtain a list comprising all words of length n that it accepts. By polymorphism, we subordinate function acceptedWords below to one computing the words of length n accepted by M considering a given starting state q≠1. The result is generated in lexicographic order.

\(acceptedWords[M_, n_] := acceptedWords[M, 1, n]
\)\(acceptedWords[{_, F_}, q_, 0] := If[MemberQ[F, q], {""}, {}]
\)\(acceptedWords[M : {δ_, _}, q_, n_] := 
      \(acceptedWords[M, q, n] = 
        Module[{w, i, ans = {}}, 
					
          w = Map[acceptedWords[M, #, n - 1]&, 
              δ[[q]]]; 

          					
          Do[
								
            If[Length[w[[i]]] > 0, 
              AppendTo[ans, 
                Map[StringJoin[
                      FromCharacterCode[ToCharacterCode["a"] - 1 + i], #]&
                    \ , w[[i]]]]]

            						, {i, Length[w]}]; 
		Flatten[ans]]\)\)

Applying this function to our test automata:

TableForm[Table[acceptedWords[evenEven, n], {n, 0, 4}]]Table[Length[acceptedWords[evenEven, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[aa, n], {n, 0, 4}]]Table[Length[acceptedWords[aa, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[secondB, n], {n, 0, 4}]]Table[Length[acceptedWords[secondB, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[oddA, n], {n, 0, 4}]]Table[Length[acceptedWords[oddA, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[dif, n], {n, 0, 4}]]Table[Length[acceptedWords[dif, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[mod5, n], {n, 0, 5}]]Table[Length[acceptedWords[mod5, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[difABC, n], {n, 0, 3}]]Table[Length[acceptedWords[difABC, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[evenEvenABC, n], {n, 0, 3}]]Table[Length[acceptedWords[evenEvenABC, n]], {n, 0, 10}]

TableForm[Table[acceptedWords[modMxN[3, 0, 4], n], {n, 0, 3}]]Table[Length[acceptedWords[modMxN[3, 0, 4], n]], {n, 0, 10}]

¿can we set up a bijection between the set of words corresponding to numbers which are multiple of four in base 3 and the set of words having an even number of a´s and an even number of b´s? Possibly yes; transformation {a->c,  c->a} is a close one.

4 PLOTTING ALL WORDS OF LENGTH n

In order to display the complexity of the words of length n accepted by a given FA, we produce a density plot assigning different gray levels to each of the elements of the alphabet, starting with white for character "a" and ending with black for the last character used. At section 5 we will obtain the corresponding analytical expression.

wordMap[M_, n_]:=Module[{a = acceptedWords[M, n], s, b},
		If[Length[a] == 0, Return[{}]];
		s = Map[(FromCharacterCode[96 + #] -> ToString[#])&,  
                Range[Length[M[[1, 1]]]]]
                ; 
		b = ToExpression[Characters[StringReplace[a, s]]];
ListDensityPlot[b,Frame -> False,AspectRatio -> Automatic];]

wordMap[evenEven, 6]

wordMap[aa, 6]

wordMap[secondB, 6]

wordMap[oddA, 6]

wordMap[dif, 10]

wordMap[mod5, 8]

wordMap[difABC, 4]

wordMap[evenEvenABC, 4]

wordMap[modMxN[3, 1, 4], 4]

5 ENUMERATING WORDS OF LENGTH n ACCEPTED BY A GIVEN AUTOMATON

Let us find an expression for the number of words of length n accepted by an FA. To this end we design function arden. Note that a system of recursive equations is set up so that its solution is the answer.

<< "DiscreteMath`RSolve`"

\(arden[{δ_, F_}] := 
      Module[{nStates, nSymbols, 
          v = Flatten[
              Range[ToCharacterCode["A"], ToCharacterCode["Z"]]], w, 
          eq, ans = {}, u, i, j}, 

        		\ \ {nStates, nSymbols} = Take[Dimensions[δ], 2]; 

        		\ \ v = FromCharacterCode/@\ Take[v, nStates]; 
		\ \ 
        v = \(("variable"<>#&)\)/@v; 
		\ \ 
        Do[eq = v[[i]]<>"[n]=="; 

          				Do[
            eq = eq<>
                \((v[[δ[[i, j
                        ]]]]<>
                    "[n-1]+")\), {j, nSymbols}]; 
				
          If[StringTake[eq, \(-1\)] == "+", eq = StringDrop[eq, \(-1\)]]; 
          
				AppendTo[ans, eq]; 
				
          AppendTo[ans, 
            v[[i]]<>"[0]=="<>
              If[MemberQ[F, i], "1", "0"]], {i, nStates}]; 

		
        w = ToExpression[\((#<>"[n]"&)\)\ /@\ v]; 
		
        u = RSolve[ToExpression[ans], w, n]; \ 
	\ \ 
        FullSimplify[
          Expand[\(Simplify[w /. \ u]\)[[1, 1
              ]]]]]\)

arden[{{{1, 1}, {2, 2}}, {2}}]

arden[{{{1, 1}}, {}}]

arden[{{{2, 2}, {2, 2}}, {1}}]

arden[{{{1, 1}}, {1}}]

arden[evenEven]Map[Table[#  /.  {n -> i},  {i, 0, 10}]&, %]

arden[aa]

arden[secondB]

arden[oddA]

arden[dif]

arden[mod5]

arden[difABC]

arden[evenEvenABC]

How many numbers of size n multiple of four are there in base 4?. Answer:

arden[modMxN[4, 0, 4]]

6 DRAWING AUTOMATA

There is no general canonical way of drawing the graph corresponding to FA. In this section we propose one that is useful for teaching purposes and which consists of the following features:

• the states are represented by circles labeled accordingly,
• final states are indicated in double circle,
• the initial state is colored in yellow and the other states in green,
• transitions are Bezier curves,
• transitions are not directed. We feel that arrowed transitions, although an essential feature, clutter the graph unnecessarily; our graph, while experimenting, gives a rough idea on the topology of the automata in hand, which after printing or exporting to standard software, can be provided of appropriate arrowheads by the user.

Function transitions below constructs the set of bezier curves joining two given points p0 and p2, (possibly equal, in which case the curves will be circles of radii a multiple of a given parameter r). There will be numTrans curves drawn through numPoints segments. Two examples follow the definition.

\(transitions[p0_, p0_, numTrans_, _, r_] := 
      Module[{i}, 
		
        Table[Circle[p0 \((1 + \(i\ r\)\/\(2\ \@\(p0.p0\)\))\), 
            \(i\ r\)\/2], {i, numTrans + 1}]]
\)\(transitions[p0_, p2_, numTrans_, numPoints_, _] := 
      Module[{i, q, a, b, p1, t, c}, 
		
        i = Range[1 - numTrans, \ numTrans - 1, 2]; 
		{a, b} = p2 - p0; 

        			q = {\(-b\), a}; 
			
        p1 = Map[\((\(p0 + p2\)\/2 + \(\ q\)\/\(3\ numTrans\)\ #)\)&, i]; 

        		c = Map[
            \((\((1 - 2  t)\) \((1 - t)\) p0 + 4\ t\ \((1 - t)\)\ #\  + \ 
                  t \((2  t - 1)\)\ p2)\)&, p1]; 
		
        Map[Line[Table[#, {t, 0, 1, 1/numPoints}]]&, c]]\)

Show[Graphics[transitions[{0, 0}, {5, 3}, 7, 20, 1]], 
      AspectRatio -> Automatic];

Show[Graphics[transitions[{1, 2}, {1, 2}, 5, 20, 1]], 
      AspectRatio -> Automatic];

Finally, function drawFA below generates the graph of a given automata. Examples follow.

\(drawFA[{δ_, F_}] := 
      Module[{n, alphSize, θ, i, j, centers, p, r, connec, arcs = {}}, 
        
				
		{n, alphSize} = Dimensions[δ]; 
		
        connec = Table[0, {n}, {n}]; 
		
        Do[
			
          \(connec[[i, 
              δ[[i, j
                ]]]]++\), {i, n}, {j, 
            alphSize}]; 
		
        Do[
			
          connec[[i, j]] += 
            connec[[j, i]], {i, n - 1}, {
            j, i + 1, n}]; 
		
        Do[
			
          If[connec[[i, j]] > 0, 
            AppendTo[
              arcs, {i, j, 
                connec[[i, j]]}]], {i, 
            n}, {j, i, n}]; 
		
		θ = N[\(2  π\)\/n]; 
		
        r = 2\ Sin[θ\/8]; 
		
        centers = Table[{Cos[i\ θ], Sin[i\ θ]}, {i, 0, n - 1}]; 
        
				
		
        p = Map[transitions[
                centers[[#[[1
                    ]]]], 
                centers[[#[[2
                    ]]]], #
                  [[3]], 15, r]&, arcs]; 
        
		
		
        Map[AppendTo[p, {RGBColor[0, 0.5, 0.5], Disk[#, r]}]&, 
          Rest[centers]]; 
		
        Map[AppendTo[p, Circle[#, r]]&, Rest[centers]]; 

		
        AppendTo[
          p, {RGBColor[1, 1, 0.5], 
            Disk[centers[[1]], r]}]; 

        		AppendTo[p, 
          Circle[centers[[1]], r]]; 

        		
		
        Map[
			
          AppendTo[p, 
              Circle[centers[[#]], 
                \(2\ r\)\/3]]&, F]; 
		
		
        Do[
AppendTo[p, 
            Text[FontForm[ToString[i], {"Arial-Bold", N[50\ r]}], 
              centers[[i]]]], {i, 
            Length[centers]}]; 
		
			
        Show[Graphics[p], AspectRatio -> Automatic, 
          PlotRange -> All]; ]\)

drawFA[evenEven]

drawFA[aa]

drawFA[secondB]

drawFA[oddA]

drawFA[dif]

drawFA[mod5]

drawFA[difABC]

drawFA[evenEvenABC]

\(Do[
	drawFA[modMxN[i, 0, 6]], {i, 6}]\)