OEIS/DFSA: Difference between revisions
imported>Gfis First version |
imported>Gfis ref. OESI wiki |
||
Line 37: | Line 37: | ||
We begin with 2 columns, and we denote the states by pairs of substates ''s</sub>i</sub>t<sub>j</sub>''. | We begin with 2 columns, and we denote the states by pairs of substates ''s</sub>i</sub>t<sub>j</sub>''. | ||
| 0 0 0 1 1 0 1 1 | | 0 0 0 1 1 0 1 1 # valid inputs | ||
-----+------------------------- | -----+------------------------- | ||
1 s1t1| s1t1 s1t2 s2t1 s2t2 4 | |||
2 s1t2| s1t3 s1t2 s2t3 s2t2 4 | |||
3 s1t3| s1t3 s1x0 s2t3 s2x0 2 | |||
4 s2t1| s3t1 s3t2 s2t1 s2t2 4 | |||
5 s2t2| s3t3 s3t2 s2t3 s2t2 4 | |||
6 s2t3| s3t3 s3x0 s2t3 s2x0 2 | |||
7 s3t1| s3t1 s3t2 x0t1 x0t2 2 | |||
8 s3t2| s3t3 s3t2 x0t3 x0t2 2 | |||
9 s3t3| s3t3 s3x0 x0t3 x0x0 1 | |||
When the states are numbered 1, 2, 3, ..., the table reduces to: | |||
| 00 01 10 11 #vi | |||
-----+------------------------- | |||
1| 1 2 4 5 4 | |||
2| 3 2 6 5 4 | |||
3| 3 0 6 0 2 | |||
4| 7 8 4 5 4 | |||
5| 9 8 6 5 4 | |||
6| 9 0 6 0 2 | |||
7| 7 8 0 0 2 | |||
8| 9 8 0 0 2 | |||
9| 9 0 0 0 1 | |||
There is a [https://github.com/gfis/OEIS-mat/blob/master/contrib/rh/dfsa.pl Perl program] that evaluates such DFSAs: | |||
perl dfsa.pl -d 1 4 "1,2,4,5,3,2,6,5,3,0,6,0,7,8,4,5,9,8,6,5,9,0,6,0,7,8,0,0,9,8,0,0,9,0,0,0" | |||
===Other regular languages=== | |||
'''[https://oeis.org/A124696 A124696]''' is another example of a finite state machine, as explained in the [https://oeis.org/wiki/Number_of_base_k_circular_n-digit_numbers_with_adjacent_digits_differing_by_d_or_less OEIS wiki article]. |
Latest revision as of 21:24, 3 November 2021
Counts of arrays
More than 20000 sequences in the OEIS enumerate arrays with special properties. The sequences were defined by Ron Hardin, often with conjectured ordinary (rational) generating functions. Such o.g.f.s and/or linear recurrences with constant coefficients were also contributed by Colin Barker. We want to derive such g.f.s. systematically. As a first example, we take:
A223615 Number of n X 3 0..1 arrays with rows and columns unimodal. Column 3 of A223620 G.f.: x*(7 + 44*x^2 - 20*x^3 + 20*x^4 - 6*x^5 + x^6) / (1 - x)^7. a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n > 7.
Unimodal words
A unimodal word wi has one "plateau" - first the symbols are increasing (wi <= wi+1), then they are decreasing (wi >= wi+1).
For the alphabet {0, 1} the unimodal words of length n are:
n=1 2 3 4 0 00 000 0000 1 01 001 0001 10 010 0010 11 011 0011 100 0100 110 0110 111 0111 1000 1100 1110 1111 ------------------ # 2 4 7 11 -> (central polygonal numbers)
A word is unimodal iff it does not match the regular expression pattern 100*1. Words of length 1 or 2 are always unimodal.
Deterministic Finite State Automaton (DFSA)
The DFSA for unimodal words over the alphabet {0, 1} has a simple transition table with 3 states:
symbol state| 0 1 -----+--------- s1| s1 s2 s2| s3 s2 s3| s3 x0
We always use a start state of 1. Successor state 0 is "forbidden", since it would lead to a non-unimodal word.
Matrices of words
Now we arrange the words in columns of an n X k matrix, with a specified number k of parallel columns of length n, and we ask for the number of such arrangeents depending on n. In addition, we require that the rows in the matrix also have the unimodal property. Then we get the following DFSA table for k=2 :
We begin with 2 columns, and we denote the states by pairs of substates sitj.
| 0 0 0 1 1 0 1 1 # valid inputs -----+------------------------- 1 s1t1| s1t1 s1t2 s2t1 s2t2 4 2 s1t2| s1t3 s1t2 s2t3 s2t2 4 3 s1t3| s1t3 s1x0 s2t3 s2x0 2 4 s2t1| s3t1 s3t2 s2t1 s2t2 4 5 s2t2| s3t3 s3t2 s2t3 s2t2 4 6 s2t3| s3t3 s3x0 s2t3 s2x0 2 7 s3t1| s3t1 s3t2 x0t1 x0t2 2 8 s3t2| s3t3 s3t2 x0t3 x0t2 2 9 s3t3| s3t3 s3x0 x0t3 x0x0 1
When the states are numbered 1, 2, 3, ..., the table reduces to:
| 00 01 10 11 #vi -----+------------------------- 1| 1 2 4 5 4 2| 3 2 6 5 4 3| 3 0 6 0 2 4| 7 8 4 5 4 5| 9 8 6 5 4 6| 9 0 6 0 2 7| 7 8 0 0 2 8| 9 8 0 0 2 9| 9 0 0 0 1
There is a Perl program that evaluates such DFSAs:
perl dfsa.pl -d 1 4 "1,2,4,5,3,2,6,5,3,0,6,0,7,8,4,5,9,8,6,5,9,0,6,0,7,8,0,0,9,8,0,0,9,0,0,0"
Other regular languages
A124696 is another example of a finite state machine, as explained in the OEIS wiki article.