L.b.⊕a.∘b.⊕a.∘a.∘b.∘a.∘a.∘b.∘b.∘b.∘a.⊕a.∘b.∘a.⊕b.∘b.∘a. |
Recently as an offshoot of Stephen Wolfram's blog on the "Forgotten Code 10", we’ve gotten a chance to study Deterministic Finite Automata (DFA). Our first step was to enumerate non-possible blocks, and in this sequel we will develop tools to help with characterization of all possible inclusions and omissions and with comparison between DFAs.
As discussed in one of Wolfram’s academic papers, each DFA determines a regular language, whose valid words can be described by a regular expression (regex) involving only three operators: concatenate, alternative, and the Kleene star. The invalid words of one DFA are the valid words of another DFA which is obtained from the first by a complement construction. Thus regex can also be useful in the enumeration of non-possible blocks, but that is not the immediate purpose here.
More or less concurrently to our investigation, Thomas Baruchel independently had the idea of counting unique regular languages for an OEIS entry. The purpose of this memo is to show one easy (but slow) method for computing terms of Thomas’s proposed new sequence. The method, from a stack-exchange post, makes use of the aforementioned complement construction, which is worth learning in general.
Introduction
Introduction
In math literature, the standard description of Deterministic Finite Automata (DFA) involves a five-tuple of combinatorial variables: States, alphabet letters, transitions, starting states, and accepting states. The states and alphabet can be inferred from an adjacency matrix describing transitions, so here we will prefer three-tuples. For example, there are exactly two one state DFA’s:
In[]:=
binaryDFAs[1]
Out[]=
D.F.A.a.⊕b.,{1},{},D.F.A.a.⊕b.,{1},{1}
And possibly 192 two-state DFA’s:
In[]:=
Short[binaryDFAs[2]]
Out[]//Short=
D.F.A.a.,b.,a.,b.,{1},{},190,D.F.A.a.⊕b.,0,a.⊕b.,0,{1,2},{1,2}
For even larger numbers of states, a naive count is given as follows:
In[]:=
Map[Times[2^#,(2^(#)-1),Plus[Divide[#!,(#-2)!],Divide[#!,(#-1)!]]^#]&,Range[1,7]]
Out[]=
{2,192,40824,15728640,9687500000,8776786378752,11025194272233344}
This counting sequence grows very quickly, faster than an exponential function. However, it is somewhat misleading when considering that two DFA’s can have different appearance, yet still accept words from identical regular languages.
In the one-state case, we can immediately see that the two possible DFA’s are indeed different:
In[]:=
GridTransposeMapListquickDepict[#],L.->DFAToOneRegex[#]&,NormalizedEdgeModel@@@binaryDFAs[1],Spacings->{2,1},Frame->All,FrameStyle->LightGray
Out[]=
L.Empty | L.a.⊕b. |
( In these pictures and subsequent, two extra states {0,-1} have been added to make it more obvious where inputs come from, and where accepted words go to. The DFA states are always in the range [1,n]. )
Here the first DFA does not have an accepting state, so it’s language is always Empty of any words whatsoever. Conversely, in the second, the only state is an accepting state, so every word, including the empty word is ultimately permitted. The regular expression of the second DFA uses as the Kleene star and ⊕ for alternatives. In subsequent examples ∘ will denote concatenation.
These two DFA’s are the first example of complementarity. By switching the accepting and non-accepting states of one, we obtain the other. Consequently, the intersection of the two languages is Empty, and the union of the two languages is every possible world. This first case is overly trivial, and we only mention it to set the stage for subsequent calculations.
Now let’s choose at random a pair of two-state DFAs:
In[]:=
SeedRandom[1234];test2=RandomSample[binaryDFAs[2],2]
Out[]=
D.F.A.0,a.⊕b.,a.,b.,{1,2},{1},D.F.A.0,a.⊕b.,a.,b.,{1,2},{2}
And depict them with alternative descriptions of their associated regular languages:
In[]:=
GridTransposeMapListquickDepict[#],L.->Column[DFAToManyRegex[#]]&,NormalizedEdgeModel@@@test2,Spacings->{2,1},Frame->All,FrameStyle->LightGray
Out[]=
L.
| L.
|
In either left or right case, we obtain formally different but practically equivalent regex expressions. In both cases the two alternatives even have different star heights! This immediately raises some interesting and difficult questions about these sort of binary regex’s: Can we ever obtain a canonical minimal regex? If not, can we at least know when two regex’s are the same or different?
At least in this particular case, we can see that the left and right languages are not the same. In the left DFA, accepted non-empty words always end in an “a”; whereas, the right DFA can sometimes accept a word ending with a “b”.
In order to ascertain a difference programmatically between two DFAs, we immediately construct two product DFAs, each from one chosen DFA and the complement of the other. Compliment DFA’s are obtained by flipping the accepting and non-accepting states of the other DFA. If both product DFAs produce the empty language, then we know that no word accepted by the first will be rejected by the second and vice versa. This proves equivalence of the two DFA, or not:
In[]:=
SameLanguageQ[#[[1]],#[[2]]]&@test2
Out[]=
False
Using the SameLanguageQ function, we can immediately count the number of distinct languages produced by DFAs with only two states. First we note pairs which are certainly the same:
In[]:=
twoStateDFAs=binaryDFAs[2];
In[]:=
AbsoluteTiming[res2=Map[If[Apply[SameLanguageQ,twoStateDFAs[[#]]],#,Nothing]&,Subsets[Range[192],{2}]];]
Out[]=
{4.5349,Null}
Then we gather equivalent pairs into equivalency classes and count them:
In[]:=
Module[{res=GroupBy[res2,First->Last]},eqClasses=KeyValueMap[Prepend[#2,#1]&,KeyDrop[res,Catenate[Values[res]]]]]Length[%]
Out[]=
{{1,5,9,13,17,21,25,29,30,33,37,41,45,49,53,57,61,65,69,73,77,78,81,85,89,93,97,101,105,109,113,117,121,125,126,129,133,137,141,145,147,149,153,157,159,161,165,169,171,173,174,177,181,183,185,189},{2,67},{3,66},{4,8,12,16,20,24,28,31,32,36,40,44,48,52,56,60,64,68,72,76,79,80,84,88,92,96,100,104,108,112,116,120,124,127,128,132,136,140,144,146,148,152,156,158,160,164,168,170,172,175,176,180,182,184,188,192},{6,63},{7,62},{14,19},{15,18},{26,163},{27,162},{38,115},{39,114},{42,111},{43,110},{50,55},{51,54},{74,151},{75,150},{86,103},{87,102},{90,99},{91,98},{122,187},{123,186},{134,139},{135,138}}
Out[]=
26
We find exactly 26 regular languages defined by DFA with at most two states. To characterize these regular languages, we can use vertex elimination to produce a regex:
In[]:=
regex2=DFAToManyRegex[NormalizedEdgeModel[##]]&@@@twoStateDFAs;
In[]:=
regexClasses=SortBy[Association[First[#]->Apply[Union,regex2[[#]]]&/@eqClasses],Length];
When looking at these results, it’s obvious that we haven’t spent much effort reducing the regex to a minimal form:
In[]:=
Column[Values[First/@regexClasses]]
Out[]=
Empty |
a. |
a.∘b.∘a.⊕b. |
b. |
b.∘a.∘a.⊕b. |
ϵ. |
a.⊕b.∘a.⊕b. |
a.∘b.∘b.⊕a.∘a.∘b.∘a.∘a.⊕a. |
a.∘b.∘b.⊕a.∘a.∘b. |
b.∘a.∘a.⊕b.∘b.∘a. |
b.∘a.∘a.⊕b.∘b.∘a.∘b.∘b.⊕b. |
a.∘b.∘a.⊕b.∘a.∘b.∘b.∘a.⊕a. |
a.∘b.∘a.⊕b.∘a.∘b. |
a.∘b.∘a.⊕b.∘a.∘b.∘a.⊕b.∘a.⊕a. |
a.⊕b.∘a.⊕b.∘b. |
a.⊕b.∘a.⊕b.∘a.⊕b. |
ϵ.⊕a.⊕b.∘a.⊕b.∘a.⊕b.∘b. |
b.∘a.∘b.⊕a.∘b.∘a.∘a.∘b.⊕b. |
b.∘a.∘b.⊕a.∘b.∘a. |
b.∘a.∘a.⊕b.∘b.∘a.∘a.⊕b.∘b.⊕b. |
b.⊕a.∘a.⊕b.∘a. |
a.⊕b.∘b.⊕a.∘a.⊕b. |
ϵ.⊕a.⊕b.∘b.⊕a.∘a.⊕b.∘a. |
ϵ.⊕a.⊕b.∘a.⊕b.∘a.⊕b.∘a.⊕b. |
a.⊕b.∘a.⊕b.∘a.⊕b. |
ϵ.⊕a.⊕b.∘a.⊕b. |
In the last element, non-reduction is particularly problematic, leaving us with 40 formally different regex for the same language admitting all words including the empty word:
Indeed by finding duplicate vertices, we can see that our forty regex are just excessive pseudonyms for the simple form we found in the one-vertex case:
We have yet to implement a reduction algorithm, but it should be possible in the near future using only
the compliment construction of SameLanguageQ. If we had the capability like SameRegexQ for automatically comparing regex’s for equivalence, another elimination algorithm could be written mainly in terms of matrix row and column permutations, and such an algorithm might be faster in some cases.
the compliment construction of SameLanguageQ. If we had the capability like SameRegexQ for automatically comparing regex’s for equivalence, another elimination algorithm could be written mainly in terms of matrix row and column permutations, and such an algorithm might be faster in some cases.
Next terms
Next terms
We now would like follow Thomas by calculating more terms of the integer sequence counting unique regular languages as a function of number of states. To limit combinatorial explosion, we introduce two more assumptions: Only one input state, and the input state must be accepting. These conditions divide out the half of all regular languages not containing the empty word. The input domain can be counted as:
Our previous results are quickly recovered:
And the next term can be computed in less than a minute:
This is not a great time, but we are not using compiled code or optimal-time algorithms. Indeed, the next term may be out of reach. Let’s try to estimate the time it would take based on roughly quadratic complexity, here reduced to roughly linear time per result generation:
The average time of results generation is estimate at 5 seconds:
An upper bound on the estimate run time would be about 3,1/2 days:
Thomas says he can compute the fourth term in only 49 seconds. Before going any farther with this problem, we should rethink our methods. The Hopcroft Karp algorithm is provides another means to implement SameLanguageQ, but with log-linear complexity.
Well, this has been a fun experiment with loose ends that could be picked up by an aspiring developer, possibly through subsequent instances of our yearly summer school. Specifically, we need an improved and generalized implementation of SameLanguageQ, and a reduction algorithm that obtains minimum DFAs by duplicate vertex elimination (possibly using the same test). It would also be very interesting to develop a suite of algorithms for comparing and reducing simple regex over finite alphabets. This problem sounds a bit like zero testing, so I won’t be surprised if some asks turn out undecideable or at least difficult in practice.
If and when any of this work happens, we should compare with Klaus Sutner’s package. In fact, it would be a nice timing test to see how quickly the Automata package can compute terms of Thomas’s new sequence. As for now, I can’t immediately tell how to construct a DFA representation that works with the paclet code. Anyone else know how?
Code
Code
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Counting regular languages
by Brad Klee
Wolfram Community, STAFF PICKS, July 24, 2024
https://community.wolfram.com/groups/-/m/t/3233849
by Brad Klee
Wolfram Community, STAFF PICKS, July 24, 2024
https://community.wolfram.com/groups/-/m/t/3233849