[seqfan] Another "Language counting" proposal

[brad klee]

Define binary regex as any valid expression of two free variables, two binary
functions (cat and or; times and plus; etc.) and one unary function (star).

Ex. star[or[a,b] ] is the universal language.

Define weight function of a regex to count total number of free variables
and function heads.

Ex. weight[star[or[a,b] ]] = 4 .

The proposals are as follows, with terms calculated by the code here:
https://community.wolfram.com/groups/-/m/t/3233849

Number of unique regular languages determined by a weight=n binary regex

{2, 2, 9, 15, 49, 104, 298, 702, 2021, 4965} (* S1 *)

Number of unique regular languages determined by an irreducible weight=n binary regex
{2, 2, 5, 13, 27, 82, 167, 514, 1209, 3438} (* S2 *)

The two sequence--call them S1, S2 resp.--should obey the following
inequality by term: S2 <= S1 <= 2 * [A091147](https://oeis.org/A091147) . They are not related by
differences. Both are good, but my preference is the second one. It

seems more useful to me.

I can't guarantee these terms, because I haven't checked Klaus's paclet
thoroughly, so please look at them with skepticism. For now it's just an
idea, perhaps if someone else digs in it will gain momentum...

Cheers,

--Brad

https://community.wolfram.com/groups/-/m/t/3233849