0
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy