Hermann Gruber, Jonathan Lee and Jeffrey Shallit: Enumerating regular expressions and their languages - Scripts used to compute results

Maple code

As described in the book chapter, we are interested in computing asymptotic upper and lower bounds for the number of regular languages that can be specified via a regular expression of a specified length. We do this for alphabet sizes k = 1, 2, 3, 4, 5, 6; moreover, "length" refers to ordinary, alphabetic, or reverse polish notation length. In some cases, we are interested in "star-free" languages (those specified without using Kleene-star closure); in effect, this means finite languages.

Organization of files

All asymptotic order estimate code, together with the output behind the results in the book chapter, can be accessed in the file: maple-scripts.tgz. These scripts were designed for and run under Maple 13.

There are four directories, each taking the form: final-scripts/[upper | lower]/[gen | sf], where

upper and lower indicate whether the code is to compute upper or lower bounds; and
gen and sf indicate whether general languages (without any restrictions) or star-free languages are to be enumerated.

Computing the lower bounds

The Maple script for computing the star-free lower bounds is maple_sf_lower.mpl. The output can be generated by starting an interactive Maple session and entering the commands:

> read `maple_sf_lower.mpl`;
> for i from 1 to 6 do writeto("sf_alph_lower_" || (convert(i, string)) || "ary.txt"); sf_alph_lower(i); end do;
> for i from 1 to 6 do writeto("sf_rpn_lower_" || (convert(i, string)) || "ary.txt"); sf_rpn_lower(i); end do;
> for i from 1 to 6 do writeto("sf_ord_lower_" || (convert(i, string)) || "ary.txt"); sf_ord_lower(i); end do;

Similarly, the Maple script for computing the general lower bounds is maple_gen_lower.mpl. The output can be generated by starting an interactive Maple session and entering the commands:

> read `maple_gen_lower.mpl`;
> for i from 1 to 6 do writeto("gen_alph_lower_" || (convert(i, string)) || "ary.txt"); gen_alph_lower(i); end do;
> for i from 1 to 6 do writeto("gen_rpn_lower_" || (convert(i, string)) || "ary.txt"); gen_rpn_lower(i); end do;
> for i from 1 to 6 do writeto("gen_ord_lower_" || (convert(i, string)) || "ary.txt"); gen_ord_lower(i); end do;

The results of the computation for each case are stored in a file with the naming convention [gen | sf]_[ord | alph | rpn]_lower_[1,2,3,4,5,6]ary.txt, where

gen and sf indicate whether general languages (without any restrictions) or star-free languages are to be enumerated, using the grammars in Tables 3 and 1, respectively, from the book chapter;
the terms ord, alph and rpn indicate the measure of length considered (respectively: ordinary, alphabetic and reverse polish notation);
upper and lower indicate whether the code is to compute upper or lower bounds; and
the number between 1 and 6 denotes the alphabet size.

Computing the upper bounds

Unlike the case of lower bounds, there is one Maple script per output file; the script has the same name as its output, aside from extension (.mpl versus .txt). Similar to before, the results of the computation for each case are stored in a file with the naming convention [ord | alph | rpn]_[snf | snf_sf]_[1,2,3,4,5,6]ary.txt, where

the terms ord, alph and rpn indicate the measure of length considered (respectively: ordinary, alphabetic and reverse polish notation);
snf and snf_sf indicate whether general languages (without any restrictions) or star-free languages are to be enumerated (note: "snf" denotes "strong normal form", meaning the grammar listed in the book chapter's Table 7 is used); and
the number between 1 and 6 denotes the alphabet size.

There are some exceptions to the naming convention:

in the unary (star-free and general) cases for all measures of length, the files are called [ord | alph | rpn]_hg2_(sf_)1ary.[mpl | txt], as having a unary alphabet enables the Table 6 optimizations to the grammar listed in Table 5;
in the non-unary general cases for ordinary length, the files are called ord_hg1_[2,3,4,5,6]ary.[mpl | txt], as the grammar in Table 5 is used instead of the computationally infeasible strong normal form grammar in Table 7;
in the general cases for alphabetic length, only the files for alphabet sizes of 2,3,4 are provided, as the growth rates for all alphabet sizes are related as in Table 8.

The output was generated by running each Maple file individually; this can be automated by issuing the following command at a bash prompt:

for z in `ls *.mpl`; do maple $z; done

C++ code

We provide here the code used for our exact enumerations; in particular, these programs generate the data for Tables 10 to 15 in the book chapter. The code should successfully compile with any recent version of gcc (last verified: gcc 4.6.1).

Organization of the files

All of the C++ tools written for this project can be accessed in the file: exact-enum.tgz. There are numerous interesting tools in here:

dfaprint — given a regular expression, print out the state table for the unique minimal DFA that accepts the generated language
uniq — given a list of regular expressions, removes those that generate duplicate regular languages and return the pruned list
parse_list — given a grammar, return its commutative image in a format usable by Maple. (This was used to aid producing the Maple scripts above.)
parse_list in enumeration mode — given a grammar to generate regular expressions, enumerate all regular languages that result from it, with various grouping options defined at compile-time

For more information, see the README file. To compute the enumerations listed in Tables 10 to 15 in the book chapter, compile the programs using compile.sh; the desired numbers can then be obtained by running compute.sh.