Addendum: Counting Valid Regex’s
Addendum: Counting Valid Regex’s
Above we count unique DFAs as a function of number of states. Instead, we could count valid regex’s as a function of string length. However, string length is too messy a notion, so we need to think more carefully about how to grade the pattern set. Recall what we did with BinaryCompositions and IrreducibleBinaryCompositions. Those cases allow only one combinator, so grading by leaf count is quite natural. In the regex’s above, we have a mixture of unary and binary operators, so leaf count makes a bit less sense a subset invariant. Let’s instead make a formal enumerator where each level has a fixed total count of heads and leafs:
In[]:=
forms[__][0]={};forms[vars_,__][1]:=vars;
In[]:=
forms[vars_,unary_,binary_][n_]:=forms[vars,unary,binary][n]=Union[Flatten[Map[Function[head,head/@forms[vars,unary,binary][n-1]],unary]],Flatten[Map[Function[head,Table[Outer[head[#1,#2]&,forms[vars,unary,binary][n-i],forms[vars,unary,binary][i-1],1],{i,1,n,1}]],binary]]]
For example, here is level 4 of the relevant regex case:
In[]:=
test4=formsa.,b.,{Square},{SmallCircle,CirclePlus}[4]
Out[]=
a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,a.∘a.,a.∘b.,b.∘a.,b.∘b.,a.∘a.,a.∘b.,b.∘a.,b.∘b.,a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,(a.∘a.),a.∘b.,b.∘a.,b.∘b.,a.,b.
And we can test the grading property as follows:
In[]:=
Count#,a.b.SquareSmallCircleCirclePlus,Infinity,Heads->True&/@test4
Out[]=
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}
Now that we have such a function, we can run through a range of related examples, finding a lot of (assumed) overlap with pre-existing sequences in the OEIS:
In[]:=
Lengthforms{a.},f.,{}[#]&/@Range[12]
Out[]=
{1,1,1,1,1,1,1,1,1,1,1,1}
In[]:=
Lengthforms{a.},{},g.[2#-1]&/@Range[12]
Out[]=
{1,1,2,5,14,42,132,429,1430,4862,16796,58786}
In[]:=
Lengthforms{a.},f.,g.[#]&/@Range[10]
Out[]=
{1,1,2,4,9,21,51,127,323,835}
In[]:=
Lengthformsa.,b.,f.,g.[#]&/@Range[10]
Out[]=
{2,2,6,14,42,122,382,1206,3922,12914}
In[]:=
Lengthformsa.,b.,f.,g.[#]2&/@Range[10]
Out[]=
{1,1,3,7,21,61,191,603,1961,6457}
In[]:=
Lengthformsa.,b.,f.,g.,h.[#]2&/@Range[10]
Out[]=
{1,1,5,13,57,201,861,3445,14897,63313}
The final result here is half of an upper bound on valid regex patterns. By introducing a few pattern processing rules, we can eliminate duplicate and redundant patterns over the first few terms:
In[]:=
$BadPatterns={CirclePlus[x_,x_],CirclePlus[x_,CirclePlus[x_,_]],CirclePlus[x_,CirclePlus[_,x_]],Square[Square[x_]],_[x_,Square[x_]],CirclePlus[Square[x_],x_],_[Square[x_],Square[x_]]};
In[]:=
$Commutative={h_[h_[x_,y_],z_]:>h[x,h[y,z]],CirclePlus[x__]:>Sort[CirclePlus[x]]};
The first two terms are unchanged:
In[]:=
formsa.,b.,{Square},{CirclePlus,SmallCircle}/@{1,2}Length/@%
Out[]=
a.,b.,a.,b.
Out[]=
{2,2}
The next term loses four patterns due to count decreases, and another term due to commutative equivalence:
In[]:=
formsa.,b.,{Square},{CirclePlus,SmallCircle}[3]Select[Union[%/.$Commutative],FreeQ[#,Alternatives@@$BadPatterns]&]Length@%
Out[]=
a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,a.∘a.,a.∘b.,b.∘a.,b.∘b.,a.,b.
Out[]=
a.⊕b.,a.∘a.,a.∘b.,b.∘a.,b.∘b.
Out[]=
5
Similarly the fourth term decreases from 26 to 11:
In[]:=
formsa.,b.,{Square},{CirclePlus,SmallCircle}[4]Select[Union[%/.$Commutative],FreeQ[#,Alternatives@@$BadPatterns]&]Length@%Complement[%%%,%%]
Out[]=
a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,a.∘a.,a.∘b.,b.∘a.,b.∘b.,a.∘a.,a.∘b.,b.∘a.,b.∘b.,a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,(a.∘a.),a.∘b.,b.∘a.,b.∘b.,a.,b.
Out[]=
a.⊕b.,b.⊕a.,a.∘b.,b.∘a.,a.∘a.,a.∘b.,b.∘a.,b.∘b.,a.⊕b.,(a.∘a.),a.∘b.,b.∘a.,b.∘b.
Out[]=
13
Out[]=
a.⊕a.,b.⊕b.,a.⊕a.,a.⊕b.,b.⊕a.,b.⊕b.,a.∘a.,b.∘b.,a.⊕a.,b.⊕a.,b.⊕b.,a.,b.
While we can be fairly sure that a(4) = 13 [ edit: funny enough, this term was miscounted as 11 earlier due to human error! ], the next term is slightly more sketchy:
In[]:=
formsa.,b.,{Square},{CirclePlus,SmallCircle}[5];Select[Union[%/.$Commutative],FreeQ[#,Alternatives@@$BadPatterns]&]Length@%
Out[]=
a.⊕a.∘a.,a.⊕a.∘b.,a.⊕b.∘a.,a.⊕b.∘b.,b.⊕a.∘a.,b.⊕a.∘b.,b.⊕b.∘a.,b.⊕b.∘b.,a.⊕b.,a.∘a.⊕b.,a.∘(a.∘a.),a.∘a.∘b.,a.∘b.∘a.,a.∘b.∘b.,b.∘a.⊕b.,b.∘(a.∘a.),b.∘a.∘b.,b.∘b.∘a.,b.∘b.∘b.,a.⊕b.∘a.,a.⊕b.∘b.,a.∘b.,b.∘a.,a.⊕b.,b.⊕a.,a.∘b.,b.∘a.,(a.∘a.),a.∘b.,b.∘a.,b.∘b.
Out[]=
31
Perhaps the counting the sequence we’re looking for starts 2,2,5,13,31... Given that regex can be translated back into DFA, a more programmatic way to compute terms of the series should be available to avoid any human error. Can anyone implement such a count?
Actually it might be easy using Klaus Sutner’s paclet:
In[]:=
PacletInstall["KlausSutner/Automata"];
In[]:=
Needs["KlausSutner`Automata`"]
In[]:=
activate=SmallCircle->,Square->,CirclePlus->,a.->"a",b.->"b";
In[]:=
KlausDFALevel[n_]:=AssociationMap#->ReplaceAllReplaceAll[#,activate],[2],x_Graph:>Graph[x,EdgeLabels->"EdgeTag"]&,formsa.,b.,{Square},{CirclePlus,SmallCircle}[n]
We quickly get DFA models for for the first level:
And can verify no overlap with the next level:
On subsequent levels, we need to filter out what we’ve seen already:
If we count these directly, we start to get duplicates on the third level:
Reducing by complement is also easy:
Then our values agree up to the fourth term.
On the fifth level, we can back out mis-counted sequences:
The first two items are the universal language of level four, and the last two items are the monotone repeat languages of level 2. These are not quite as easy to filter, so we miscounted them earlier.
This is a nice usage of Klaus’s paclet assuming it obtains forms canonical by SameQ. For rigor sake we should double check terms using other home-grown implementations.