# Lower bounding DFA

If the regular language $L$ is defined as $\{ w \in \Sigma^* \mid |w| \leq 140 \}$. Why does any DFA for it must have at least 142 states? Why not only 140 states?

• Is this a question from a textbook, lecture notes? If so, could you provide the source of this question? – fade2black Nov 18 '17 at 1:29
• It is from a pset. The context of the question is also on distinguishability & Myhill_Nerode theorem. – user75706 Nov 18 '17 at 2:02
• I mean you should include it in your OP. – fade2black Nov 18 '17 at 2:03

## 1 Answer

Because $140$ states are not enough.

For any $n>0$, if you have the constraint $|w| \leq n$ then you will have $n+1$ accept states and one additional "dead" (reject) state in case the length of the input is greater than $n$. So in total you have $n+2$ states. For example if $|w| \leq 2$ then you have 4 states: (1), (2), (3), (dead), where states from 1 to 3 are accept states.

 -->(1)--a,b-->(2)--a,b-->(3)--a,b-->(dead)


The "dead" state loops on itself for any input.

But we still need to prove it formally. We could show that the minimum DFA accepting the language $$L =\{ w \in \Sigma^* \mid |w| \leq n \}$$ has $n+2$ states. Let's assume that $x$ and $y$ are strings of different length not greater than $n$. Then each such string corresponds to a single state of the minimum DFA because $x$ and $y$ are distinguishable. To prove it WLOG assume $x$ is the shorter string. Let's choose any string $z$ of length $n-|x|$. Then it follows $\delta(xz) \in F$ while $\delta(yz) \notin F$ since $|yz| > n$. But there are exactly $n+1$ strings of distinct length no greater than $n$ $(\text{namely } 0,1,\dots, n)$, and there must be a single non-accept state. So, the minimum DFA must have $n+2$ states.