A000802 Maximal number of states in the minimal deterministic finite automaton accepting a language over a binary alphabet consisting of some words of length n.

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

Offset

0,2

Links

John Cerkan, Table of n, a(n) for n = 0..3300

J.-M. Champarnaud and J.-E. Pin, A maxmin problem on finite automata, Discrete Appl. Math. 23 (1989), no. 1, 91-96.

Formula

a(n) = Sum_{k=0..n} min(2^k,2^(2^(n-k))-1). - Sean A. Irvine, Jun 24 2011

Maple

a:= n-> add((t-> `if`(t>k, 2^k, 2^t-1))(2^(n-k)), k=0..n):
seq(a(n), n=0..36);  # Alois P. Heinz, Apr 13 2022

Prog

(PARI) a(n) = sum(k=0, n, min(2^k, 2^(2^(n-k))-1)) \\ (works while n<29) Michel Marcus, May 25 2013

Crossrefs

Sequence in context: A277271 A192670 A118647 * A236392 A200377 A080005

Adjacent sequences: A000799 A000800 A000801 * A000803 A000804 A000805

Keyword

nonn

Author

Jeffrey Shallit

Extensions

a(34)-a(36) from Sean A. Irvine, Jun 23 2011

Status

approved