# DFA for the language of non-empty words that are no longer than $2^6$

I was given a question in Automata that I need to prove or disprove, and I thought about this language:

$$L = \{w\in \{0, 1\}^*\mid 1\le |w| \le 2^6\}$$ Can you please help me to figure out if its minimal DFA contains only 6 states?

How can I get intuition about DFA sizes?

• The pumping constant in the pumping lemma is the number of states in the minimal DFA. The number of states is also the number of Myhill-Nerode equivalence classes. Apr 29 at 21:51

Suppose the minimal DFA $$(Q, \delta, q_0, F)$$ contains strictly less than $$2^6$$ states. Then there exists a state $$q$$ and two words $$u$$, $$v$$ such that $$|u| < |v| \leqslant 2^6$$ and $$\delta(q_0, u) = \delta(q_0, v) = q$$.