New answers tagged dfa
0
I believe you have $F(n) = n+2$ for all $n$.
To prove that $F(n) \geq n+2$, we prove $f(0^n) \geq n+2$: consider any DFA with at most $n+1$ states, and let $q_0,\ldots, q_{n+1}$ be the sequence of states visited when reading $0^{n+1}$. By the pigeonhole principle, there exist $0\leq i<j \leq n+1$ such that $q_i = q_j$, thus $q_i \cdots q_j$ is a loop and ...
Top 50 recent answers are included
