L = {s∈(0+1)* | for every prefix s' of s, $\mid n_{0}(s')-n_{1}(s') \mid \leq 2 $} is regular?

Question

Given language: L = {s∈(0+1)* | for every prefix s' of s, $\mid n_{0}(s')-n_{1}(s') \mid \leq 2 $} is regular?

---

My Try:

Somewhere it explained as: here we need just 6 states to recognize L.

#0 - #1 = 0
#0 - #1 = 1
#0 - #1 = 2
#0 - #1 = -1
#0 - #1 = -2

If the difference goes above 2 or below -2, we go to a dead state. All other states are accepting. This transition to dead state is possible because of the words "for every prefix s' of s" in L and that is what makes this language regular.

Can you explain please, how we count number of $0's$ and $1's$ in strings of the language?

AFAIK : I think, we need for two variables for that, I got confusion. would you include NFA/DFA for language ?

Answer 1

We don’t actually count the $0$s and $1$s: we just keep track of the difference. The difference $n_0(s')-n_1(s')$ increases by $1$ every time we read a $0$ and decreases by $1$ every time we read a $1$. If the difference is always in the set $\{-2,-1,0,1,2\}$, we want to accept the string, and if it ever goes outside that set, we want to reject the string, so we need only six states: one for each value of the difference that is in that set, and one for being outside the set.

Let $q_0$ be the initial state. We’ll design the DFA so that it’s in state $q_0$ whenever it has read the same number of $0$s and $1$s. There will also be the following states:

• $q_1$; the machine will be in this state when the number of $0$s read is one more than the number of $1$s;
• $q_2$; the machine will be in this state when the number of $0$s read is two more than the number of $1$s;
• $q_{-1}$; the machine will be in this state when the number of $0$s read is one less than the number of $1$s;
• $q_{-2}$; the machine will be in this state when the number of $0$s read is two less than the number of $1$s; and
• $q_\infty$; the machine will be in this state when the numbers of $0$s and $1$s read so far differ by more than $2$.

The meanings assigned to the states tell you what most of the transitions must be. For instance, in state $q_0$ reading a $0$ must put the machine in state $q_1$, while reading a $1$ must put it in state $q_{-1}$. State $q_\infty$ is a garbage (or trap) state that collects the words that are not to be accepted. The full set of transitions is:

$$\begin{array}{ll} q_0\overset{0}\longrightarrow q_1&q_0\overset{1}\longrightarrow q_{-1}\\ q_1\overset{0}\longrightarrow q_2&q_1\overset{1}\longrightarrow q_0\\ q_2\overset{0}\longrightarrow q_\infty&q_2\overset{1}\longrightarrow q_1\\ q_{-1}\overset{0}\longrightarrow q_0&q_{-1}\overset{1}\longrightarrow q_{-2}\\ q_{-2}\overset{0}\longrightarrow q_{-1}&q_{-2}\overset{1}\longrightarrow q_\infty\\ q_\infty\overset{0,1}\longrightarrow q_\infty \end{array}$$

States $q_0,q_1,q_2,q_{-1}$, and $q_{-2}$ are all acceptor states; $q_\infty$ is not.