-3
$\begingroup$

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?

$\endgroup$
1
  • 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$ Nov 18, 2014 at 9:15

1 Answer 1

1
$\begingroup$

The language is regular.

Denote

$ 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

$\endgroup$
4
  • $\begingroup$ And would you know how to obtain a minimal DFA accepting A? I've tried it, but... $\endgroup$
    – eyhqtl
    Nov 18, 2014 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$ Nov 18, 2014 at 9:13
  • 2
    $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$
    – Raphael
    Nov 18, 2014 at 9:42
  • $\begingroup$ @DavidRicherby May i submit the DFA? $\endgroup$
    – muradin
    Nov 18, 2014 at 14:18

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