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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    May 20 '15 at 7:49
  • $\begingroup$ See here and here. $\endgroup$
    – 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$.

Finally, note that without the prefix condition, the language is not regular.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.