# What is the minimal states for the language DFA?

Let the language $$L = \{ w: \text{ for any prefix } u \text{ of } w : \left|\#_o(u) - 2\cdot \#_1(u) \right| \le 2 \}$$

What is the minimal number of states for a DFA, accepting $L$?

1. $4$
2. $5$
3. $6$
4. $\infty$ (The language isn't regular)

Now, although the intuition says the answer is $\#4$ it's actually a regular language and the minimal number of states is $6$ (answer $\#3$).

I've tried to think about a construction for a DFA accepting $L$, unsuccessfully.

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael May 20 '15 at 7:49
• See here and here. – Raphael May 20 '15 at 7:51

Here's a hint to get you started. To save typing, let $x=\#_o(u), y=\#_1(u)$. Make a DFA where the states correspond to the value $x-2y$ seen so far. You'll then have states $q_{-2},q_{-1},q_0, q_1, q_2, p$ where $q_0$ is the start state, $q_{-2}, \dotsc, q_2$ are final and $p$ is a "dead" state.
Then, for example, suppose you're in state $q_1$ and see an input of $0$. Then, since $x-2y=1$ and you see another $0$, you'll now have $x$ increased by $1$ so now $x-2y$ is $2$ so on a $0$ you'll pass from $q_1$ to $q_2$. Similarly, on a $1$ you'll pass from $q_1$ to $q_{-1}$.
The prefix condition makes it easy to use our dead state $p$, since if you ever get there, you'll never leave (since any subsequent input will still violate the prefix condition that got you there). You can fill in the details: you get to $p$ from either $q_{-2}$ or $q_{-1}$ on a $1$ or $q_2$ on a $0$.