|
| |
|
|
A000802
|
|
Maximal number of states in deterministic finite automaton accepting a language consisting of some words of length n.
|
|
0
| |
|
|
1, 2, 4, 7, 11, 19, 34, 50, 82, 146, 274, 529, 785, 1297, 2321, 4369, 8465, 16657, 33041, 65809, 131344, 196880, 327952, 590096, 1114384, 2162960, 4260112, 8454416, 16843024, 33620240, 67174672, 134283536, 268501264, 536936720, 1073807632, 2147549456, 4295033104
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
REFERENCES
| Champarnaud, J.-M.; Pin, J.-E.; A maxmin problem on finite automata. Discrete Appl. Math. 23 (1989), no. 1, 91-96.
|
|
|
FORMULA
| a(n)=sum(min(2^k,2^(2^(n-k))-1),k=0..n). [Sean A. Irvine, Jun 24, 2011]
|
|
|
CROSSREFS
| Sequence in context: A007864 A192670 A118647 * A200377 A080005 A151992
Adjacent sequences: A000799 A000800 A000801 * A000803 A000804 A000805
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jeffrey Shallit (shallit(AT)graceland.uwaterloo.ca)
|
|
|
EXTENSIONS
| a(34)-a(36) from Sean A. Irvine (sairvin(AT)xtra.co.nz), Jun 23 2011
|
| |
|
|
