Algorithms on 
Finite Automata

Part IV. Counting Automata 
and Fractal Automata

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

Permission is hereby granted to reproduce part or all of this file for any purpose other than direct profit providing that the source is acknowledged.

This is the last of four parts dealing with the implementation of algorithms on FA. To activate the different functions comprising the previous parts, open each one of them and choose the Kernel-Evaluate-Evaluate Initialization menu path. Do the same for this notebook.

15 COUNTING NON-EQUIVALENT AUTOMATA

Consider the set of all possible FA. If the alphabet is of size m and they comprise n states, then there are (n^nm)(2^n) structurally different automata; this number grows very rapidly as the following table shows.

\(m = 2; 
Table[\(n\^\(n\ m\)\) 2\^n, {n, 10}]\)

In order to shorter this number, we will assume two AFs to be the same if they are mutual complements, which means that for a given δ, the possible sets F will be shortened depending on the value of n. For example, if n=4, instead of F being taken from the set 
		{{},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},
  		  {3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}
 it will suffice to take F from the set
    	 {{},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}	 
We do not include {1, 2, 3} as a possibility because we have already included its complement {4}.   Function subSetsK below computes the power set of the set Range[n] to be filtered by function noCompl as the example shows.

subSetsK[_, 0] := {{}}\(subSetsK[0, _] := {}
\)subSetsK[n_, k_] := {}  /;  k > n\(subSetsK[n_, k_] := 
      Module[{s1 = subSetsK[n - 1, k], s2 = subSetsK[n - 1, k - 1]}, 
		
        Join[s1, Map[Append[#, n]&, s2]]]\)

\(noCompl[n_] := 
      Module[{k}, 
		Flatten[Table[subSetsK[n, k], {k, 0, Floor[n/2]}], 1]]
        \)

Union @@ Table[subSetsK[4, i], {i, 0, 4}]

noCompl[4]

A further reduction can be achieved by eliminating the possibility F={} and keeping only those FA such that they
• cannot be further minimized and
• accept an infinite language (those accepting finite languages are structurally too simple to be useful)
The process is, however, computationally intensive and even the 3-states case proves to be quite laborious. For example, to find out how many 2-state FA on the alphabet Σ={a,b} are there complying with the above conditions we proceed as in the following dialog:

\(states = 2; 
a = 2\ states; 
s = Rest[noCompl[states]]; 


    u = Table[IntegerDigits[i, states], {i, 0, states\^a - 1}]; 

    u = Map[Join[Table[0, {a - Length[#]}], #]&, u]\  /. 
        x_Integer -> x + 1; 
u = Map[Partition[#, 2]&, u]; 


    ans = {}; 
Map[\((i = #; 
		Map[AppendTo[ans, {i, #}]&, s])\)&, u]; \ 
    

u = Select[ans, \((minimize[#] == #)\)&]; 

    u = Select[u, MemberQ[Characters[regularLanguage[#]], "*"]&]; 

    Print["There are ", Length[u], " different automata of ", states, 
      \ " states, out of ", \(2\^states\) states\^a, " possible ones"]
      \)Map[showFA[#]&, u]Map[regularLanguage[#]&, u]u = Map[arden[#]&, u]Print["There are ", Length[Union[u]], " different sequences"]

16 FRACTAL AUTOMATA

We can associate a quadtree to every FA acting on the alphabet Σ={a, b, c, d}. Equivalently, a monochromatic picture can be obtained by analizing the set of words of size n accepted by a given FA. These pictures are all self-similar and hence of fractal nature; we are interested in obtaining the fractal associated with a given FA.
Function wordSquare below obtains the square associated to a given accepted word by recursively subdividing a basic square of size 2. From top to bottom and left to right, the quadrants of this basic square are associated with the characters "b", "d", "a" and "c" respectively. An example follows.

\(wordSquare[w_] := 
      Module[{f = {{0, 1}, {1, 1}, {0, 0}, {1, 0}}, cc, c = Characters[w], p, 
          u, v, basis = {3, 1, 4, 2}}, 
		
        cc = Flatten[
            Map[\((ToCharacterCode[#] - ToCharacterCode["a"] + 1)\)&, \ 
              c]]; 
		
        p = Reverse[
            f[[basis[[cc
                ]]]]]; 
		
        u = Last[p] + Fold[\(#1 + #2\)\/2&, {0, 0}, Drop[p, \(-1\)]]; 
		
        v = u + 1\/2\^\(Length[c] - 1\); 
		Rectangle[u, v]]\)

wordSquare["bbc"]

Function fractalFA below computes the approximation to the fractal corresponding to a given FA. The approximation consists in considering only those accepted words of size n.

\(fractalFA[a_, n_] := 
      Module[{w = acceptedWords[a, n], quadTree}, 
		
        quadTree = Map[wordSquare[#]&, w]; 
		Graphics[quadTree]]\)

We shall consider only FA accepting infinite sets of words as the alternative produces dull black squares. An interesting example is that fractal corresponding to the FA accepting the language (a+b+c)*. We plot the first six approximations below converging towards the Sierpinski triangle.

g = Table[fractalFA[{{{1, 1, 1, 2}, {2, 2, 2, 2}}, {1}}, i], {i, 6}];
g = Partition[g, 3];
Show[GraphicsArray[g],AspectRatio -> Automatic,GraphicsSpacing->0.2];

An interesting fractal is the one corresponding to the FA accepting only those words having an even number of "a" and an even number of "b".  The sixth approximation is computed next and several other examples follow.

g = fractalFA[{{{2, 1, 1, 2}, {1, 2, 2, 1}}, {1}}, 6];
Show[g,AspectRatio -> Automatic];

g = fractalFA[automata["(b+c)(a+b+c+d)*", 4], 4];
Show[g,AspectRatio -> Automatic];

g = fractalFA[automata["(b+c)(a+b+c+d)*a", 4], 4];
Show[g,AspectRatio -> Automatic];

Chess Automata:

g = fractalFA[automata["(a+b+c+d)(a+b+c+d)(b+c)(a+b+c+d)*", 4], 4]
          ;
Show[g,AspectRatio -> Automatic];

Staircase automata:

g = fractalFA[automata["(b+c)*a(a+b+c+d)*", 4], 6];
Show[g,AspectRatio -> Automatic];

g = fractalFA[automata["(b+c+d)*a(b+c)*a(a+b+c+d)*", 4], 10];
Show[g,AspectRatio -> Automatic];

The following dialog answers the question of how many different non-equivalent pictures can be plot considering 2-states FA:

\(states = 2; 
a = 4\ states; 
s = {{1}}; 


    u = Table[IntegerDigits[i, states], {i, 0, states\^a - 1}]; 

    u = Map[Join[Table[0, {a - Length[#]}], #]&, u]\  /. 
        x_Integer -> x + 1; 
u = Map[Partition[#, 4]&, u]; 


    ans = {}; 
Map[\((i = #; 
		Map[AppendTo[ans, {i, #}]&, s])\)&, u]; 

    
u = Select[ans, \((minimize[#] == #)\)&]; 

    u = Select[u, MemberQ[Characters[regularLanguage[#]], "*"]&]; 

    Print["There are ", Length[u], " different automata of ", states, 
      \ " states, out of ", \(2\^states\) states\^a, " possible ones"]
      \)

For instance, the 5th generations of each of the first twenty of those are depicted below.

v = Take[u, 20];
g = Map[fractalFA[#, 5]&, v];
g = Partition[g, 4];
Show[GraphicsArray[g],AspectRatio -> Automatic,GraphicsSpacing->0.2];

17 GALLERY

The immense fractal automata universe can be explored by random choices using function randomFA. Examples of interested findings by the author follow. Note we are using function NthSubset from the Combinatorica package.

\(randomFA[nStates_] := 

        		{Table[Random[Integer, {1, nStates}], {nStates}, {4}], 
          NthSubset[Random[Integer, {1, 2\^nStates - 1}], Range[nStates]]}\)
randomFractal[nStates_, n_]:=
Show[fractalFA[randomFA[nStates], n],AspectRatio -> Automatic]

randomFractal[2, 5];

Some random examples