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

305 Views Asked by At

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

There are 1 best solutions below

0
On BEST ANSWER

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.