This is the exercise:

Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at most 2. Determine if A is a regular language and prove it.

Ok, as @roi-divon commented, A is a regular language. I've tried to obtain de minimal DFA accepting A but I haven't got it... Someone knows?

  • 3
    $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. $\endgroup$ – David Richerby Nov 18 '14 at 9:15

The language is regular.


$ L^k = \{ x \ | \ \forall \alpha \in Prefix(x): |\#_0(\alpha)-\#_1(\alpha)| \leq k \} $

Your language is $L = L^1$.

We shall prove, using Myhill-Nerode theorem that each $L^1$ is regular (actually for any $k,\ L^k$ is regular).

Define equivalence classes of $R_L$ as follow:

  • for $-k \leq i \leq k: \ S^i = \{ x \ | \ \#_0(\alpha)-\#_1(\alpha) = i, \forall \alpha \in Prefix(x): |\#_0(\alpha)-\#_1(\alpha)| \leq k \}$
  • $S_{out} = \{ w | \exists \alpha\in Prefix(x): |\#_0(\alpha)-\#_1(\alpha)| \gt k\}$

We can see that $L^k = \bigcup_{-k \leq i \leq k}S^i $

Clearly, the equivalence classes are not empty, they don't intersect and the union is $\Sigma^*$

Assume $x,y \in S_{out}$, we show that $x R_L y$: clearly from every $z \in \Sigma^*: \ xz,yz \notin L$ (have "bad" prefixes")

Assume $x,y \in S^i$, and assume there is a $z \in \Sigma^*$ such that $xz \in L$ but $yz \notin L$. Then $yz$ has a prefix $y \beta$ such that the difference between 0's and 1's is larger than k ($\beta$ is prefix for z). By counting the number of 0's and 1's of $x \beta$ we get that it's larger then k, in contradiction that $xz \in L$

Now we show that if $x,y$ in different classes, then $(x,y) \notin R_L$.

Assume $ x \in S^i, \ y \in S_{out}$: then for $z = \epsilon: \ xz = x \in L, yz = y \notin L$. Therefore $(x,y) \notin R_L$

Assume $x \in S^i, \ y \in S^j$, and $j \neq i$. w.l.o.g, $i > j$. Examine $z = 0^{k-i+1}$. Counting 0's and 1's, we get that $xz \notin L$, and $yz \in L$. Therefore $(x,y) \notin R_L$

By that We've proved that $L = L^1$ is regular

  • $\begingroup$ And would you know how to obtain a minimal DFA accepting A? I've tried it, but... $\endgroup$ – eyhqtl Nov 18 '14 at 9:08
  • $\begingroup$ Also, rather than this lengthy proof via Myhill-Nerode, it's much easier to just produce a DFA for this: six states should suffice. $\endgroup$ – David Richerby Nov 18 '14 at 9:13
  • 2
    $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Nov 18 '14 at 9:42
  • $\begingroup$ @DavidRicherby May i submit the DFA? $\endgroup$ – muradin Nov 18 '14 at 14:18

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