Frontier Automata

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”]]
Current paclet version:  1.0.2.

Load the paclet, turn on abbreviations, formatting and small image sizes.

Needs["KlausSutner`Automata`"]
MakeAbbrevs[]
SetImageSize[Medium]
FormatFA[True]

Code

FrontierTree

Compute the interior of a frontier:  prefix closure.

Clear[FrontierInterior]
FrontierInterior[ rw_List, A_Alpha ] := 
Module[{U,prefs},
	prefs[s_String]:= Table[StringTake[s,i],{i,0,StringLength[s]-1}];
	U = First /@ rw;
	WordSort[Union[Flatten[prefs /@ U]]]
];

Visualize a frontier:  leaves are targets of back transitions. 
Get coordinates from KaryTree, TreePlot.

ClearAll[FrontierTree]
Options[FrontierTree]=Options[TreePlot]; 
FrontierTree[ FrontierRW[rw_List,A_Alpha,___], opts:OptionsPattern[]] := 
Module[{indx,branch,U,Ui,ed,vlab,vstl,oplab,opstl},
	indx = ToIndex[A];
	branch[s_String]:= Table[
		DirectedEdge[StringTake[s,i-1],StringTake[s,i],indx[StringTake[s,{i}]]],{i,StringLength[s]}];
	U = First /@ rw;
	Ui = FrontierInterior[rw,A];
	ed = WordSort[Union[Flatten[branch /@ U]]];
	vlab = Join[Table[x->Placed[x,Center], {x,Ui}],Table[ x->Placed[x/.rw,Center],{x,U}]] /. ""->ϵ;
	vstl = Join[Table[x->GrayLevel[.95],{x,Ui}],Table[ x->Blend[{Yellow,White},.8], {x,U}]] /. ""->ϵ;
	TreePlot[ ed/.""->ϵ, ϵ->Top, opts, 
		VertexLabels->vlab, VertexStyle->vstl ]
];

Options[TreePlot,{VertexLabels,VertexStyle}]

Finite Languages

To motivate the construction in the next section, first consider finite languages. There is an obvious way to convert a finite language into a partial DFA accepting that language: insert the words into a trie.  The root will be the initial state, and all the nodes corresponding to words in the language are final.  If a DFA is needed, one can simply add a sink and route all missing transitions to the sink. By default, the command FiniteLanguageFA uses this construction.

L = {"aa","aaaa","abab", "b","baa","bbb","bbab", "abbbb"};
Mtrie = FiniteLanguageFA[L,Alpha[2]];
PlotFA[Mtrie,Type->"MultiColor",EdgeStyle->Thick,VertexSize->Medium]

A few sanity checks indicate that the automaton works as intended.

LanguageFA[Mtrie,8]
LanguageFA[Mtrie,16,SizeOnly->True]

The language is finite, so the generating function is just a polynomial.

GrowthFunctionDFA[CompletePDFA[Mtrie],z]
% // Expand

From the picture, it is clear that one can share some common subtrees, leading to a smaller automaton.

Mmin = MinimizeFA[Mtrie,StateType->"Indexed"];
PlotFA[Mmin,Type->"MultiColor",EdgeStyle->Thick,VertexSize->Medium]

In this case, Mmin is a PDFA and thus trim. The corresponding DFA contains a sink that is suppressed by default in PlotFA, to see the full machine use the Trim option.

Mdfa = CompletePDFA@Mmin;
Table[ PlotFA[ Mdfa,Trim->bool,Type->"MultiColor",EdgeStyle->Thick,VertexSize->Medium],{bool,{False,True}} ] // GraphicsRow

It is often convenient to label a state with the transfer sequence, the length-lex shortest words that lead from the initial state to the state. For efficiency reasons, the command TransferSequenceFA only returns a word that is guaranteed to have minimal length, but may not produce the lexicographically least of these words. In this case, everything works fine.

PlotFA[Mmin,Type->"MultiColor",EdgeStyle->Thick,VertexSize->Large, 
VertexLabels->Table[x->Placed[First@TransferSequenceFA[Mmin,{1},{x}],Center] ,{x,StateList[Mmin]}]]

Semigroup

To explain the structure of the minimal PDFA we turn to the associated syntactic semigroup.

S = SemigroupGenerate[Mdfa]

Here are the critical identities in the semigroup. Many lead to aab, which is the transfer sequence for the sink in the DFA.

eqs = SemigroupEquations[S];
Partition[eqs,4] // TF

In terms of the semigroup,  aab  is a left null. To check, we set up a witness function that translates semigroup elements into corresponding words.

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

So we can write the equations more suggestively as follows.

Partition[ eqs /.  "aab"->"0", 4 ] // TF

The critical equations in the semigroup are the remaining ones.

DeleteCases[ eqs, _->"aab" ] // TableForm

ComputationGraphFA[Mdfa,#,AspectRatio->0.3,PlotLabel->#]& /@ {"aaaa","baa"} // GraphicsRow

Regular Languages

Trie-Like Automata

It is natural to ask whether a trie-like layout can also be used for arbitrary DFAs that accept infinite languages.  The root should again be the initial state, and we would like to unfold the automaton into a trie structure. To deal with words of arbitrary length, we will need some sort of back transitions.  We would like these back transitions to point to a “previous” location in the trie: think of constructing the trie in stages, and all back transitions must have a target that has already been constructed.  

For example, here is minimal DFA for the even/even language.

EE = MinimizeFA[IntersectionFA[ SemilinearDFA["a",0,2,Alpha[2],Type->"Factor"], 
SemilinearDFA["b",0,2,Alpha[2],Type->"Factor"]],StateType->"Indexed"];
cols = Directive[Opacity[0.3],#]& /@ {Red,Green, Lighter@Blue, Yellow};
PlotFA[ EE, Type->"MultiColor", EdgeStyle->Thick, VertexSize->Medium, VertexStyle->Thread[Range[4]-> cols]]

If we think of the set of all words as an infinite tree, we can label the nodes of that tree by the corresponding state in M:  node x is labeled by state δ((Subscript[q, 0]),x). We use colors rather than names.

T = KaryTree[31];
W = Words[4,Alpha[2]];
vlab = Thread[ Range[31]-> W] // EpsToEpsilon;
AssignTransitionFunction[del,EE]
vsty = Thread[ Range[31]->(cols[[del[1,ToIndex[#,Alpha[2]]]]]& /@ W) ];
TT = TreePlot[ T, VertexLabels-> vlab,LayerSizeFunction->(1 + #1/5 &),
VertexStyle->vsty,VertexSize->Large]

To turn this labeled tree into a DFA for the even/even language we could re-target all the transitions to the bottom level to any node higher up of the same color. The root is the initial state and all orange nodes are final. Of course, there are other options. For example, we could re-target the transitions leading to level 3 instead.  In fact, we could switch the transitions with  sources  nodes a, b and ab (other than   (DirectedEdge[a, ab , b])).  In this case we wind up with a trie with nodes ϵ, a, b and ab with obvious forward transitions, and back transitions 
	(DirectedEdge[a, ϵ, a]),(DirectedEdge[b, ab, a]),(DirectedEdge[b, ϵ, b]),(DirectedEdge[ab, b, a]),(DirectedEdge[ab, a, b])
Here is command that converts a DFA into the corresponding data:

fr = FrontierFromDFA[EE]

In the output of FrontierFromDFA, the first component is a collection of rewrite rules of the form u s -> v where u, v ∈ (SuperStar[Σ]) and s ∈ Σ,  corresponding to the back transition (DirectedEdge[u, v, s]).  The last component associates states with corresponding transfer sequences (not necessarily  minimal).

We can convert the frontier to a corresponding DFA, as long as we provide information about the final states. In this case, get back the original machine.

FrontierToDFA[fr,FinalStateList[EE]]

The rewrite rules of the frontier can be used to explain the computations of the machine.

RewriteString["aabaababbbbbaaaab",fr[[1]],Full->True] // TableForm

RewriteString[#,fr[[1]]]& /@ Words[{5},Alpha[2]] 
% // Frequencies

Frontiers, Defined

More generally, define a frontier to be a non-empty language L that is prefix-free and right-closed, meaning that for every word x, either x is a prefix of a word in L, or there is a word in L that is a prefix of x.  In other words, every infinite branch in the tree of all words intersects L in exactly one place. In particular all languages (Σ^k) are frontiers, as is the set {a,b,a b} from above. As indicated, we can build a DFA that has as state set all the prefixes of a frontier, subject to the condition that all states of the original automaton appear as labels.

An example of a handcrafted frontier for the even/even machine from above. It includes the additional point aa.

fr1 = FrontierRW[
{"aaa"->"a","aab"->"b","aba"->"b","abb"->"a","ba"->"ab","bb"->""}, 
Alpha[2],
{{"",1},{"a",2},{"b",3},{"aa",1},{"ab",4}} ];

FrontierTree[fr1,VertexSize->Large]

M1 = FrontierToDFA[ fr1, FinalStateList[EE]];

PlotFA[M1,Type->"MultiColor",VertexSize->Medium]

The machines are equivalent.

EquivalentQFA[EE,M1]

By default, the conversion from DFA to frontier constructs the smallest frontier based on length-lex order.  One way to force larger frontiers is by specifying a level in the word tree.

fr2 = FrontierFromDFA[EE,Method->"Level", Type->{3,First}]

FrontierTree[fr2,VertexSize->Large]

M2 = FrontierToDFA[fr2,FinalStateList[EE]];
PlotFA[M2,VertexLabels->Automatic,Type->"MultiColor",EdgeStyle->Thick,VertexSize->Medium]

Another option is to force all back transitions to lead not only to prior nodes, but to a node higher up on the same branch in the word tree.

fr3 = FrontierFromDFA[EE,Method->"Periodic"]

FrontierTree[fr3,VertexSize->Large]

M3 = FrontierToDFA[fr3,FinalStateList[EE]];
PlotFA[M3,VertexLabels->Automatic,Type->"MultiColor",EdgeStyle->Thick]

A sanity check.

EquivalentQFA[{EE,M1,M2,M3}]

More Examples

(a^( * ))(SuperStar[b])a

M = MinimizeFA[ RegexToFA[ RET[RES["a"],RES["b"],"a"], Alpha[2] ],StateType->"Indexed"];
PlotFA[M,VertexLabels->Automatic,Type->"MultiColor",EdgeStyle->Thick]

fr = FrontierFromDFA[M]

FrontierTree[fr,VertexSize->Medium]

fr1= FrontierFromDFA[M,Method->"Periodic"]

FrontierTree[fr1,VertexSize->0.6]

kth Symbol

3rd symbol from the end

M = MinimizeFA[PositionFA[-3->"a",Alpha[2]],StateType->"Indexed"]

fr = FrontierFromDFA[M]

The frontier tree shows a modified version of the “remember the last 3 symbols” approach.

FrontierTree[fr,VertexSize->.6]

Again, the conversion back to a DFA produces an isomorphic automaton.

FrontierToDFA[fr,FinalStateList[M]]
IsomorphicQDFA[%,M]

The rewrite rules here fail to express computations properly.

RewriteString["aabaababbbbbaaaab",fr[[1]],Full->True] /. ""->ϵ// TableForm

A larger frontier built on periodicity.

fr1= FrontierFromDFA[M,Method->"Periodic"];
Short/@fr1

FrontierTree[fr1,VertexLabels->None,VertexSize->Large,EdgeStyle->Arrowheads[Small],LayerSizeFunction->(If[#==1,1.6,#^(1/6)]&)]

kth Symbol with cone

M = TransformationDFA[M]

fr = FrontierFromDFA[M]

FrontierTree[fr,VertexSize->.8,LayerSizeFunction->(If[#==1,1.6,#^(1/2)]&)]

fr1= FrontierFromDFA[M,Method->"Periodic"];
Short /@ fr1

FrontierTree[fr1, VertexLabels->None,EdgeStyle->Arrowheads[Small],LayerSizeFunction->(If[#==1,1.6,#^(1/2)]&)]