3
$\begingroup$

Is the language of words containing same number of 101s and 010s regular? If yes, how can I design a DFA for it?

In general, is the language of words containing equal number of strings which one is "one's complement" of the other one is regular (like the language of words containing equal number of 01s and 10s which is regular)? Is there any counterexample?

|cite|improve this question
$\endgroup$
4
$\begingroup$

No, the language of words containing same number of 010s and 101s is not regular.

Consider $x_n=(0100)^n$ and $y_n=(1011)^n$. Then $x_iy_j$ contains $i$ number of 010s and $j$ number of $101s$. That is, $x_iy_j$ is in the language if and only if $i=j$.

So $x_i$ represents a distinct Nerode-Myhill equivalence classes for all $i$. Since there are infinitely many such $x_i$, there are infinitely many Myhill-Nerode equivalence classes. By Myhill–Nerode theorem, the language is not regular.

Here are several related exercises. Exercise 2 answers the more general situation in the question. Exercise 3 is a further generalization.

Let $\Sigma=\{0,1\}$.

Exercise 1. The language of words over alphabet $\Sigma$ containing the same number of 01s and 10s is regular. The language of words over alphabet $\{0,1, 2\}$ containing the same number of 01s and 10s is not regular.

Exercise 2. Let nonempty $w\in \Sigma^*$. Let $\overline w$ be the one's complement of $w$. For example, $\overline{010010111}=101101000$. Let $E_w$ be the language of words over $\Sigma$ containing the same number of $w$s and $\overline w$s. Show that $$ E_w\text{ is regular} \iff w=01\text{ or }w=10$$ (It may take a while to do this exercise.)

Exercise 3. Let $u$ and $v$ be two different non-empty words in $\Sigma^*$. Let $E_{u,v}$ be the language of words over $\Sigma$ containing the same number of $u$s and $v$s. Let $N_{u,v}$ be the language of words over $\Sigma$ containing no $u$ nor $v$ as a subword. Show that $$ L_{u,v}\text{ is regular } \iff \{u,v\}=\{01,10\}\text{ or } E_{u,v} = N_{u,v}.$$ (It may take a while to do this exercise.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Could you prove it using pumping lemma instead of Myhill_Nerode theorem? @Apass.Jack $\endgroup$ – Marzi Apr 5 '19 at 20:07
  • $\begingroup$ For the sake of contradiction, suppose $E_{010}$ is pumpable with pumping length $p$. Consider $(010)^p0011(101)^p=uvw$, where $|uv|\le p$, $|v|\ge 1$. There are a few cases for $u, v$. Regardless, you can find either $uw\not \in E_{010}$ or $uv^2w\not\in E_{010}$. $\endgroup$ – John L. Apr 5 '19 at 21:57
  • $\begingroup$ In Exercise 3, "$L_{u,v}\text{ is regular }$" should be "$E_{u,v}\text{ is regular }$". $\endgroup$ – John L. Apr 5 '19 at 22:10
  • 1
    $\begingroup$ I do not understand how your exercise 3 relates to the fact that $u=001$ and $v=100$ also defines a regular language. $\endgroup$ – Hendrik Jan Apr 6 '19 at 13:23
  • 1
    $\begingroup$ A recent paper "Counting Subwords and Regular Languages" (which has been presented at DLT 2018, LNCS Vol. 11088) characterizes the strings for which $E_{u,v}$ is regular. This the case when one of $u,v$ is "interlaced" by the other (Theorem 4). As far as I understand this means that any word (different from $u$) that has prefix and suffix $u$ must also have a subword $v$ (or the other way around). This then seems to imply that the number of substrings $u,v$ never differs more than 1. $\endgroup$ – Hendrik Jan Apr 6 '19 at 13:34

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.