# If $A$ is not a regular language and $B$ is a regular language and $B \neq \varnothing$, does $AB$ is not regular language?

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?

• 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. – Theo Bendit Sep 23 '18 at 8:10
• Note: If $A=\{\,0^p\mid p\text{ prime}\,\}$ and $B=0^*$, then $AB$ is regular – Hagen von Eitzen Sep 23 '18 at 8:45
• Why don't you apply the pumping lemma to $L$? – Hagen von Eitzen Sep 23 '18 at 9:41
• 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. – Wakeme UpNow Sep 23 '18 at 10:10
• 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. – 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.