I am trying to proof that

$L = \{ 0^11^2...0^{n-1}1^n0^{n-1}...1^20^1\}$ where $n >= 0$ is not a regular language.

So my method is to put

$S = 0^11^2...0^{n-1}$

$W = S1^nS^R$

And then proof $S^R$ is not a regular language using pumping lemma. But as my understanding goes, the closure property is for regular language only and not the other way around. So From above I've got that

$S$ and $S^R$ is not a regular language. But $1^n$ is a regular language. So how to proof that $W$ is not a regular language?

  • 1
    $\begingroup$ You can't write $W = S1^nS^R$, since that would allow for, say, $01100011000110$. If you write it as a concatenation of languages like this, you cannot control the value of $n$ between the two definitions. $\endgroup$ – Theo Bendit Sep 23 '18 at 8:10
  • 3
    $\begingroup$ Note: If $A=\{\,0^p\mid p\text{ prime}\,\}$ and $B=0^*$, then $AB$ is regular $\endgroup$ – Hagen von Eitzen Sep 23 '18 at 8:45
  • $\begingroup$ Why don't you apply the pumping lemma to $L$? $\endgroup$ – Hagen von Eitzen Sep 23 '18 at 9:41
  • $\begingroup$ How exactly? (Normally I work with $W = XYZ$ and X = $a^i$, $Y = a^j$ but in this case, the variable is at the centre and I don't know how to prove). It would be so kind if you could give me a hint. Thanks. Also from the first comment, I just notice that. Thank you. $\endgroup$ – Wakeme UpNow Sep 23 '18 at 10:10
  • $\begingroup$ For the title question: consider the counterexample $A = \{ 0^m 1^n \mid m \ge n \}$ and $B = 1^*$. Then $AB = 0^* 1^*$ is regular. $\endgroup$ – Daniel Schepler Sep 23 '18 at 15:38

Okay, I have asked my senior for help

So what he told is

Let $L = \{ 0^11^2...0^{n-1}1^n0^{n-1}...1^20^1\}$. Given $W = XYZ$ for $\forall W\in L$

We got $|W| = n^2$. For arbitrary Y, $1\le|Y|\le n$

Consider $n^2 \lt n^2 + 1 \le |XY^2Z| \le n^2 + n < n^2 + 2n < (n + 1)^2$

So $n^2 < |XY^2Z| < (n+1)^2$

Thus proving $XY^2Z \notin L$. From pumping lemma we can conclude that $L$ is not regular.


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.