Automata Demo

Initialization

Author: Klaus Sutner, sutner@cs.cmu.edu.
This notebook is available under a  Creative Commons BY-NC-SA license.
You can download and install the current version of the Automata paclet from the paclet repository by executing
	PacletInstall[ResourceObject[“KlausSutner/Automata”]]
A slightly more recent version may be at my website  automata. 
There are also other notebooks that may be useful.
Current paclet version:  1.0.2

Load the paclet.

Needs["KlausSutner`Automata`"]

Some abbreviations and keeping image sizes under control.

MakeAbbrevs[]
SetImageSize[Small]

Normally it is preferable to turn on formatting right at the start. We will delay for a while to explain the underlying data structures first. 
We define a convenient plotting function for small machines.

FormatFA[False]
FormatSemigroup[False]
FormatEps[False]
colplot = PlotFA[#, Type->"MultiColor",EdgeStyle->Thick, VertexSize->Medium ]&;

Constructing FSMs

Basics

A finite state machine that recognizes the language consisting of just one string “ab”.

M = FA[ TSys[3,2,Graph[{DirectedEdge["","a",1],DirectedEdge["a","ab",2],DirectedEdge["ab","",2]}], Alpha[2],<|"TransType"->"PDFA"|>],
<| "AccCond"->Existential[{1},{3}]|>]

The FSM consists of two parts:  a transition system and an acceptance condition. 
The transition system has 5 parts:  n the number of states, k the number of letters in the alphabet, a directed graph whose edges are labeled in [k], an alphabet and a description of the type of machine. Currently, there are 4 kinds of machines:  DFA, PDFA, NFA and NFAE. The latter may have ϵ-transitions, represented by an edge label 0. 
The acceptance condition Exist[ini,fin]  has two lists, both subsets of [n], that indicate initial and final states. Note well that the acceptance condition is always in indexed form, but the graph in  the transition system may well have a more complicated vertex set, which is used as the state set of the machine. In the example, the state set is {"","a","ab"} to indicated matched letters.  Hence initial state 1 in the acceptance condition refers to state “”, and final state 3 refers to state “ab”.

Here is a visualization of machine M. The colored vertices indicate initial (orange) and final (blue) states.

PlotFA[M,VertexSize->Medium]

The data structures representing automata are somewhat messy, but there is often no need to work with them directly, a number of constructors for automata together with a collection of operations make it possible to construct machines without having explicitly specify all the components. Closely related is the issue of representing automata in a notebook: It is usually best to turn on formatting and hide details.

FormatFA[True]
M

For small machines, the actual plot will be shown. For larger ones, we display a default image.

Finite Languages

For finite languages, a DFA can be built using either a trie or the quotient construction (the latter produces the minimal DFA).

{EmptyFA[Alpha[2]],UniversalFA[Alpha[2]]}

We will often use the standard 2-letter alphabet.

Alpha[2] // AlphabetList

A PDFA based on a simple trie.

M = FiniteLanguageFA[{"aaa","bbb","aabb"},Alpha[2]]

A plot with state labels.

PlotFA[  M,VertexLabels->Placed["Name",Center],VertexSize->Large,ImagePadding->10]

A more colorful version, omitting some information.

M // colplot

Determine the census function and the language of M.

LanguageFA[ M,12, SizeOnly->True ]
LanguageFA[ M,6]

Alternatively one can build a quotient machine that shares subtrees and produces the minimal DFA.

M = FiniteLanguageFA[{"aaa","bbb","aabb"},Alpha[2],Type->"Quotient"]

M //colplot

If we need a DFA rather than a PDFA, we can simply complete the latter.

MM = CompletePDFA[M]

By default, PlotFA prints only the trim part of an automaton, in this case the PDFA.

Table[ PlotFA[MM, "Trim"->bool,VertexSize->Medium],{bool,{False,True}}]  // GraphicsRow[#,Spacings->100]&

Positions

We can generate machines for the language of all words with a fixed letter in a particular position.  If the position is counted from the beginning of the word, the machine is naturally a PDFA.

M1 = PositionFA[ 4->"b", Alpha[3] ]

LanguageFA[M1,12,SizeOnly->True]
LanguageFA[M1,{4}]

Counting from the end of the word is easiest to handle with an NFA.

M2 = PositionFA[ -4->"a", Alpha[3] ]

LanguageFA[M2,12,SizeOnly->True]
LanguageFA[M2,{4}]

Multiple conditions can be given simultaneously, but not with mixed signs.

M2 = PositionFA[ {-2->"a",-4->"c"}, Alpha[3] ]

LanguageFA[M2,12,SizeOnly->True]
LanguageFA[M2,{4}]

PositionFA[ {-2->"a",4->"c"}, Alpha[3] ]

Determinization produces a de Bruijn automaton.

MM = DeterminizeFA[M2];
MM // colplot

By taking intersections we can combine various conditions.

M3 = IntersectionFA[M1,M2]

M3 // colplot

Semilinear Languages

The next operation constructs a finite state machine based on a semilinear set  {t,p,A,B}   where t ≥ 0 is the transient, p≥ 1 the period and A ⊆ {0,…,t-1} , B ⊆ {0,…,p-1} are subsets defining the semilinear set  A  ⋃   (t + B + p ℕ ).  Semilinear sets include in particular simple counts {(Subscript[n, 1]),…,(Subscript[n, k])} and modular counts { n | n = 0 (mod p)}. One can use several numerical parameters associated with a word:  
	- length of word
	- number of occurrences of factors
	- number of occurrences of scattered subwords
Here are typical examples:

All words of length 2:

dfa = SemilinearDFA[  {3,1,{2},{}}, Alpha[3] ];
LanguageFA[ dfa, 8 ]

All words with 2 occurrences of a factor a b a.

dfa = SemilinearDFA[ "aba", {3,1,{2},{}},Alpha[2], Type->"Factor" ];
LanguageFA[dfa,7 ]
LanguageFA[dfa,12, SizeOnly->True ]

By default, factors are allowed to overlap. To count only non-overlapping factors use

dfa = SemilinearDFA[ "aba", {3,1,{2},{}},Alpha[2], Type->"FactorNoOverlap" ];
LanguageFA[ dfa,8 ]
LanguageFA[dfa,12, SizeOnly->True ]

Counting subsequences rather than factors.

dfa = SemilinearDFA[ "aba", {3,1,{2},{}},Alpha[2], Type->"Subsequence" ];
LanguageFA[ dfa,6 ]

A one-letter lasso automaton.

M= SemilinearDFA[ {7,11,{2,5},{1,3}}, Alpha[1] ];

PlotFA[M,VertexSize->Medium]

Another subword count, this time for scattered subsequences: 3 occurrences of a b b.

M = SemilinearDFA[  "abb", {4,1,{3},{}} ,Alpha[2], Type->"Subsequence" ];

PlotFA[M ]

Verify that the subword counts are correct.

L = Flatten@LanguageFA[M,{10}];
L == Select[ Words[{10}],WordBinomial[#,"abb"]==3& ]

The machine as constructed fails to be minimal.

MM = MinimizeFA[M];
MM  // PlotFA

Counting 0 mod 5 occurrences of scattered subword a a b.

M = SemilinearDFA[  "aab", {0,5,{},{0}}, Type->"Subsequence" ];

PlotFA[M, Type->"MultiColor"]

The machine works as advertised for words of length 6:

L = LanguageFA[ M,{8} ]
L == Select[ Words[{8}],Mod[WordBinomial[#,"aab"],5]==0& ]

Counting 0 mod 3 occurrences of scattered subword a b b.

M = SemilinearDFA[  "abb", {0,3,{},{0}}, Type->"Factor" ];
PlotFA[M, Type->"MultiColor"]
PlotFA[ MinimizeFA[M], Type->"MultiColor"]

For simple counts and modular counts there are abbreviations:

M = SemilinearDFA[ "a", 3, Type->"Factor" ];
LanguageFA[ M, 6 ]

M = SemilinearDFA[ "a", 1,3, Type->"Factor"  ];
PlotFA[M, Type->"MultiColor",VertexSize->Medium]
LanguageFA[ M, 4 ]

Fixing the letters in certain positions: a in position 2, c in position 4.

M = PositionFA[  {2,4},{1,3}, Alpha[3] ];
M//colplot
LanguageFA[ M, 5 ]

Frontiers

We can unfold any DFA into a frontier automaton where all back transitions point to a previous location in the current branch.  Here is a mod-counter.

sl1 = SemilinearDFA[ "a",{0,3,{},{0}}, Type->"Factor" ];
sl2 = SemilinearDFA[ "b",{0,2,{},{0}}, Type->"Factor" ];

M=MinimizeFA[IntersectionFA[sl1,sl2]];
PlotFA[M,Type->"MultiColor",EdgeStyle->Thick]

And here is the periodic frontier automaton: forward transitions, backward transitions, and witnesses labeled by states.

frw = FrontierFromDFA[ M,Method->"Periodic" ];
frw = FrontierFromDFA[ M  ]

We can convert the frontier back to a DFA (we need to specify the final states). The resulting machine is isomorphic to the original one.

MM = FrontierToDFA[frw,FinalStateList[M]];
IsomorphicQDFA[M,MM]

The conversion fails when the level is too small and produces a corresponding error message.

frw = FrontierFromDFA[M,Method->"Level", Type->{3,First}]

frw = FrontierFromDFA[M,Method->"Level", Type->{4,First}]

MM = FrontierToDFA[frw,FinalStateList[M]];

G = PlotFA[MM,Type->"MultiColor","Trim"->False,EdgeStyle->Thick,
VertexCoordinates->GraphEmbedding[KaryTree[StateCount[MM],AlphabetCount[MM]]]]

Products

A simple counter automaton.

m1=SemilinearDFA[ "a", 2, Alpha[2], Type->"Factor" ]
m2=SemilinearDFA[ "b", 3, Alpha[2], Type->"Factor" ]

LanguageFA[m1,6]
LanguageFA[m2,6]

The (trim part of the) product automaton and for the minimal automaton.

m=IntersectionFA[m1,m2];
PlotFA /@ {m, MinimizeFA[m]} // GraphicsRow[#,Spacings->100]&

The construction guarantees an accessible automaton, but co-accessibility may well fail.

m1=PositionFA[-3->"a",Alpha[2]];
m2=PositionFA[-5->"b",Alpha[2]];
m3=PositionFA[{-3->"a",-5->"b"},Alpha[2]];
m=IntersectionFA[m1,m2];

LanguageFA[m,6]

EquivalentQFA[m,m3]

Two mod-counter automata.  The algorithm used for automata associated with semilinear sets produces a non-minimal machine.

m1=SemilinearDFA["a",0, 5, Alpha[2],Type->"Factor" ];
m2=SemilinearDFA["b",0, 12, Alpha[2],Type->"Factor" ];
m1 // colplot

And we get a larger-than-needed product automaton.

m=IntersectionFA[m1,m2];
m // colplot

Minimization produces the expected torus.

MinimizeFA[m] // colplot

Which we can also obtain by minimizing the component automata first.

mm=IntersectionFA[MinimizeFA[m1],MinimizeFA[m2]];
mm // colplot

Permutation Alphabets

A symmetric group acting on itself: the alphabet is the whole group.

K = GroupElements@SymmetricGroup[3];
Clear[del]
del[s_Integer][ p_Cycles] := PermutationProduct[ p, K[[s]] ]
m = GenerateFA[ Cycles[{}], Table[ Evaluate[del[s]], {s,6} ],Alpha[6,"Digit"],(#===Cycles[{}])&,(#===Cycles[{}])&, Type->"DFA" ];

PlotFA[ m,Type->"MultiColor", EdgeStyle->Thick ]

Using 3 transpositions as generators.

K = {Cycles[{{1,2}}],Cycles[{{2,3}}],Cycles[{{1,3}}]};
Clear[del]
del[s_Integer][ p_Cycles] := PermutationProduct[ p, K[[s]] ]
m = GenerateFA[ Cycles[{}], Table[ Evaluate[del[s]], {s,3} ],Alpha[3,"Digit"],(#===Cycles[{}])&,(#===Cycles[{}])&, Type->"DFA" ];

PlotFA[ m,Type->"MultiColor", EdgeStyle->Thick ]

A transposition and a 3-cycle.

K = {Cycles[{{1,2}}],Cycles[{{1,2,3}}]};
Clear[del]
del[s_Integer][ p_Cycles] := PermutationProduct[ p, K[[s]] ]
m = GenerateFA[ Cycles[{}], Table[ Evaluate[del[s]], {s,2} ],Alpha[2,Type->"Digit"],(#===Cycles[{}])&,(#===Cycles[{}])&, Type->"DFA" ];

PlotFA[ m,Type->"MultiColor", EdgeStyle->Thick ]

Group Languages

Consider all elements of a permutation group as words, try to understand the growth rate of the state complexity of the associated finite languages. 

The full symmetric group is easy.

Table[  With[ {L = PermutationList[#,k]& /@  GroupElements@SymmetricGroup[k]},
StateCount@MinimizeFA@FiniteLanguageFA[ ToWord[L,Alpha[k]], Alpha[k] , Type->"Quotient" ]] , {k,8} ]
FindSequenceFunction[%,x]

m =  With[ {L = PermutationList[#,6]& /@  GroupElements@SymmetricGroup[6]},
		FiniteLanguageFA[ ToWord[L,Alpha[6]], Alpha[6]] ];
m // StateCount

mm = MinimizeFA[m];
PlotFA[mm,Type->"MultiColor"]

But the alternating group is a bit strange.

tab = Table[  With[ {L = PermutationList[#,k]& /@  GroupElements@AlternatingGroup[k]},
StateCount@MinimizeFA@FiniteLanguageFA[ ToWord[L,Alpha[k]], Alpha[k] , Type->"Quotient" ]] , {k,8} ]

sf = FindSequenceFunction[tab,z]

Dihedral groups:

Table[  With[ {L = PermutationList[#,k]& /@  GroupElements@DihedralGroup[k]},
		StateCount@FiniteLanguageFA[ ToWord[L,Alpha[k]], Alpha[k] , Type->"Quotient" ]] , {k,3,10} ]
FindSequenceFunction[%,z]

M= With[ {L = PermutationList[#,6]& /@  GroupElements@DihedralGroup[6]},
		FiniteLanguageFA[ ToWord[L,Alpha[6]], Alpha[6] , Type->"Quotient" ]];

PlotFA[ M,Type->"MultiColor", EdgeStyle->Thick  ]

And some Abelian groups.

Table[  With[ {L = PermutationList[#,8+k]& /@  GroupElements@AbelianGroup[{3,5,k}]},
		StateCount@FiniteLanguageFA[ ToWord[L,Alpha[8+k]], Alpha[8+k] , Type->"Quotient" ]] , {k,3,10} ]
FindSequenceFunction[%,z]

(n,k)-DFAs

By an (n,k)-DFA we mean any DFA on n states over a k-letter alphabet. Ignoring isomorphisms, the number of (n,k)-DFAs is (2^(n+log n  (k n + 1))), so we can only handle rather small values of n and k.

Tally Automata

We construct all minimal (n,1) automata.

Minimality here translates into two conditions:
- the bitvector of final states on the limit cycle forms a primitive binary word,
- the two predecessors of the base point (if the transient is non-zero) must not both be final or non-final.
Primitive words are easy to count with Möbius inversion and we easily get a summation for minimal tally automata.

Clear[primCount,minCount]
primCount[1]= 2;
primCount[n_Integer?Positive] := 
Sum[   MoebiusMu[n/d]2^d, {d,Divisors[n]} ];
minCount[n_Integer?Positive] := 
primCount[n] +  Sum[ 2^(t-1) primCount[n-t], {t,n-1}];
minCount/@Range[10]

Code

Primitive bitvectors of length n.

Clear[prims]
prims[n_Integer?Positive] := 
With[ {tups = Tuples[{0,1},{n}]},
Select[tups, With[ {per= Length[FindRepeat[#,2]]},!(per >0  && Mod[n,per]==0)]& ] ];

Convert parameters t,p,F to a DFA. We give an explicit construction for the sake of clarity; in general,  it would be preferable to use a constructor such as GraphToFA.

Clear[finToDFA]
finToDFA[t_Integer?NonNegative,p_Integer?Positive,fin_List ] := 
FA[ TSys[ t+p,1,Graph[Table[ DirectedEdge[s,TransientMod[s+1,t,p],1], 
{s,0,t+p-1}] ], Alpha[1], <|"TransType"->"DFA"|>], 
<|"AccCond"->Existential[{1},fin+1]|>]

Construct all possible DFAs for given n; wrapper for version depending on t and p.

Clear[constructLasso]
constructLasso[n_Integer?Positive]:= 
Table[ constructLasso[ t, n-t], {t,0,n-1} ]
constructLasso[t_Integer?NonNegative,p_Integer?Positive]:= 
Module[ {tp,prm,trans0,trans1,prm0,prm1},
tp = t + p;
prm= Pick[ Range[t,tp-1],#,1]& /@ prims[p];

(* t=0 use all primitive finals state sets *)
If[ t==0, 
Return[ finToDFA[t,p,#]& /@ prm]];

(* separate on membership  t-1 versus T-1  in transient/periodic part *)
trans0 = DeleteCases[ PowerSet[Range[0,t-1]], {___,t-1} ];
trans1 = Cases[ PowerSet[Range[0,t-1]], {___,t-1} ];
prm0 = DeleteCases[ prm, {___,tp-1}];
prm1 = Cases[ prm, {___,tp-1}];
Join[ finToDFA[t,p,#]& /@ (Flatten/@CartesianProduct[trans1,prm0]),
finToDFA[t,p,#]& /@ (Flatten/@CartesianProduct[trans0,prm1])]
];

Small Examples

All minimal lasso DFA on 4 states.

aut= constructLasso[4]; 
aut // LengthLength

Check against the counting function.

% // Last // Total
minCount[4]

Map[ PlotFA[#,Type->"MultiColor",Trim->False,VertexSize->Medium]&, aut, {2}] // Column

We can visualize the acceptance languages for 6-state minimal lasso DFAs.
Each column represents the language of a machine as a bitvector.

aut= Flatten@constructLasso[6]; 
aut // Length
A = LanguageFA[ #, 50, SizeOnly->True ]& /@ aut;
AA = Thread@SortBy[ A, Length@Last@FindTransientRepeat[ #,2]& ];
PlotMatrix[AA]

(2,2)-DFAs

As a warmup, let’s determine all minimal (2,2)-DFAs. We start with a brute-force enumeration and filter out isomorphic machines later. 
Here are all (2,2) transition matrices.

mats = Partition[#,2]& /@CartesianProduct[2,2,2,2];
mats // Length

We may safely assume that the initial state is 1, so we only need to combine the matrices with all finite state sets. This produces 64 machines.

dfas = With[{fins = PowerSet[Range[2]]},
	Flatten@Table[ GraphToFA[ Graph[Range[2],TransitionsFromMatrix[A]],Alpha[2],{1}, F ], {A,mats}, {F,fins} ]];
dfas // Length

Since there are only a handful of machines, we simple compute the equivalence classes with respect to behavioral equivalence.

equcls = ToClasses[ dfas, EquivalentQFA, Type->"Relation" ];
equcls // LengthLength

There are 2 large classes, in positions 1 and 2.  Class 1 contains all machines accepting nothing and class 2 contains all machines with universal language.

AllTrue[ equcls[[1]],PropertyQFA[#,"Empty"]& ]
AllTrue[ equcls[[2]],PropertyQFA[#,"Universal"]& ]

Hence there are 26 non-equivalent (2,2)-DFAs.

(2,3)-DFAs

Second, we determine all minimal (2,3)-DFAs, using the same brute-force approach as above.
Here are all (2,3) transition matrices.

mats = Partition[#,3]& /@CartesianProduct[2,2,2,2,2,2];
mats // Length

Again we assume that the initial state is 1, resulting in 256 machines.

dfas = With[{fins = PowerSet[Range[2]]},
	Flatten@Table[ GraphToFA[ Graph[Range[2],TransitionsFromMatrix[A]],Alpha[3],{1}, F ], {A,mats}, {F,fins} ]];
dfas // Length

The number is sufficiently small to compute the equivalence classes directly, in some 4 seconds on my machine.

equcls = ToClasses[ dfas, EquivalentQFA, Type->"Relation" ]; // AbsoluteTiming
equcls // LengthLength

As before, the 2 large classes correspond to empty/universal machines.

AllTrue[ equcls[[1]],PropertyQFA[#,"Empty"]& ]
AllTrue[ equcls[[2]],PropertyQFA[#,"Universal"]& ]

dfas // RandomChoice

Hence there are 114 non-equivalent (2,3)-DFAs.

(3,2)-DFAs

This time we need to be careful to avoid computational blowup.  
As in the (2,2) case, we combine all (3,2) transition matrices with all possible final state sets, making no attempt to remove isomorphs (beyond fixing the initial state to be 1). Alas, this time, we get 5832 machines and a direct pairwise equivalence test would take over 2.5 hours. A slightly more stream-lined search for inequivalent machines still takes some 15 minutes. We describe a better approach below.

mats = Partition[#,2]& /@CartesianProduct[3,3,3,3,3,3];
mats // Length
dfas = With[{fins = PowerSet[Range[3]]},
	Flatten@Table[ GraphToFA[ Graph[Range[3],TransitionsFromMatrix[A]],Alpha[2],{1}, F ], {A,mats}, {F,fins} ]];
dfas // Length

Running EquivalentQFA on all pairs of these machines is too slow, we need to do some preprocessing. 
We first filter by two ad hoc invariants: accepted words up to length 8, and census function up to 20.  
This takes some 22 seconds on my machine.

invars[M_?DFAQ]:= {LanguageFA[M,20, SizeOnly->True],LanguageFA[M,8]};

blocks = GatherBy[ dfas, invars]; // AbsoluteTiming
blocks // Length
Length /@ blocks  // Frequencies

The total number of blocks is 1054.  As before, there are 2 large blocks comprised of all empty/universal machines.

m = RandomChoice[blocks[[1]]];
PlotFA[m,Trim->False,VertexSize->Medium]
AllTrue[ blocks[[1]],PropertyQFA[#,"Empty"]& ]

m = RandomChoice[blocks[[2]]];
PlotFA[m,Trim->False,VertexSize->Medium]
AllTrue[ blocks[[2]],PropertyQFA[#,"Universal"]& ]

We remove the 2 trivial blocks and perform an explicit equivalence test on the remaining classes. As it turns out, our heuristic is good enough to force all the blocks to contain only equivalent machines.

AllTrue[ Drop[blocks,2], EquivalentQFA ] // AbsoluteTiming

Just to be on the safe side, check one of the larger blocks.

blocks92 = Last@Select[blocks,Length[#]==92& ];

All the machines accept only (SuperPlus[{a,b}]). Incidentally, the other size-92 block consists of machines accepting only ϵ.

RandomChoice[blocks92];
 PlotFA[%,Trim->False,VertexSize->Medium]

So there are 1054 equivalence classes altogether.

Determinization

kth Symbol

An NFA checking for symbols from the end:

M = PositionFA[ -4->"a", Alpha[2] ];
M // colplot

The corresponding DFA is based on a de Bruijn graph.

MM = DeterminizeFA[M];
G = MM // colplot

Checking the language and the growth function.

LanguageFA[MM,5]
LanguageFA[MM,16, SizeOnly->True ]
GrowthFunctionDFA[MM,z]

Of course, the machines are equivalent.

EquivalentQFA[ M, MM ]

All subsets of [5] that contain 1 appear in the accessible part of the power automaton.

DeterminizeFA[ M, StateType->"Shallow" ];
StateList[%]

This suggests a blow-up from n to (2^(n-1)).

Table[  With[ {M= PositionFA[-k->"a", Alpha[2] ]},
	StateCount [{ M, DeterminizeFA[M]}]], {k,12} ] // TableForm

Follow Languages

Double sling automata of type:   (SuperStar[Σ]) a  (Σ^( n)) b  (SuperStar[Σ]) ⋃ (SuperStar[Σ]) b  (Σ^( n)) a  (SuperStar[Σ]).
Here is n=3.  
Some abbreviations to help with the construction of the regular expressions.

ab = REP["a","b"];
Clear[REPower]
REPower[exp_,0]=Eps;
REPower[exp_,nn_Integer]:=RET@@Table[exp,{nn}];

With[ {n=3},
	exp1=RET[RES[ab],"a",REPower[ab,n],"b",RES[ab]];
	exp2=RET[RES[ab],"b",REPower[ab,n],"a",RES[ab]] 
];
m=RegexToFA[REP[exp1,exp2],Alpha[2]]

The NFAE clearly grows linearly with n.

PlotFA[ m,  Type->"MultiColor", EdgeStyle->Thick ]

But the deterministic machines blow up.

m // DeterminizeFA ;
mm= m // MinimizeFA;
PlotFA[ #,  Type->"MultiColor" ]& /@ {m,mm} // GraphicsRow

Brzozowski Universal

A DFA based on a circulant automaton that demonstrates maximal blow-up under reversal. We could perform surgery on a circulant, but it is also straightforward to construct the machine from scratch.

ClearAll[BrzozowskiUniveralDFA]
BrzozowskiUniveralDFA[n_Integer]:=
With[{tr =Join[ Table[ DirectedEdge[p,Mod[p+1,n,1],1], {p,n} ],
{ DirectedEdge[1,2,2], DirectedEdge[2,1,2]},Table[ DirectedEdge[p,p,2], {p,3,n} ],
Table[ DirectedEdge[p,p,3], {p,n-1} ], {DirectedEdge[n,1,3]}]},
GraphToFA[ Graph[Range[n],tr],Alpha[3],{1},{n}, StateType->"Indexed"]]

m=BrzozowskiUniveralDFA[6];
PlotFA[m, VertexSize->Medium]

The language is slightly complicated:

LanguageFA[m,6]
LanguageFA[m,14,SizeOnly->True]

The machine as constructed is minimal.

m // MinimizeFA // StateCount

And the reversal blows up …

mm=DeterminizeFA[ReverseFA[m]];
PlotFA[mm, Type->"MultiColor"]

The power automaton produced by determinization is already minimal.

mm // MinimizeFA // StateCount

A few examples:

Table[  With[ {M= BrzozowskiUniveralDFA[k]},
	StateCount [{ M, DeterminizeFA[ReverseFA[M]]}]], {k,2,10} ] // TableForm

Determinization and Blowup

Constructions of minimal NFAs that demonstrate exponential blow-up during determinization and minimization.

Code

Switch the label of a transition. Only for (2,2)-regular graphs and binary labels.

ClearAll[switchLabel]
Options[switchLabel]={Type->First};
switchLabel[G_?GraphQ,p_Integer,q_Integer,opts:OptionsPattern[]] := 
Block[ {el,tr0,tr1},
el = Sort@Cases[EdgeList[G],DirectedEdge[p,q,_]];
If[Length[el]== 0, Return[$Failed]];
tr0 = OptionValue[Type][el];
tr1 = MapAt[ (3-#)&, tr0, 3];
EdgeAdd[EdgeDelete[G,tr0],tr1]
];
switchLabel[M_?FSMQ,p_Integer,q_Integer,opts:OptionsPattern[]] := 
Block[ {G},
G = switchLabel[TransitionSystemGraph[M],p,q,opts];
CloneFA[M,"TransitionGraph"-> G, "TransType"->"NFA"]
];
switchLabel[M_?FSMQ,p_Integer \[DirectedEdge]q_Integer,opts:OptionsPattern[]] := switchLabel[M,p,q,opts];
switchLabel[G_?GraphQ,p_Integer \[DirectedEdge]q_Integer,opts:OptionsPattern[]] := switchLabel[G,p,q,opts];
switchLabel[M_?FSMQ,DirectedEdge[p_Integer ,q_Integer,_],opts:OptionsPattern[]] := switchLabel[M,p,q,opts];
switchLabel[G_?GraphQ,DirectedEdge[p_Integer ,q_Integer,_],opts:OptionsPattern[]] := switchLabel[G,p,q,opts];

Compute the zigzag decomposition of a (2,2)-regular graph.

ClearAll[ZigzagDecomposition]
ZigzagDecomposition[G_?GraphQ] := 
Block[{alleds,zigzag},
(* construct zigzag starting at u *)
zigzag[uu_]:=  
Block[{src,trg,fe,be,eds,zz,cnt},
zz = {};
src= uu;  cnt=0;
While[ (eds = Select[alleds,First[#]==src& ])=!={} && cnt++<1000,
fe =First[eds];        (* forward edge with source src *)
alleds = DeleteCases[alleds,fe];
trg = fe[[2]];
be =First@Select[alleds,#[[2]]==trg& ]; (* backward edge with target trg *)
alleds = DeleteCases[alleds,be];
zz = Join[zz,{fe,be}];
src= First[be]             (* update src *)
];
zz
];
alleds = EdgeList[G];
SafeLastFirst@Reap[  While[ alleds =!= {},
	Sow[ zigzag[alleds[[1,1]]] ]]]
]   /;  Union[Thread[{VertexInDegree[G],VertexOutDegree[G]}]]=={{2,2}};
ZigzagDecomposition[M_?FSMQ] := ZigzagDecomposition[TransitionSystemGraph[M]];

Compute a permutation labeling, given a zigzag decomposition.

ClearAll[labelZigzags]
labelZigzags[ Z:{__List}, lab_List ] := 
With[{ZZ = Map[ Take[#,2]&, Z, {2} ]},
TransitionsSort@Flatten[auxLabelZigzag@@@Pairs[ZZ,lab]] ];
labelZigzags[  Z:{__List}, b_Integer ] := labelZigzags[ Z, IntegerDigits[b,2,Length[Z]] ];
auxLabelZigzag[zz_List,b_Integer] := 
Append@@@Pairs[zz,Mod[ b+Range[0,Length[zz]-1],2]+1];

Moore

NFA:   n	DFA:  (2^( n))
A classical example by Moore.  Note that full exponential blow-up of the minimal DFA automatically guarantees minimality of the NFA:  the number of distinct behaviors in any smaller NFA would be insufficient.
First the deterministic version of the transitions.

n = 8;
tr = TransitionsSort[ DirectedEdge@@@Join[ Pairs[Range[n],Join[{1},RotateLeft[Range[2,n]]] ,Table[1,{n}]], 
 Pairs[Range[n],RotateLeft[Range[n]],Table[2,{n}]] ] ]

G = Graph[ Range[n], tr,VertexLabels->Placed["Name",Center], VertexStyle->LightBlue,VertexSize->Large ]

The corresponding DFA is clearly minimal.

GraphToFA[ G, Alpha[2], {1},{1}]// colplot

Switch the label of the self-loop 1->1 and build the corresponding NFA.

H = switchLabel[G,1\[DirectedEdge]1];
M = GraphToFA[ H, Alpha[2], {1},{1}];
M // colplot

Determinization followed by minimization produces a machine on 256 states.

MinimizeFA[M]

Somewhat surprisingly, the corresponding semiautomaton also works.

SetInitialFinal[M,All,All] // MinimizeFA

Switching the label of the 1->2 transition in the red zigzag produces a machine on 255 states.

H = switchLabel[G,1\[DirectedEdge]2];
GraphToFA[ H, Alpha[2], {1},{1}] // MinimizeFA

And the other 2 transitions in the red zigzag both have maximum blowup.

GraphToFA[ switchLabel[G,8 \[DirectedEdge]1], Alpha[2], {1},{1}] // MinimizeFA
GraphToFA[ switchLabel[G,8 \[DirectedEdge]2], Alpha[2], {1},{1}] // MinimizeFA

The remaining edgs show no blowup: switching a label produces a partial DFA.

Table[ StateCount@MinimizeFA@GraphToFA[ switchLabel[G,i \[DirectedEdge]i+1], Alpha[2], {1},{1}], {i,2,7}]

Jiraskova

NFA:   n	DFA:   (2^( n))
A machine with a much higher degree on nondeterminism.

Clear[JiraskovaFA]
JiraskovaFA[n_]:=
Block[{next0,next1},
next0[n]={};next0[i_]:={1,i+1}/;i<n;
next1[n]={};next1[i_]:={i+1}/;i<n;
GenerateFA[ {1}, {next0,next1}, Alpha[2], (#==1)&,(#==n)&, Type->"NFA"]
];

All states except the last are nondeterministic.
The NFA has full blow-up and produces a reduced DFA.

M = JiraskovaFA[8];
M // colplot
MinimizeFA[M] // StateCount

But the corresponding semiautomaton fails miserably: the DFA is still large, but minimization collapses the machine.

MM = SetInitialFinal[ M, All, All ];
MM // DeterminizeFA // StateCount
MM // MinimizeFA // StateCount

Note the diagram of the minimal automaton.

M // MinimizeFA // colplot

Iwama, Matsuura, Paterson

Construction of minimal NFAs that demonstrate exponential blow-up during determinization and minimization.
NFA:   n	DFA:  (2^( n))-α
The following requires 7 <= n and 5 <= α <= 2n - 2.  The other parameters are just for notational convenience.

n=11;
α=8;
k=α-1;
m=n-k;
5≤α<2n-2&&GCD[n,k]==1

The state set uses two kinds of states:  {0,p} and {1,p}.
We construct a set of taps at which non-deterministic transitions occur.
In our example, there is only one tap; correspondingly, there are 2 nondeterministic states.

A=With[{r=Ceiling[(k/4)]},
If[EvenQ[k],Join[Range[3,2 r,2],Range[2 r,k-4,2]],Range[3,k-4,2]]]

ClearAll[next0,next1]
next0[{0,i_}]:={{0,Mod[i+1,k]}};
next0[{1,i_}]:={{1,Mod[i+1,m]}};
next1[{0,2}]={{1,0}};
next1[{0,i_}]:=If[MemberQ[A,i],{{0,i},{0,0}},{{0,i}}];
next1[{1,0}]={{1,1}};
next1[{1,1}]={{0,0},{0,2}};
next1[{1,i_}]:={{1,i}};

Build the corresponding transition system by a closure operation.

M = GenerateFA[{{0,0},{1,0}},{next0,next1},Alpha[2], (#=={0,0})&, (#=={0,0})&, Type->"NFA" ];
M // colplot

Determinization produces nearly full blow-up with gap α.

MM = DeterminizeFA[M];
MM // StateCount
%==(2^n)-α

The missing states in the power automaton.

Complement[ PowerSet[Range[n]], StateList[MM] ]

The DFA is already minimal.

MM // MinimizeFA // StateCount

Zigzags

Suppose G is a  (2,2)-regular digraph. Standard examples are circulants and de Bruijn graphs.   Define a zigzag in G to be a cycle with alternating forward and backward edges. It is easy to see that G can be uniquely  decomposed into edge-disjoint zigzag components. 

Zigzags are useful in the study of NFAs that show strong blowup during determinization. First, given the zigzag decomposition of a graph, we can easily construct all permutation labelings of the graph.  Here a permutation labeling means that the corresponding transition maps (Subscript[δ, a]) : Q⟶ Q are permutations. In other words, the labeling is deterministic and codeterministic.  In a permutation labeling, the label of each single transition on a zigzag determines the whole zigzag. A permutation automaton is obviously already transition-deterministic, so there is no blowup. Now define a 1-permutation automaton to be obtained from a permutation automaton by switching the label of a single transition. These automata seem to display full or nearly full blowup in many cases.

Circulants

Some examples due to yours truly:  1-permutation automata based on (2,2)-regular circulant graphs.
Note that the number of zigzags in the circulant C(n,(Subscript[s, 1]),(Subscript[s, 2])) is gcd(n,(Subscript[s, 1])-(Subscript[s, 2])).

Circulants (n,0,1)

A circulant with strides 0 and 1, on n states.

M= With[ {n=10},
CirculantFA[ n, {0,1}, Labels->{Table[1,{n}],Table[2,{n}]} ]];
M // colplot

There is one zigzag, the whole graph.

ZigzagDecomposition[M]
% // LengthLength

Changing the label of a self-loop causes full blowup.

MM = switchLabel[M,1\[DirectedEdge]1];
MM // colplot
MM // DeterminizeFA // StateCount

Changing the label of a forward edge also causes blowup, but the situation is more complicated, we get (2^(n-2)) states.

switchLabel[M,1\[DirectedEdge]2] // DeterminizeFA // StateCount

Circulants (n,1,2)

A circulant with strides 1 and 2, on n states. Again, there is one zigzag, the whole graph.

M= With[ {n=11},
CirculantFA[ n, {1,2}, Labels->{Table[1,{n}],Table[2,{n}]} ]];
M // colplot

There is one zigzag, the whole graph.

ZigzagDecomposition[M]
% // LengthLength

Changing the label of a stride-1 transition. There is a slight dependency on the parity of n.

Table[  With[ {M= CirculantFA[ n, {1,2}, Labels->{Table[1,{n}],Table[2,{n}]} ]},StateCount[ DeterminizeFA[switchLabel[ M, 1\[DirectedEdge]2 ] ] ] ], {n,3,12} ]

For stride-2 transitions there is is uniform full blowup.

Table[  With[ {M = CirculantFA[ n, {1,2}, Labels->{Table[1,{n}],Table[2,{n}]} ]},StateCount[ DeterminizeFA[switchLabel[ M, 1\[DirectedEdge]3 ] ] ] ], {n,4,12} ]

Incidentally, all the power automata are already reduced.

Table[  With[ {M = CirculantFA[ n, {1,2}, Labels->{Table[1,{n}],Table[2,{n}]} ]},StateCount[ MinimizeFA[switchLabel[ M, 1\[DirectedEdge]3 ] ] ] ], {n,4,12} ]

Circulants (n,-1,1)

A circulant with strides -1 and 1, on n states.

M= With[ {n=10},
CirculantFA[ n, {-1,1}, Labels->{Table[1,{n}],Table[2,{n}]} ]];
M // colplot

For even n, there are two zigzags.

ZigzagDecomposition[M]
% // LengthLength

Exploiting various isomorphisms, there is only one possible switch and it causes full blowup.

MM = switchLabel[M,1\[DirectedEdge]2];
MM // colplot
MM // DeterminizeFA // StateCount

Odd number of nodes.

M= With[ {n=9},
CirculantFA[ n, {-1,1}, Labels->{Table[1,{n}],Table[2,{n}]} ]];
M // colplot

This time, there is only one zigzag.

ZigzagDecomposition[M]
% // LengthLength

Again, there is essentially only one possible switch and it causes full blowup.

MM = switchLabel[M,1\[DirectedEdge]2];
MM // colplot
MM // DeterminizeFA // StateCount

Circulants (n,1,3)

Circulants with strides 1 and 3, on n states.
The number of zigzags depends on the parity of n.

Table[
Length@ZigzagDecomposition@CirculantFA[ n, {1,3}, Labels->{Table[1,{n}],Table[2,{n}]} ],{n,3,12}]

Up to isomorphism, there are two choices to switch labels. 
Stride-1 transitions. In all cases there is blowup, but the details are a bit messy.

Table[  With[ {M= CirculantFA[n,{1,3},Labels -> {Table[1,{n}],Table[2,{n}]}]},
With[ {MM =  DeterminizeFA[switchLabel[M,1\[DirectedEdge]2]]}, {StateCount [M],StateCount[MM],2^StateCount[M]-StateCount[MM]} ]] , {n,4,12} ] // TableForm

Stride-3 transitions produce full blowup in all cases.

Table[  With[ {M= CirculantFA[n,{1,3},Labels -> {Table[1,{n}],Table[2,{n}]}]},
With[ {MM =  DeterminizeFA[switchLabel[M,1\[DirectedEdge]4]]}, {StateCount [M],StateCount[MM],2^StateCount[M]-StateCount[MM]} ]] , {n,5,12} ] // TableForm

Circulants (n,1,4)

Circulants with strides 1 and 4, on n states.
This time, the number of zigzags depends on n mod 3.

Table[
Length@ZigzagDecomposition@CirculantFA[ n, {1,4}, Labels->{Table[1,{n}],Table[2,{n}]} ],{n,3,12}]

Up to isomorphism, there are two choices to switch labels. In all cases there is blowup, but the details are a bit messy.

M= With[ {n=10},
CirculantFA[ n, {1,4}, Labels->{Table[1,{n}],Table[2,{n}]} ]];
M // colplot
switchLabel[M,1\[DirectedEdge]2]// DeterminizeFA // StateCount
switchLabel[M,1\[DirectedEdge]5]// DeterminizeFA // StateCount

Up to isomorphism, there are two choices to switch labels. 
Stride-1 transitions. In all cases there is blowup, depending on n mod 4.

Table[  With[ {M= CirculantFA[n,{1,4},Labels -> {Table[1,{n}],Table[2,{n}]}]},
With[ {MM =  DeterminizeFA[switchLabel[M,1\[DirectedEdge]2]]}, {StateCount [M],StateCount[MM],2^StateCount[M]-StateCount[MM]} ]] , {n,4,12} ] // TableForm

Stride-4 transitions produce full blowup in all cases.

Table[  With[ {M= CirculantFA[n,{1,4},Labels -> {Table[1,{n}],Table[2,{n}]}]},
With[ {MM =  DeterminizeFA[switchLabel[M,1\[DirectedEdge]5]]}, {StateCount [M],StateCount[MM],2^StateCount[M]-StateCount[MM]} ]] , {n,6,12} ] // TableForm

De Bruijn

The (2,k) de Bruijn graph has (2^(k-1)) zigzags of size 4 each. Since one bit suffices to determine the labels on a zigzag, so there are (2^(2^(k-1))) permutation labelings (ignoring isomorphisms).

G = DeBruijnGraph[2,3];
ZZ = ZigzagDecomposition[G];
ZZ // LengthLength
HighlightGraph[ G,ZZ ]

A permutation labeling on the de Bruijn graph.

sa = GraphToFA[ Graph[Range[8],labelZigzags[ZZ,0]], Alpha[2],All,All ];
PropertyQFA[ sa, {"Deterministic","Codeterministic"}]
sa // colplot

Z = First@ZigzagDecomposition[sa]

sa // TransitionList

Switching the labels in the first zigzag.   Switching the self-loop always causes full blowup.

Table[ switchLabel[sa,e] // DeterminizeFA // StateCount, {e,Z} ]

A table for all permutation labelings and all switches.

tab = Table[
With[ { sa = GraphToFA[ Graph[Range[8],labelZigzags[ZZ,b]], Alpha[2],All,All ]},
Table[ StateCount@DeterminizeFA[switchLabel[sa,e]], 
{e,SortBy[TransitionList[sa],TransitionStates]}]], {b,0,15}];

The 4 gray columns correspond to the self-loops and the dual edges in their zigzags. Switching these edges always causes full blowup, regardless of the permutation labeling.

PlotMatrix[tab/. 256->LightGray,ColorFunction->"Rainbow"]

Overall, exactly half of the semiautomata produce full exponential blowup. 
Alas, this is an open conjecture, computationally verified up to k = 5.

Count[tab,256,{2}]

The least blowup is still to size 240.

256-tab // Flatten // Frequencies

Some permutation labelings produce almost full blowup regardless of which transition is switched.

Total /@ tab
Max[%]/16 // N

Random

Construct a random (2,2)-regular graph on 12 nodes and its zigzag decomposition.
It appears that the blowup for the associated 1-permutation automata is fairly close to 4096, on average.

nn=12;
V = Range[nn];
ed= Join[ Thread[DirectedEdge[V,RandomSample[V],ConstantArray[1,nn]]],
Thread[DirectedEdge[V,RandomSample[V],ConstantArray[2,nn]]] ];
H = Graph[V,ed];
ZZ = ZigzagDecomposition[H]
HighlightGraph[ Annotate[ H,
 {VertexLabels->Placed["Name",Center],VertexStyle->LightBlue,VertexSize->Large,EdgeStyle->Thick} ],ZZ ]

Construct a random permutation labeling on H and determinize the corresponding 1-permutation automata.

G = Graph[Range[12],labelZigzags[ZZ,RandomInteger[2^Length[ZZ]-1]]];

Table[ With[ {GG = switchLabel[G,ed]},
StateCount@DeterminizeFA@GraphToFA[GG,Alpha[2],All,All] ], {ed, EdgeList[G]} ]
% // Mean // N

Minimization

De Bruijn

Constructing a de Bruijn automaton from scratch: state set is Q = ((Σ )^( <= k)).

ClearAll[deb]
deb[a_String,k_Integer?Positive][s_String] := If[StringLength[s]<k, StringJoin[s,a],StringJoin[StringDrop[s,1],a]];

M = GenerateFA[ "",  {deb["a",4],deb["b",4]}, Alpha[2],
	(#=="")&,(StringLength[#]==4&& StringTake[#,1]=="b")&, Type->"DFA", StateType->"Shallow" ]

The automaton is a binary tree grafted on top of a de Bruijn graph.

M // colplot

Incidentally, the same machine can be obtained via the transformation automaton of the de Bruijn automaton.

MM =PositionFA[-4->"b",Alpha[2]] // DeterminizeFA // TransformationDFA
IsomorphicQDFA[MM,M]

The machine behaves properly: it accepts all strings x such that (Subscript[x, -4])= b.

LanguageFA[ M, 5  ]
LanguageFA[ M, 12, SizeOnly->True ]

But minimization smashes the tree part down into the de Bruijn automaton; we only need 16 states.

MM = MinimizeDFA[ M, StateType->"Indexed" ];
MM // StateCount

This can also be seen from the cover map from M to M M.

CoverQDFA[ M, MM , Full->True ]

Here is the same de Bruijn automaton generated by a regex.

MMM = MinimizeFA@RegexToFA[  RET[RES[REP["a","b"]],"b",REP["a","b"],REP["a","b"],REP["a","b"] ], Alpha[2] ];
MMM // colplot

Again, the cover map.

CoverQDFA[ M, MMM , Full->True ]
cm = Last[%];

Map[ First,GatherBy[Normal[cm],Last],{2}] //EpsFromEmpty// TF2

All the machines are duly equivalent.

EquivalentQFA[{M,MM,MMM}]

The machine M from above has a structured state set:

M // StateList // EpsFromEmpty

States can be preserved under minimization.  This can be helpful to understand the structure of a machine.

Table[ StateList@MinimizeFA[M,StateType->tp], {tp,{"Indexed","Shallow","Deep"}} ] // Column[#,Spacings->1]&

Slow Minimization

Here is an example where Moore’s standard minimization algorithm performs poorly (no, not the usual simple path).

m1=DeterminizeFA[RegexToFA[ RET[RES[REP["a","b"]],"aabaabaab"],Alpha[2]]]

m1 // colplot

{m2,{t2}}=Reap@MinimizeDFA[m1,DoTrace->True];

Grid[t2,Spacings->2,Background->LightYellow, Frame-> All, FrameStyle->GrayLevel[0.8]  ]

Brzozowski Minimization

Somewhat surprisingly, minimization can be accomplished by reversing and determinizing twice.

m0 = PositionFA[ -5->"a", Alpha[2] ];
m1 = ReverseFA[m0];
m2 = DeterminizeFA[m1];
m3 = ReverseFA[m2];
m4 = DeterminizeFA[m3];
StateCount[{m0, m1, m2, m3, m4}]

colplot /@ {m0, m1, m2, m3, m4}  // GraphicsColumn

IsomorphicQDFA[MinimizeFA[m0],m4]

Random DFA

Generating a random DFA, brute force and ignoring all finer points.

nn = 20;
{Q,tr} = Closure[  1, Table[RandomInteger[{1,nn}]&,{2}], Cayley->True ];
q = Max@VertexOutComponent[Graph[tr],1];
M = GraphToFA[Graph[Range[nn],tr], Alpha[2],{1},{q}]

For small number of states, the minimal machine is only about 20% on average.

GraphicsRow[ colplot/@{M, MinimizeFA[M]} ]

checkMinimal[n_Integer] := 
Module[{Q,tr,q,M},
{Q,tr} = Closure[  1, Table[RandomInteger[{1,n}]&,{2}], Cayley->True ];
q = Max@VertexOutComponent[Graph[tr],1];
M = GraphToFA[Graph[Range[n],tr], Alpha[2],{1},{q}];
StateCount[{M,MinimizeFA[M]}]
];

tab = Sort@Table[  checkMinimal[50] , {200} ]; 
ListPlot[ Thread@tab, PlotStyle->PointSize[Medium]]
1/Divide@@@tab // N // Mean

Sample Languages

Forbidden Factors

Let L be the the language of all words not containing any of the factors   aaa, aba, bab, bbb  over the two-letter alphabet Σ = {a,b}.   We construct the minimal DFA for L  using  ConcatenateFA.

m = With[{m0=FiniteLanguageFA[{"aaa","bbb","aba","bab"},Alpha[2],Type->"Quotient"],
all = UniversalFA[Alpha[2]]},
	MinimizeFA[ComplementFA[ConcatenateFA[all,m0,all]]]]

Table[  {p,PropertyQFA[ m,p ]}, {p,PropertyQFA[]} ]  // TableForm

The growth function appears to be eventually constant.

LanguageFA[m,16,SizeOnly->True]

Which fact we can verify via the generating function and some simplification of infinite series.

Clear[x]
gs=GrowthFunctionDFA[m,x]
Series[gs,{x,0,10}]

A complete proof (assuming we trust Simplify and GrowthFunctionDFA).

Simplify[gs==1+2 x+4 (∑_(i=2)^∞)(x^i)]

The complement  (SuperStar[Σ])- L  must be an ideal. From the diagram, we have a right ideal, but closure on the left is not obvious.

mc = ComplementFA[m];
mc // colplot

all = UniversalFA[Alpha[2]] ;
EquivalentQFA[ ConcatenateFA[all,mc,all], mc ]

We compute a DFA accepting a base for this ideal. Clearly, the DFA has a finite language.

mc // StateList

base = LanguageFactorFA[ mc, Type->"MinimalFactor" ]

base //colplot

The whole cover language consists of all factors of the infinite word  (((aabb))^( ω)).

EnumFormZero[LanguageFA[m,12]]

Even Unequal

Consider the language of words of length 2n over {a,b} containing an a b or b a in an odd position: 
	(Subscript[L,  n]) =  { u  s t v |  u  even length,  s≠t  ∈ {a,b}  } ⊆ (({a,b})^(2n)).

Claim:  The minimal DFA for  (Subscript[L,  n])  has  5n  states.

Note that the languages (Subscript[L, n]) are quite large, so a brute force construction of the automata will fail for relatively small n.

ue = {"ab","ba"};
buildLn[n_Integer?Positive] := 
Union@Flatten@Table[ Concatenate@@@CartesianProduct[ Words[{2i}],ue,Words[{2n-2i-2}]], {i,0,n-1} ];

Strings of length 6 in the unequal language.

buildLn[3]

The growth rate up to length 16 and the corresponding sequence function.

Table[ Length[buildLn[n]], {n,8} ]
FindSequenceFunction[%,z]

Constructing the minimal DFA using quotients.

unequal2[ n_Integer]:=FiniteLanguageFA[ buildLn[n],Alpha[2],Type->"Quotient"];

M = unequal2[4];
M // PlotFA

The state complexity of the machines.

Table[ StateCount[unequal2[n]], {n,8} ]

UnEqual

Consider the language of words of length 2n over {a,b} where the first half differs from the second half.
	(Subscript[L,  n]) =  { u  v |  u, v∈ (({a,b})^n), u !=v  } ⊆ (({a,b})^(2n)).

Claim:  The state complexity of  (Subscript[L,  n])  is  3·(2^n)+ n - 2. 

First a brute-force construction of the minimal DFA via the quotient automaton, see QuotientDFA.  Note that the cardinality of (Subscript[L,  n]) is (2^( 2n)) - (2^( n)), so we have to constrain our experiments to reasonably small values of n.

unequal[n_Integer]:=
With[{L=Words[{n}]},
FiniteLanguageFA[ StringJoin/@DeleteCases[CartesianProduct[L,L],{x_,x_}],Alpha[2], Type->"Quotient"]];

We verify that the claim holds for n ≤ 6 (we have removed the sink from the automata).

Table[StateCount[unequal[n]],{n,8}]
% === Table[3 (2^n)+n-2,{n,8}]

Here is a closer look at n = 3.

m=unequal[3];
PlotFA[m,Type->"MultiColor",VertexSize->Medium]

The structured state set here consists of quotients of the original unequal language.

Q = StateList[m] // EpsFromEmpty

Here are some simple tests.

ClearAll[leftQuot]
leftQuot[a_String][_?EpsQ] := Nothing;
leftQuot[a_String][w_String] := 
If[ StringTake[w,1]===a, StringDrop[w,1], Nothing ];
leftQuot[a_String][L_List] := leftQuot[a] /@ L;

leftQuot["a"][Q[[1]]]
Position[Q,%]

leftQuot["b"][Q[[1]]]
Position[Q,%]

Closure[  Q[[1]], {leftQuot["a"],leftQuot["b"]} ]  // Length

Clearly, the states in the quotient automaton for (Subscript[L, n]) are organized in layers where states at layer k are of the form P ⊆ (Σ^( 2n-k)) and transitions lead from layer k to layer k+1 (except for the sink).  In fact,  the first n layers form full binary tree since the behaviors of these states are necessarily distinct.  
In general, there is a leaf x  corresponding to (Σ^n)-{x} for each word x ∈ (Σ^( n)).   So the first tree accounts for (2^(n+1))-1 states.  The remainder of the machine has two kinds of states: those where a witness for inequality of u and v has already been found, and those where we are still waiting for such a witness.

AssignTransitionFunction[δ,m]
Table[ {ToWord[w,Alpha[2]],LanguageFA[ SetInitial[m,{δ[1,w]}], {2} ]},{w, Tuples[{1,2},4]} ]   // GatherBy[#,Last]&  // TF2

More precisely, the first type is of the form  δ((Subscript[q, 0]),u x)  where x is not a prefix of u ∈ (Σ^( n)) has behavior (Σ^(2n-|u x|)) and the second type is of the form  δ((Subscript[q, 0]),u x)  where x is a prefix of u ∈ (Σ^( n)) and has behavior (Σ^(2n-|u x|))-{y}  where u = x y. But then there are n states of the first type, and (2^n)-1 states of the second type (these form another tree which is upside-down compared to the first, and has as root the sink of the DFA).

Locally UnEqual

A modified version of the UnEqual language is based on the condition that (Subscript[x, i])!= (Subscript[x, i+n]) for some position i <= n. Again, the cardinality of (Subscript[L,  n]) is again  (2^( 2n)) - (2^( n)), but the condition is now local (very much in the spirit of choosing a good variable ordering for BDDs).

Claim:  The state complexity of  (Subscript[L,  n])  is  5n - 1.

wrd = ToWord[Alpha[2]];
uneq = wrd /@ Select[ Tuples[{1,2},8], Or@@(UnsameQ@@@Partition[#,2])& ];

M = FiniteLanguageFA[uneq,Alpha[2],Type->"Quotient"];

PlotFA[M,Type->"MultiColor"]

Table[ With[{L = wrd/@ Select[ Tuples[{1,2},2nn], Or@@(UnsameQ@@@Partition[#,2])& ]},
StateCount@FiniteLanguageFA[L,Alpha[2],Type->"Quotient"]], {nn,8}]
FindSequenceFunction[%,z]

UnPalindrome

Consider the language (Subscript[L, n]) of non-palindromes of length 2n:

	(Subscript[L,  n]) =  { u v |  u, v∈ (({a,b})^n), u≠(v^op)  } ⊆ (SuperStar[{a,b}]).
	
Claim:  The state complexity of  (Subscript[L,  n])  is  3·(2^n)+ n - 2. 

This is the same as the UnEqual language from above.

unpalindrome[n_Integer]:=With[{L=Words[{n}]},FiniteLanguageFA[ StringJoin/@Select[CartesianProduct[L,L],#[[1]]=!= StringReverse[#[[2]]]&],Alpha[2], Type->"Quotient"]];

We verify that the claim holds for n ≤ 6 (we have removed the sink from the automata).

Table[StateCount[unpalindrome[n]],{n,6}]
% === Table[3 (2^n)+n-2,{n,6}]

Here is a closer look at n = 3.

m=unpalindrome[3];
PlotFA[m,Type->"MultiColor",VertexSize->Medium]

The structured state here consists of quotients of the original unpalindrome language.

Q = StateList[m]

Here are some simple tests.

ClearAll[leftQuot]
leftQuot[a_String][_?EpsQ] := Nothing;
leftQuot[a_String][w_String] := 
If[ StringTake[w,1]===a, StringDrop[w,1], Nothing ];
leftQuot[a_String][L_List] := leftQuot[a] /@ L;

leftQuot["a"][Q[[1]]]
Position[Q,%]

leftQuot["b"][Q[[1]]]
Position[Q,%]

Closure[  Q[[1]], {leftQuot["a"],leftQuot["b"]} ]  // Length

The rest of the analysis is similar to the UnEqual language.

Inverse Transition Matrix

For a finite language, we can extract its cardinality from the inverse of the transition matrix of the canonical DFA.

L = Union[StringJoin@@@FlattenOne@Table[   Table[ RandomChoice[{"a","b","c"},k], {k,2,5}], {5}]]

m = FiniteLanguageFA[ L, Alpha[3], Type->"Quotient" ];

m // colplot

Remove the sink and extract the transition matrix A.

mm = TrimFA[m];
A = Total@BooleanTransitionMatrix[mm];
PlotMatrix[A,Mesh-> All, MeshStyle-> {{GrayLevel[0.8],Thin},{GrayLevel[0.8],Thin}}]

Note that  (I-A) (A^( * ))= I.  Thus I - A  is invertible and we can read off the size of the language from the inverse.

n = StateCount[mm];
Det[IdentityMatrix[n]-A]

B= Inverse[IdentityMatrix[n]-A];
With[ {ini=ToBitVector[InitialStateList[mm],Range[n]], fin=ToBitVector[FinalStateList[mm],Range[n]]}, 
ini.B.fin ]
Length[L]

PlotMatrix[B,Mesh->All, MeshStyle-> {{GrayLevel[0.8],Thin},{GrayLevel[0.8],Thin}}]

Magmas and Shuffle

Magmas

A magma is a set together with a binary operation, without any additional constraints and in particular without associativity requirements.  Given a sequence of elements in a finite magma, we can evaluate under left or right associative multiplication (among others). 

Claim:  The sequences that evaluate to the same element under left and right associative multiplication form a regular language.

Left/Right Multiplication

The magma is given by an explicit Cayley table for the multiplication.

Given the table, we implement dyadic multiplication, and left and right multiadic multiplication according to the given table.
It will be useful later to augment the carrier set  [n]  by a “neutral” element 0 (we are working in a magma with neutral element). We extend the multiplication table accordingly.

The code uses the global $CT for Cayley table.

Clear[λ,ρ,nn,$CT,A]
SetAttributes[{ρ,λ,μ},Listable]
nn = 3;
A= Alpha[nn];
indx = ToIndex[A];
wrd = ToWord[A];
λ[i_Integer]:=i;
λ[i_Integer,j_Integer]:=$CT[[i+1,j+1]];
λ[i_Integer,j_Integer,k___Integer]:=λ[λ[i,j],k];
ρ[i_Integer]:=i;
ρ[i_Integer,j_Integer]:=$CT[[i+1,j+1]];
ρ[k___Integer,i_Integer,j_Integer]:=ρ[k,ρ[i,j]];
λ[x_?WordQ]:=wrd[{λ@@indx[x]}];
ρ[x_?WordQ]:=wrd[{ρ@@indx[x]}];

We generate a Cayley table at random (and then add the parts for the neutral element). For sequences of length 2 there should be no difference, but for longer sequences we may get different answers depending on grouping.  First a random example.

$CT = ArrayReshape[ RandomInteger[{1,nn},nn^2 ], {nn,nn}];
$CT = Join[ Thread[{Range[0,nn]}],Join[ {Range[nn]},$CT],2];
TableForm[ $CT, TableHeadings->{Range[0,nn],Range[0,nn]}]

AllTrue[ Tuples[Range[nn],2],λ@@#==ρ@@#& ]
Select[ Tuples[Range[nn],3],λ@@#==ρ@@#& ]
% // Length

For the rest of this section, we use the rock/paper/scissors magma. In this case, 21 words of length 3 are “associative.”

nn = 3;
$CT = {{1,2,1},{2,2,3},{1,3,3}};
$CT = Join[ Thread[{Range[0,nn]}],Join[ {Range[nn]},$CT],2];
TableForm[ $CT, TableHeadings->{Range[0,nn],Range[0,nn]}]

AllTrue[ Tuples[Range[nn],2],λ@@#==ρ@@#& ]
Select[ Tuples[Range[nn],3],λ@@#==ρ@@#& ]
% // Length

The Component Machines

To construct the maine automaton we first build machines Mleft[s] that accept all strings in  (Σ^( +)) that evaluate to s under λ.   The appropriate state set is Σ  augmented by a "neutral" element 0. These automata are naturally DFAs: the right action of the transition function of a DFA automatically translates into left-associative multiplication in this context.

ClearAll[Mleft]
Mleft[s_Integer] := GenerateFA[ 0,  Table[ Evaluate[λ[#,a]]&,{a,nn}],A, (#==0)&, (#==s)& ]

Mleft[1] // colplot

Here are all n machines; clearly, they differ only in their final states.

colplot[ Mleft[#]]& /@ Range[nn] // GraphicsRow

Some sanity checks.

Select[Words[{4},A],λ[#1]=="b"&]
% === LanguageFA[Mleft[2],{4}]

We can check that the union of the 3 automata accepts all non-empty words.

mm = UnionFA@Table[ Mleft[i], {i,nn} ]//MinimizeFA;
mm // colplot

The machines for right-associative multiplication are a bit harder to come by.  Here we need transitions  p (Subscript[⟶, a]) q  whenever  p = a · q.  The initial state is then s ∈ Σ  and the final state ϵ (we use the same state set as for the other machines).  First, the transitions: part 1 is a translation of the Cayley matrix, part 2 is a (Subscript[⟶, a]) ϵ.

tr1 = Flatten[ MapIndexed[DirectedEdge@@Reverse[Append[#2,#1]]&,Rest/@ Rest@$CT,{-1}]]
tr2 = Table[DirectedEdge[i,0,i],{i,nn}];
G = Graph[ Range[0,nn],Sort[ Join[tr1,tr2] ] ];

The actual machines; this time, the initial state moves around.

Clear[Mright]
Mright[s_Integer]:= GraphToFA[ G,A,{s}, {0},  StateType->"Shallow" ];

colplot[ Mright[#]]& /@ Range[nn] // GraphicsRow

Again some modest sanity checking.

Select[Words[ {4},A],ρ[#]=="a"&]
% === LanguageFA[Mright[1],{4}]

MinimizeFA[UnionFA@@Table[Mright[i],{i,3}]] 
LanguageFA[%,10,SizeOnly->True]

Looks good.

The Principal Machine

Now we construct the main machine, a sum of products of the component machines from above.

mlr = IntersectionFA[ Mleft[1], Mright[1] ];
mlr // colplot

LanguageFA[ mlr, {4} ]
λ /@ % 
 ρ /@ %%

The master machine is generated by taking the disjoint union of the various intersections.

M = UnionFA@Table[ IntersectionFA[ Mleft[i], Mright[i] ], {i,3} ];
M // colplot

The minimal DFA and its diagram.

MM=MinimizeFA[M];
MM // StateCount
MM // colplot

We can test that the machine works as advertised.

L=LanguageFA[MM,{3,6}];
λ[L]===ρ[L]

The growth function of  L and the corresponding 3rd order recurrence.

LanguageFA[MM,12,SizeOnly->True]
FindSequenceFunction[%]

Alternatively, the generating function.

Clear[z]
GrowthFunctionDFA[MM,z] // TraditionalForm

One can now investigate other properties of the magma. For example, if there is no sink in the minimal DFA for L, then every word u has an extension u v ∈ L.

TrapStateList[MM]

Shuffle

We construct a machine for   K = { x |  x || u  ⋂ L  ≠ ∅  }  where u is a fixed word, and L a regular language, given by a FSM M.

The new machine uses a state set of  Q × [m+1]  where  m  is the length of u.  First,  a walk through the construction. We generate a suitable sample machine M for the language  L = (SuperStar[a])b (SuperStar[a])b (SuperPlus[c])(SuperStar[a]).

A3 = Alpha[3];
M=MinimizeFA[RegexToFA[RET[RES["a"],"b",RES["a"],"b",RES["c"],"c",RES["a"]],A3]]

Extract the transition function and the initial state.

AssignTransitionFunction[delta,M]
q0=InitialState[M];

Let’s use u = b c.  Unpack u into a list of characters (in index notation) and record its length.

u = "bc";
uchar=ToIndex[u,A3]
ulen=Length[uchar]

The transition functions used to generate the new machine. next[0] handles ϵ-transitions (though we currently pretend these are ordinary transitions associated with a letter to fit into the framework of Closure)
	(p,i) -> (p · (Subscript[u, i+1]), i+1)
and next[s] takes care of transitions
	(p,i) -> (p·s,i).

ClearAll[next,BOT]
next[0][{p_,i_}]:=With[{ii=i+1},If[ii≤ulen,{delta[p,uchar[[ii]]],ii},BOT]];
next[s_][{p_,i_}]:={delta[p,s],i};
next[_][BOT]:= BOT;

Closure builds the state set and the transition relation.

{Q,tr}=Closure[{{q0},0},Table[ Evaluate[next[s]],{s,0,3}],Cayley->True ]

It remains to select the final states.

fin = PositionList[ Q,Select[Q,#=!=BOT && SubsetQ[FinalStateList[M],First[#1]]&&Last[#1]==ulen&]]

We also need to fix the symbol index in the transitions (the empty word  ϵ  is supposed to be indexed by 0).

G =Graph[ TransitionsMap[ tr, Identity,#-1& ]];
fa=GraphToFA[ G, A3,{1},fin, StateType->{"Indexed","Shallow"} ]

fa // colplot

Recall that u = b c. Here are the first few words in L and K:

LanguageFA[M, 5 ]
LanguageFA[fa,5 ]

Sanity check:

K5 = LanguageFA[M,{5}] ;
Select[ Words[ {3},Alpha[3]], Intersection[WordShuffle[#,u],K5]=!={}& ] 
LanguageFA[fa,{3}]

Mu = MinimizeFA[fa];
colplot /@ {M,Mu}  // GraphicsColumn

The whole operation can is packaged into a single function thus. This is for a 3-letter alphabet only.

ClearAll[shuffleWordFA]
shuffleWordFA[M_?FSMQ,u_String ]:=
Module[{delta,q0,uchar,ulen,next,Q,tr,fin,BOT,G},
uchar=ToIndex[u,A3];
ulen=Length[uchar];
AssignTransitionFunction[delta,M];
q0=InitialState[M];
next[0][{p_,i_}]:=With[{ii=i+1},If[ii≤ulen,{delta[p,uchar[[ii]]],ii},BOT]];
next[s_][{p_,i_}]:={delta[p,s],i};
next[_][BOT]:= BOT;
{Q,tr}=Closure[{{q0},0},Table[ Evaluate[next[s]],{s,0,3}],
	Cayley->True,Bound->500 ];
fin = PositionList[ Q,Select[Q,#=!=BOT && SubsetQ[FinalStateList[M],First[#1]]&&Last[#1]==ulen&]];
G =Graph[ TransitionsMap[ tr, Identity,#-1& ]];
GraphToFA[ G, A3,{1},fin, StateType->{"Indexed","Indexed"}  ]
];

Another example: shuffling with b b.

Mu = MinimizeFA[shuffleWordFA[M,"bb"]];
colplot /@ {M,Mu}  // GraphicsColumn

Nothing changes if we append c a to the shuffle word.

Mu = MinimizeFA[shuffleWordFA[M,"bbca"]];
colplot /@ {M,Mu}  // GraphicsColumn

Regular Expressions

Example Even-even

An expression using the headers REP, RET, RES corresponding to the operators in the Kleene algebra.

e0=REP["aa","bb"];
e1=REP["ab","ba"];
e00=RES[REP[e0,RET[e1,RES[e0],e1]]]

Build a regular expression for the language over {a,b}  consisting of all strings with an even number of a’s and even number of b’s. Using the standard Thompson conversion (begin/exit automata with ϵ-moves).

m1=RegexToFA[e00,Alpha[2] ];
% // colplot

m2=EpsilonEliminationFA[m1];
% // colplot

m2 // DeterminizeFA;
% // colplot

m3=MinimizeFA[m2];
% // colplot

We can trace the conversion process and show all the intermediate begin/exit-automata.

TableForm[Union[Flatten[Trace[RegexToFA[e00,Alpha[2]],BEFA[_Integer,_]]]]]

Using a different conversion algorithm due to McNaughton-Yamada we get a different non-deterministic machine.

m4 = RegexToFA[ e00, Alpha[2], Type->"NNFA"];
m4 //colplot

EquivalentQFA[m3,m4]

RE for odd-odd

From the last section, we have a regular expression e00 for even/even parity strings over Σ = {a,b} .

e00

An expression e11 for odd/odd parity is a bit larger: there has to a be an a adjacent to a b, and we can split the string into two even/even parts at that point. Since letters do not commute, we need two expressions of this type.

e11=REP[RET[e00,"ab",e00],RET[e00,"ba",e00]]

MinimizeFA[RegexToFA[e11,Alpha[2]]]
% // colplot

Better solution:

RET[ RES[e0],e1,e00 ] 
RegexToFA[ %, Alpha[2]] // MinimizeFA // colplot

So how about odd/even?  Unfortunately a simple split at an occurrence of a does not work.

e10=RET[e00,"a",e00];
mm=MinimizeFA[RegexToFA[e10,Alpha[2]]];
% // colplot

The problem lies with splits such as  bab.  We construct a machine for odd/even by hand and check that our expression so far misses these words.

m10=IntersectionFA[SemilinearDFA["a",1,2,Alpha[2],Type-> "Factor"],SemilinearDFA["b",0,2,Alpha[2],Type-> "Factor"]];
LanguageFA[ComplementFA[m10,mm],8 ]

So we use two splits:  even b-count on both sides or odd b-count on both sides.

e10=REP[RET[e00,"a",e00],RET[e00,"b",e00,"a",e00,"b",e00]]

We obtain large intermediate machines, but the final automaton only has 4 states.

mre = RegexToFA[e10,Alpha[2]];
mre // StateCount
mred = DeterminizeFA[mre];
mred // StateCount
mrem = MinimizeFA[mred];
mrem // colplot

EquivalentQFA[mrem,m10]

The cover relation from m10 to

EquivalentQFA[m10,mrem,DoTrace->True] // Last // TF

Works.
Here is another solution obtained by taking the derivative of the even/even expression.

E10=RET[REP["a",RET["b",RES[REP["aa","bb"]],REP["ab","ba"]]],e00]

M = MinimizeFA@RegexToFA[E10,Alpha[2]];
EquivalentQFA[M,m10]

Example "no factor a a a a".

Complements are a bit problematic to express with regular expressions.

exp=RET[REP[Eps,"a","aa","aaa"],RES[REP["b","ba","baa","baaa"]]]

m0 = EpsilonEliminationFA@RegexToFA[exp,Alpha[2]];
m1=DeterminizeFA[m0];
m2=MinimizeFA[m1];
gr = colplot /@ {m0,m1,m2} // GraphicsRow

Verify that m1 works properly, first empirically and then by constructing the minimal automaton in a different way. The two machines turn out to be identical.

LanguageFA[  ComplementFA[m1],6]

MinimizeFA[ComplementFA[SemilinearDFA["aaaa",{1,1,{},{0}},Type->"Factor"]]]
EquivalentQFA[%,m1]

Divisible by 3

Numbers divisible by 3 in binary, MSD first, with leading zeros.

AutomataDefaults["REGEXalpha",Alpha[2,<|"AlphabetType"->"Digit"|>]]

reg = RES[ REP[ "0",RES[ RET[ "1",  RES[ RET["0",RES["1"] ,"0" ] ],"1" ] ] ] ]

fa = RegexToFA[reg]

Our presentation allows for leading zeros.

L =LanguageFA[  fa, 5 ]

FromDigits[#,2]& /@ Rest@Flatten[L] // Union

machs ={ fa,  EpsilonEliminationFA[fa],DeterminizeFA[fa], M = MinimizeFA[fa]};

PlotFA[ #, VertexSize->Medium,  Type->"MultiColor",VertexSize->Small ]& /@ machs// GraphicsColumn

The growth function is easy to find in this case.

LanguageFA[ M, 14, SizeOnly->True ]
% // FindSequenceFunction[#,z]&

Conway's (Subscript[R, n])

The following regular expressions are equivalent to (((a+b))^( * )), for all n.
However, this equivalence cannot be proven from Conway’s axioms (Subscript[C, 1])-(Subscript[C, 14]) . 

Set a suitable default alphabet for regular expressions.

AutomataDefaults["REGEXalpha",Alpha[2,"Digit"]];

Clear[REPower,ConwayRn]
REPower[ee_,0]:=Eps;
REPower[ee_,1]:=ee;
REPower[ee_,n_Integer?NonNegative]:=RET@@Table[ee,{n}];
ConwayRn[n_Integer]:=With[{e=RET["a",RES["b"]]},REP[RES["b"],RET[RES["b"],RES[REPower[e,n]],REPower[RET[REP[Eps,"a"],RES["b"]],n]]]];

Check equivalence for n = 12.  The NFAE produced by conversion from the regular expression has 104 states.

fa = RegexToFA[ ConwayRn[12],Alpha[2]];
fa // StateCount
PlotFA[ fa,  Type->"MultiColor", VertexSize->Medium,EdgeStyle->Thick]

Determinization gets us down to 26 states.  Note that all states are final.

dfa = DeterminizeFA[fa]
PlotFA[ dfa, Type->"MultiColor",VertexSize->Large]

And minimization produces a universal machine.

MinimizeFA[dfa]

Transformation Semigroups

De Bruijn Automaton

We construct the standard de Bruijn automaton for “third symbol from the end is a”.

m = DeterminizeFA@PositionFA[ -3->"b", Alpha[2] ];
m // colplot

We generate the corresponding semigroup.

S =SemigroupGenerate[m]

SemigroupCayleyTable[S] // PlotMatrix[#, ColorFunction->"Rainbow"]&

The resulting data structure also maintains information about witnesses and equations.

Through[{SemigroupDegree, SemigroupOrder,SemigroupGenerators,SemigroupElements,SemigroupWitnesses,SemigroupEquations}[S]] // Column[#,Spacings->1]&

Witnesses are length-lex minimal. 
There are 8 idempotents in S, which happen to be constants and thus right nulls.  They are the only regular elements in S.

SemigroupElements[S,"Idempotent"] // Sort

SemigroupElements[S,"Regular"] // Sort

A table of semigroup elements with various special properties.

Table[ {type,SemigroupElements[S, type ]}, {type,{"Idempotent","LeftNull","RightNull","Null","LeftUnit","RightUnit","Unit","Regular"}}] // Grid[#,Alignment->Left]&

It is often convenient to set up a witness map S ⟶(SuperStar[Σ]), in particular when dealing with D-classes.

AssignFunction[ wit, SemigroupElements[S]-> SemigroupWitnesses[S],"FunctionAttributes"->Listable ]
wit @ SemigroupElements[S]

Generate the semigroup again, this time with Green’s relations. Below, grn is a list of the L, R and D classes of S, respectively.
There are 6 trivial D-classes and one additional regular D-class of size 8, consisting of the idempotents.

{S,grn} = SemigroupGenerate[ m, "GreensRelations"->True];

The L-classes are all trivial in this case.

grn[[1]]
Length /@ %

There is one non-trivial R-class, consisting of the right Anulls. The same holds for the H-classes.

Length /@ grn[[2]]
Length /@ grn[[3]]

The witnesses for the right nulls are all words of length 3.

wit@grn[[3,-1]]

Conversion to D-classes only works for regular classes. In this case, there is only one, the right nulls, a D-class of dimension (1,8,1).

DCLGreenToGrid[S,grn]
DCLDimension@%

The equations remove the first letter of all length 4 words, so this is consistent.

SemigroupEquations[S]

Full Transformation Semigroup (Subscript[𝕋, 3])

Here is the standard set of generators for the full transformation semigroup of degree 3.

gen ={SGT[{2,1,3}],SGT[{2,3,1}],SGT[{1,1,3}]};

(*gen ={SGT[{2,1,3,4}],SGT[{2,3,4,1}],SGT[{1,1,3,4}]};*)

The semigroup elements are all transformations  [3]->[3].

S = SemigroupGenerate[gen]

SemigroupCayleyTable[S] // PlotMatrix[#, ColorFunction->"Rainbow"]&

The equations here are in raw form and can be simplified.

Through[{SemigroupOrder,SemigroupDegree,SemigroupElements,SemigroupWitnesses,SemigroupEquations}[S]] // Column[#,Spacings->1]&

Assorted elements of the semigroup. All elements are regular.

Table[ {type,SemigroupElements[S, type ]}, {type,{"Idempotent","LeftNull","RightNull","Null","LeftUnit","RightUnit","Unit","Regular"}}] // Grid[#,Alignment->Left]&

Again, but this time keeping track of discovery process. Labeling the nodes by transformations is best handled by some pretty printing.

ClearAll[prnSGT]
Attributes[prnSGT]={Listable};
prnSGT[SGT[x_List]] := StringifyList[x,Fill->""];

{S,ef,eb} = SemigroupGenerate[  gen,Alignment->Right,Full->True ];

Gf = Graph[eb];
Annotate[ Gf,VertexLabels->Thread[VertexList[Gf]->prnSGT@VertexList[Gf]]]

Forward and backward edges combined.

Glr = GraphUnion[ Graph[ef],Graph[eb] , 
EdgeStyle->Flatten@{Thread[ef->Table[Darker@Red,{Length[ef]}]],Thread[eb->Table[Lighter@Blue,{Length[eb]}]]}]

Computing Green’s relations.

{S,green}=SemigroupGenerate[  gen, "GreensRelations"->Automatic ];

green // prnSGT // Column[#,Spacings->1]&

The D-classes in terms of left/right multipliers and the H block. We rearrange the classes by rank.

dcl = DCLGreenToGrid[S,green];
dcl = SortBy[ dcl, RankSGT[#[[1,1]]]&];
dcl // Column[#,Spacings->1]&

The classes in the familiar grid layout. The underlying groups are the trivial group, the two-element group, and  the symmetric group on 3 letters.

DCLDimension[dcl]
MatrixForm[prnSGT[DCLUnpack[#]]]& /@ dcl // Column

The equations produced by the generating algorithm can be simplified quite a bit.

rw = RewriteRulesSimplify[ SemigroupEquations[S] ]

The equations not involving c describe the symmetric group of order 6.

Select[ rw, !StringMatchQ[#[[1]],"*c*"]& ]

Lastly, the assorted Cayley graphs obtained during the generation process.

Table[ SemigroupCayleyGraph[gen,Alignment->dir,Full->bl ],
	{dir,{Left,Right}}, {bl,{True,False}} ]   // GraphicsGrid

Universal Squares of Languages

Two Letters

We construct a simple example of a regular language L ≠ (SuperStar[Σ]) such that L · L = (SuperStar[Σ])  over the alphabet  Σ = {a,b}.  
Note that necessarily ϵ, a, b ∈ L for any solution. 
A little experimentation produces  L = ϵ + a (SuperStar[Σ])+ (SuperStar[Σ])b.

all=RES[REP["a","b"]];
exp=REP[Eps,RET["a",all],RET[all,"b"]]

m=MinimizeFA[RegexToFA[exp,Alpha[2]]]
m // colplot

We check the growth function.

LanguageFA[m,16,SizeOnly->True]
GrowthFunctionDFA[m,z] // TraditionalForm

It is easier to inspect a few words in the complement of L.

LanguageFA[ComplementFA[m],{5}]

It seems the complement of L has the form  b (SuperStar[Σ]) a, a claim easily verified by constructing the corresponding machines.

expc=RET["b",all,"a"];
EquivalentQFA[ComplementFA[m],RegexToFA[expc,Alpha[2]]]

Next we compute a machine for L·L, and check that indeed  L · L = (SuperStar[Σ]).

mm=ConcatenateFA[m,m];
mm //colplot
PropertyQFA[mm,"Universal"]

Only the relative order of a and b matters: both correspond to idempotent elements in the syntactic semigroup.

S = SemigroupGenerate[m]

SemigroupCayleyTable[S] // PlotMatrix[#, ColorFunction->"Rainbow",Mesh->All]&

The 4 elements are all idempotent.

Length@SemigroupElements[S,"Idempotent"]

Pairs[ SemigroupWitnesses[S],SemigroupElements[S]] // Grid

RewriteRulesSimplify@SemigroupEquations[S] // Column

Only state 4 fails to be accepting, so the only “bad” word is of the form b a, but admits a factorization b:a, as claimed.

Three Letters

A slightly more ambitious example over a three-letter alphabet: 	L = (c^( * ))(ϵ + a  (SuperStar[Σ])+ (SuperStar[Σ])b) (SuperStar[c]).
Note the asymmetry between c and the other letters.

all=RES[REP["a","b","c"]];
exp=RET[RES["c"],REP[Eps,RET["a",all],RET[all,"b"]],RES["c"]]

m=MinimizeFA[RegexToFA[exp,Alpha[3]]];
m // colplot

The complement of L is a bit more complicated in this case and has the form (SuperStar[c])b (SuperStar[Σ]) a (SuperStar[c]).

LanguageFA[ComplementFA[m],{5}]

LanguageFA[ComplementFA[m],12,SizeOnly->True]
FindSequenceFunction[%,z]

expc=RET[RES["c"],"b",all,"a",RES["c"]];
EquivalentQFA[RegexToFA[expc,Alpha[3]],ComplementFA[m]]

It may help to construct the syntactic semigroup of L to understand what is going on here.

S = SemigroupGenerate[m]

SemigroupCayleyTable[S] // PlotMatrix[#, ColorFunction->"Rainbow",Mesh->All]&

This time the semigroup is already a monoid, there are 5 elements, all idempotents. (Subscript[δ, c]) is the identity, so we are essentially back in the two-letter case.

Pairs[ SemigroupWitnesses[S],SemigroupElements[S,"Idempotent"]] // Grid

RewriteRulesSimplify@SemigroupEquations[S] // Column

In hindsight, this is clear from the DFA (see the blue self-loops), but it certainly is not obvious from the regular expression.  For the suspicious, a check that (L^( 2))= (Σ^( * )).

ConcatenateFA[m,m] // PropertyQFA[#,"Universal"]&

Cellular Automata

ECA 45

Consider the elementary CA number 45. Here is the evolution of a one-point seed and a random configuration.

ca=ECA[45]

OrbitCA[ca,SeedConfiguration[{1},80],50]  // PlotMatrix

OrbitCA[ca,SeedConfiguration[80,"RandomDigits"->2],50]  // PlotMatrix

ECA 45 is surjective on infinite configurations and hence must be surjective on infinitely many finite grids by a compactness argument (using cyclic boundary conditions).   The corresponding de Bruijn automaton is unambiguous.

ClassifyCA[ca]

sa=ToSemiautomatonCA[ca];
PropertyQFA[ sa, "Ambiguous" ]

To determine the grid sizes n for which ECA 45 acts like a bijection on  (Subscript[𝒞, n])=(({0,1})^n), we construct the automaton 
	𝒜 = (Subscript[Σ , p∈ Q]) (Subscript[ℬ, p,p])  
where ℬ = ⟨Q,{0,1},δ ⟩ is the de Bruijn automaton for the CA and (Subscript[ℬ, p,p]) indicates the automaton obtained by selecting p as initial and final state.

sa // PlotFA

m=UnionFA@@(SetInitialFinal[sa,{#1},{#1}]&)/@Range[StateCount[sa]];
mm=MinimizeFA[m]

The growth function of the language of 𝒜 suggests that ca will be surjective exactly for all odd n.

LanguageFA[mm,16,SizeOnly->True]
2^Range[0,16]
%-%%

It looks like  (Subscript[a, n])= (2^n) for odd n, and (Subscript[a, n])= (2^n)-(2^(n/2)) for even n.  For a proof, note that there is a reasonable description of the growth function in terms of a recurrence equation.

LanguageFA[mm,16,SizeOnly->True] // FindSequenceFunction

The claim follows easily by induction. 

With more effort, on can extract the same information from the generating function for the growth function of 𝒜.

gf = GrowthFunctionDFA[mm,x]
Series[ gf, {x,0,10}]

For grid size n=6  we should expect only  (2^( 6))-(2^( 3 ))= 56  first generation configurations. We determine the transients and periods of all configurations on a small grid and print a frequency table.

nn = 6;
AssignMapCA[ glob,ca]
trper=AnalyzeOrbit[glob,#]&/@Tuples[{0,1},nn];
trper // Frequencies // TableForm[#,TableDepth->2]&

So there is one limit cycle of length 18, one of length 3, one of length 2 and three fixed points.
Phasespace:

Graph[ Table[DirectedEdge[X,glob[X]], {X,Tuples[{0,1},nn]} ] ]

Minimal Fischer Automata

Consider a one-dimensional cellular automaton ρ as a transducer on bi-infinite words, so ρ : (Σ^( ∞)) ⟶ (Σ^( ∞)).  The finite factors of ρ(X) where X∈ (Σ^( ∞))  form a regular language accepted by the de Bruijn automaton associated with ρ.  For example, for ECA 73 we get:

sa=ToSemiautomatonCA[ECA[73]]

The minimal DFA here has maximal size 16.

m=MinimizeFA[sa]

All the ECAs whose minimal DFA have maximum size are based on one-permutation automata. By symmetry, we consider only the first 128 machines.

blowup=Select[Range[0,127],StateCount[MinimizeFA[ToSemiautomatonCA[ECA[#]]]]==16&]

Partition[PlotFA[ToSemiautomatonCA[ECA[#]],Type->"MultiColor"]&/@blowup,4] // GraphicsGrid

Back to ECA 73. The growth function is rather complicated:

GrowthFunctionDFA[m,x]
Series[%,{x,0,14}]

mc = ComplementFA[m];
mc //PlotFA

The complement forms an ideal, but this ideal fails to have a finite base.

D2= Alpha[2,"Digit"];

ConcatenateFA[ UniversalFA[D2],mc,UniversalFA[D2]]
EquivalentQFA[ mc,%]

idbase = MinimizeFA@LanguageFactorFA[ mc, Type->"MinimalFactor" ]

LanguageFA[ idbase, 16, SizeOnly->True ]

PropertyQFA[ idbase, "Finite" ]

A deterministic reduced semiautomaton for the cover language can be determined by finding a terminal strongly connected component in the minimal DFA for the language (which component is uniquely determined).

Clear[FischerAutomatonFA]
Options[FischerAutomatonFA]={Full->False};
FischerAutomatonFA[MM_?FSMQ,opts:OptionsPattern[]] :=
Module[{M,Mf,Q},
M= TrimFA[MinimizeFA[MM]];
Q = SafeLastFirst@CondensationGraph[TransitionSystemGraph[M],Full->True];
Mf = Quiet[SubautomatonFA[M,Q,StateType->{"Shallow","Indexed","Indexed"}]];
Mf = SetInitialFinal[Mf,All,All];
If[ OptionValue[Full], 
	{Mf,M}, Mf ]
];

sa = ToSemiautomatonCA[ECA[73]]
mf = FischerAutomatonFA[sa]
EquivalentQFA[ mf, sa ]

sa = ToSemiautomatonCA[ECA[39]]
mf = FischerAutomatonFA[sa]
EquivalentQFA[ mf, sa ]

Here is a more interesting example, a binary width-4 automaton.   There are several non-trivial components.

sa = ToSemiautomatonCA[CA[4,2,15042]]
{mf,mm} = FischerAutomatonFA[sa,Full->True]
EquivalentQFA[ mf, sa ]

PlotFA[ mf,Type->"MultiColor" ]

PlotFA[ mm,Type->"MultiColor" ]

A Counterexample

The minimal Fischer automaton for any factorial, extensible and transitive language L is uniquely determined. Here is an example due to A. Jonoska that shows that transitivity is essential here: two equivalent, deterministic minimal semiautomata that fail to be isomorphic, over a 3-letter alphabet.

D3 = Alpha[3,"Digit"];

s1 = GraphToFA[Graph[Range[4],{(DirectedEdge[1, 2, 1]),(DirectedEdge[1, 3, 2]),(DirectedEdge[2, 1, 1]),(DirectedEdge[2, 4, 2]),(DirectedEdge[3, 3, 3]),(DirectedEdge[3, 4, 2]),(DirectedEdge[4, 3, 1])}],D3,All,All]

s2 = GraphToFA[Graph[Range[4],{(DirectedEdge[1, 4, 2]),(DirectedEdge[1, 3, 1]),(DirectedEdge[1, 3, 3]),(DirectedEdge[2, 2, 1]),(DirectedEdge[2, 1, 2]),(DirectedEdge[3, 3, 3]),(DirectedEdge[3, 4, 2]),(DirectedEdge[4, 3, 1])}],D3,All,All]

The automata are transition deterministic but multi-entry.

PropertyQFA[s1,"Deterministic"]
PropertyQFA[s2,"Deterministic"]
EquivalentQFA[s1,s2]

colplot /@ {s1,s2} // GraphicsRow

The underlying digraphs fail to be isomorphic.  The machines are reduced, but note that unlike with Fischer automata this does not suffice to establish minimality here (it is not hard to see, though, that no deterministic machine of size 3 or less can produce L).

ToClasses[Range[4],MinimizeFA[SetInitial[s1,{#1}]]&,Type->"Function"]
ToClasses[Range[4],MinimizeFA[SetInitial[s2,{#1}]]&,Type->"Function"]

Note that the second semiautomaton is a subautomaton of the minimal DFA for L.

MinimizeFA[s1] // colplot

s1fac = LanguageFactorFA[s1] 
EquivalentQFA[s1,s1fac]

Incidentally, the ideal of forbidden blocks has a finite base.

sc = ComplementFA[s1]
EquivalentQFA[ sc, ConcatenateFA[  UniversalFA[D3], sc, UniversalFA[D3] ] ]

idbase = LanguageFactorFA[ sc, Type->"MinimalFactor" ] // MinimizeFA;
PropertyQFA[  idbase, "Finite" ]

idbase // colplot

Multiplicity Semigroup Surjective

A binary cellular automaton of width 4. The global map is surjective, but fails to be injective or even open.
Smaller semigroups:  7710, 7650.

ca=CA[4,2,7770];
ClassifyCA[ca]

OrbitCA[ca,SeedConfiguration[{1},100],80] // PlotMatrix

OrbitCA[ca,SeedConfiguration[100,"RandomDigits"->2],80] // PlotMatrix

Since ca is surjective, all words must have the same multiplicity in the de Bruijn semiautomaton associated with C.

sa=ToSemiautomatonCA[ca];
PlotFA[ sa, Type->"MultiColor"]

LanguageFA[sa,{5},Multiplicity->True]

We construct the multiplicity semigroup of the automaton, the image of the canonical homomorphism  (Σ^( * ))-> (2^( Q × Q)).  The semigroup has size 754.  Note that this semigroup would be infinite if our CA were non-surjective.

bmat = BooleanTransitionMatrix[sa];

ClearAll[f1,f2]
f1[M_?MatrixQ] :=M.bmat[[1]];
f2[M_?MatrixQ] := M.bmat[[2]];
{mats,tr,wit} = Closure[  IdentityMatrix[8], {#.bmat[[1]]&, #.bmat[[2]]&} , Cayley->True,Witnesses->True, Bound->500000 ];
mats // Length

The matrices are duly binary. The identity matrix is the only matrix of rank 8, so the underlying semigroup has only 754 elements.

mats // Flatten // Union
MatrixRank /@ mats // Frequencies

Matrix ranks of each SCC in G are necessarily constant and are weakly decreasing along each path in the condensation graph.

H= IndexGraph@Graph[tr];
Hc = CondensationGraph[H,StateType->"Shallow"];
Annotate[Hc,{VertexLabels->Table[x->Placed[MatrixRank[mats[[x[[1]]]]],Center], {x,VertexList[Hc]}], 
VertexSize->Large,VertexStyle->White,
GraphLayout->"LayeredDigraphEmbedding" } ]

The 6 exits all have rank 1.

bot = Select[VertexList[Hc], VertexOutDegree[Hc,#]==0&]
MatrixRank /@ mats[[Flatten@bot]] // Union

The induce subgraphs that are isomorphic to a (2,2) de Bruijn graph.

Subgraph[H,Flatten@bot]

The matrices are duly binary. The identity matrix is the only matrix of rank 8, so the underlying semigroup has only 754 elements.

mats // Flatten // Union
MatrixRank /@ mats // Frequencies

We extract the 24 matrices of minimal rank, which turns out to be 1 in this case.

minmat = Select[ mats, MatrixRank[#]==1& ];

Partition[ PlotMatrix[#,Mesh->True,MeshStyle->{{,Thickness[Tiny]},{,Thickness[Tiny]}}]& /@ Sort@minmat , 6 ] // GraphicsGrid

There are 6 classes of matrices according to non-zero rows and 4 according to columns; all 24 combinations appear.

Union[(Union[First/@Position[#1,1]]&)/@minmat]
Union[(Union[First/@Position[Thread[#1],1]]&)/@minmat]

The witnesses associated with minimal rank matrices.

W=ToWord[wit[[PositionList[ mats, minmat ]]],Alpha[2,"Digit"] ]

A random witness and the corresponding computation graph in the de Bruijn semiautomaton.   Notice the bottleneck.

ComputationGraphFA[ sa,RandomChoice[W],VertexLabels->None,DoTrace->"Trim"]

A similar picture for all the witnesses associated with min-rank matrices.

Partition[ Table[ ComputationGraphFA[sa,x,VertexLabels->None,DoTrace->"Trim", PlotLabel->x],
{x,W} ],4] // GraphicsGrid[#,Frame->All]&

Pick one of these witnesses at random and convert into an index list.

w=ToIndex[ RandomChoice[W], Alpha[2,"Digit"] ]

Computing   δ(Q,w)  and    (δ^( r))(Q,(w^( r)))    shows that associated row/column pattern.

AssignTransitionFunction[del,sa]
AssignTransitionFunction[delr,ReverseFA[sa]]
del[Range[8],w]
delr[Range[8],Reverse[w]]

To check that the global map is not open, we use a product machine construction (this is the method used in ClassifyCA).  We can trace a path from the diagonal in the product (which forms a strongly connected component since the CA is surjective) to some other component.

s2=ProductFA[sa,sa,StateType->"Shallow" ];
PlotFA[ s2, Type->"MultiColor" ]

There are 2 non-trivial SCCs, the second one being the diagonal.

{H, scc, ntscc,lvs } = CondensationGraph[ TransitionSystemGraph[s2], Full->True ]

PositionList[ scc, ntscc ]
Length /@ scc[[%]]

There is a path of length 2 from the diagonal to the other non-trivial SCC.

GraphDistance[H,scc[[8]],scc[[3]]]
HighlightGraph[ H, ntscc,VertexSize->Large ]

The subautomaton induced by the second SCC accepts all words up to length 6. Hence all these words support vertex-disjoint computations.

s3 = SubautomatonFA[s2,scc[[3]],StateType->{"Shallow","Shallow"} ];

PlotFA[ s3, Type->"MultiColor" ]

LanguageFA[ ComplementFA@s3, 12, SizeOnly->True ]

The 2 missing words of length 7 produce bottlenecks.

Complement[ Words[{7},Alpha[2,"Digit"]],LanguageFA[s3,{7}] ] 
ComputationGraphFA[sa,#,VertexLabels->None, DoTrace->"Trim"]& /@ % // GraphicsRow

Multiplicity Semigroup Open

The next cellular automaton has a global map that is open (and hence surjective), but fails to be injective.

ca=CA[4,2,15555];
ClassifyCA[ca]

OrbitCA[ca,SeedConfiguration[{1},100], 80 ] // PlotMatrix

OrbitCA[ca,SeedConfiguration[100,"RandomDigits"->2], 80 ] // PlotMatrix

The de Bruijn automaton associated with C and checking multiplicity.

sa=ToSemiautomatonCA[ca];
PlotFA[ sa,Type->"MultiColor" ]

LanguageFA[sa,{5},Multiplicity->True]

Again we construct the multiplicity semigroup of the automaton, the image of the canonical homomorphism  (Σ^( * ))-> (ℕ^( Q × Q)).  The semigroup has size 24.

bmat = BooleanTransitionMatrix[sa];
PlotMatrix /@ bmat // GraphicsRow

ClearAll[f1,f2]
f1[M_?MatrixQ] := M.bmat[[1]];
f2[M_?MatrixQ] := M.bmat[[2]];
{mats,tr,wit} = Closure[  IdentityMatrix[8], {f1,f2} , Cayley->True,Witnesses->True ];
mats // Length

Removing the identity matrix leaves  24 matrices of rank 4, the actual semigroup.

mats = DeleteCases[ mats, IdentityMatrix[8] ];
MatrixRank /@ mats

Partition[ PlotMatrix[#,Mesh->True,MeshStyle->{{,Thickness[Tiny]},{,Thickness[Tiny]}}]& /@ Sort@mats , 6 ] // GraphicsGrid

There are 2 types of matrices according to non-zero rows; all columns have exactly one non-zero entry.

Union[(Union[First/@Position[#1,1]]&)/@mats]
Union[(Union[First/@Position[Thread[#1],1]]&)/@mats]

The product machine used in the classification algorithm.

s2=ProductFA[sa,sa,StateType->{"Shallow","Shallow"} ];
PlotFA[ s2, Type->"MultiColor" ]

Again there are 2 non-trivial SCCs, but there are no paths between them.

{H, scc, ntscc,lvs } = CondensationGraph[ TransitionSystemGraph[s2], Full->True, StateType->"Indexed" ];

PositionList[ scc, ntscc ]
Length /@ scc[[%]]
GraphDistance[ H,9,34]

HighlightGraph[ H, {{9},{34}},VertexSize->Large ]

Multiplicity Semigroup Injective

Lastly, a reversible binary cellular automaton of width 4.

ca=CA[4,2,21845];
ClassifyCA[ca]

OrbitCA[ca,SeedConfiguration[100,"RandomDigits"->2],80] // PlotMatrix

Since ca is surjective, all words must have the same multiplicity in the de Bruijn semiautomaton associated with C.

sa=ToSemiautomatonCA[ca];
PlotFA[ sa, Type->"MultiColor" ]

LanguageFA[sa,{5},Multiplicity->True]

We construct the multiplicity semigroup of the automaton, the image of the canonical homomorphism  (Σ^( * ))-> (2^( Q × Q)).  The semigroup has size 754, so this will take some 15 seconds.  Note that this semigroup will be infinite if you start with a non-surjective CA.

bmat = BooleanTransitionMatrix[sa];
PlotMatrix /@ bmat // GraphicsRow

ClearAll[f1,f2]
f1[M_?MatrixQ] := M.bmat[[1]];
f2[M_?MatrixQ] := M.bmat[[2]];
{mats,tr,wit} = Closure[  IdentityMatrix[8], {f1,f2} , Cayley->True,Witnesses->True ];
mats // Length

There are 8 matrices of minimal rank 1, which turn out to be all-ones columns.

MatrixRank /@ mats // Frequencies

minmat = Select[ mats, MatrixRank[#]==1& ];
Partition[ PlotMatrix[#,Mesh->True,MeshStyle->{{,Thickness[Tiny]},{,Thickness[Tiny]}}]& /@ minmat ,4 ] // GraphicsGrid

The witnesses for the minimal-rank matrices are all words of length 3: each words synchronizes the semiautomaton to a different state.

W=ToWord[wit[[PositionList[ mats, minmat ]]],Alpha[2,"Digit"] ]

Partition[ Table[ ComputationGraphFA[sa,x,VertexLabels->None,DoTrace->"Trim", PlotLabel->x],
{x,W} ],4 ] // GraphicsGrid[#,Frame->All]&

The bottlenecks all occur on the right.

In the product automaton all transitions lead towards the only non-trivial SCC in the middle, the diagonal.

s2=ProductFA[sa,sa];
PlotFA[ s2, Type->"MultiColor" ]

CondensationGraph[ TransitionSystemGraph[s2]]