How do I show that $a^n w b^n$ is not regular?

Question

Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular.

I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the middle part $w$.

I would pick the symbols $\ a^na^mb^mb^n $ as a starting point and show that this does breach at least one of the three properties of the pumping lemma. At this point I don't know if this is the right word to pick & how I do continue from here.

Answer 1

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression $$ a(a+b)(a+b)^*b, $$ assuming that $0 \notin \mathbb{N}$ (otherwise the language is just $\Sigma^*$). The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

• ($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
• ($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have $$ s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$} $$ for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.