FSM Algorithms

CDM
K. Sutner

Even/Even

aes=RES["aa"]
aos=RET["a",RES["aa"]]
aesb = RET["b", aes, "b"]
aob = REP["a",RET["b", aos, "b"]]
ee=RES[REP[aesb, RET[aob,RES[aesb],aob]]]

Conversion

RegexToFA["ab",Alpha[2]] // colplot

RegexToFA[REP["ab","ba"],Alpha[2]] // colplot

RegexToFA[REP["ab",RES["ba"]],Alpha[2]] // colplot

RegexToFA[RES[REP["ab","ba"]],Alpha[2]] // colplot

RegexToFA[REP[RES[REP["ab","ba"]],"ccc"],Alpha[3]] // colplot

Language EE

m1=RegexToFA[ee,Alpha[2] ];
PlotFA[m1,Type->"MultiColor",VertexSize->Large]

m2=EpsilonEliminationFA[m1]
PlotFA[m2,Type->"MultiColor",VertexSize->Large]

m3 = DeterminizeFA[m2];
m3 // colplot

m4=MinimizeFA[m3];
% // colplot

GrowthFunctionDFA[m3,z]

Series[%,{z,0,8}]

Language EE  2

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

m1=RegexToFA[e00,Alpha[2] ];
PlotFA[m1,Type->"MultiColor",VertexSize->Large]

m2=EpsilonEliminationFA[m1];
PlotFA[m2,Type->"MultiColor",VertexSize->Large]

m3 = DeterminizeFA[m2];
PlotFA[m3,Type->"MultiColor",VertexSize->Large]

m4=MinimizeFA[m3];
m4 // colplot

Language OO

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

m1=RegexToFA[e11,Alpha[2] ];
PlotFA[m1,Type->"MultiColor",VertexSize->Large]

m1 // MinimizeFA // colplot

Language OO   2

e11 = RET[ RES[e0],e1,e00 ]

m1=RegexToFA[e11,Alpha[2] ];
PlotFA[m1,Type->"MultiColor",VertexSize->Large]

m1 // MinimizeFA // colplot

Conway’s Regex

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[{abs=RET["a",RES["b"]],aebs=RET[REP[Eps,"a"],RES["b"]]},
REP[  RES["b"],
RET[RES["b"],RES[REPower[abs,n]],REPower[aebs,n]]]];

ConwayRn[1]

ConwayRn[3]

fa = RegexToFA[ ConwayRn[3],Alpha[2]];
fa // StateCount
fa // colplot

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

MinimizeFA[dfa]

Blowup  Moore

Exponential blow-up during determinization and minimization.

G = MooreGraph[8]

Corresponding DFA, is clearly minimal.

dfa = GraphToFA[ G, Alpha[2], {1},{1}];
PlotFA[dfa,Type->"MultiColor",VertexLabels->Automatic,VertexSize->Medium]

Switch label at loop 1->1.

nfa = switchLabel[dfa,1\[DirectedEdge]1];
nfa // colplot

Determinization produces a machine on 256 states.

DeterminizeFA[nfa]

Minimization changes nothing.

MinimizeFA[nfa]

More  Moore

Switch the 1->2 transition.

PlotFA[ GraphToFA[ G, Alpha[2], {1},{1}],Type->"MultiColor",VertexLabels->Automatic,VertexSize->Medium]

switchLabel[dfa,1\[DirectedEdge]2]// MinimizeFA

Switch  the other 2 transitions.

switchLabel[dfa,8\[DirectedEdge]1]// MinimizeFA
switchLabel[dfa,8\[DirectedEdge]2]// MinimizeFA

That’s it.

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

Circulants (1,2)

Semiautomata with I = F = Q.

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

DeterminizeFA[switchLabel[ M, 0\[DirectedEdge]1 ] ]
DeterminizeFA[switchLabel[ M, 0\[DirectedEdge]2 ] ]

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

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

Circulants (1,3)

M= With[ {n=10},CirculantFA[ n, {1,3} ]];
M // colplot

DeterminizeFA[switchLabel[ M, 0\[DirectedEdge]1 ] ]
% // MinimizeFA
DeterminizeFA[switchLabel[ M, 0\[DirectedEdge]3 ] ]
% // MinimizeFA

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

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

M= switchLabel[ CirculantFA[ 9, {1,3}], 0\[DirectedEdge]1 ];
Q = StateList[DeterminizeFA[M]]-1;
Q // Length

cmp = Complement[ PowerSet[Range[0,8]], Q];
cmp // TableForm

Complement[#,{1,4,7}]& /@ cmp  // TableForm

Brzozowski Universal

m=BrzozowskiUniveralDFA[6];
m // colplot

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

GrowthFunctionDFA[m,z]

mr = ReverseFA[m];
mr // colplot

mm=DeterminizeFA[mr];
mm // StateCount
PlotFA[mm, Type->"MultiColor"]

mm // MinimizeFA // StateCount

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

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];

Edward Moore’s example.

MooreGraph[n_Integer]:= 
Block[{tr},
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}]] ] ];
Graph[ Range[n], tr,VertexLabels->Placed["Name",Center], VertexStyle->LightBlue,VertexSize->Large ]];

Brzozowski universal (reverse DFA).

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"]]