Vtyjkyuk

Given language:
L = s∈(0+1)* 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 ?

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:

$$beginarrayll
q_0overset0longrightarrow q_1&q_0overset1longrightarrow q_-1\
q_1overset0longrightarrow q_2&q_1overset1longrightarrow q_0\
q_2overset0longrightarrow q_infty&q_2overset1longrightarrow q_1\
q_-1overset0longrightarrow q_0&q_-1overset1longrightarrow q_-2\
q_-2overset0longrightarrow q_-1&q_-2overset1longrightarrow q_infty\
q_inftyoverset0,1longrightarrow q_infty
endarray$$

States $q_0,q_1,q_2,q_-1$, and $q_-2$ are all acceptor states; $q_infty$ is not.