[seqfan] A108122 investigated using finite state tool

[Dale Gerdemann]

Hello Seqfans,

A108122 appears to count strings of digit blocks in {0,10,11,12} where the
block 111 is forbidden. I checked this for strings up to length 25.

I discovered this by experimentation with the finite state toolkit "Foma",
which is a program that I think people ought to know about. For this test,
I used the extended regular expression:

[x|1 x|1 1|1 2]*  & ~ $[1 1 1];

I used 'x' instead of '0' because, rather unfortunately, '0' is reserved
for another purpose in Foma. The operators here are

[...]     grouping
|         union
*        Kleene star
&       intersection
~       complement
$       containment
There are Unicode alternatives to these, which look quite a bit nicer.

Complement and containment presuppose an alphabet, which Foma defines as
the set of occurring symbols in the extended regular expression. So here
Sigma = {x,1,2}. The Ascii character for Sigma is '?' To count strings of
length 5, for example, the following code can be used:

define myRegex [x|1 x|1 1|1 2]*  & ~ $[1 1 1];
regex myRegex & [? ? ? ? ?];

Foma will compile this into an automaton and count the paths in this
automaton. Even for counting strings of length 25, the result is
instantaneous.

Foma was developed by Mans Hulden for use in Computational Linguistics. But
there's no reason why its use should be limited to CL. The program is free
and is available on GoogleCode.

Dale Gerdemann