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

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.

• Why do you think it is not regular? – Ran G. Jan 24 '15 at 17:15
• You pick the word, so you can ignore $w$; just use $a^n b^n$. But then the argument falls apart since we can "hide" everything we ever pump in $w$. – Raphael Feb 24 '15 at 23:07
• possible duplicate of How to prove that a language is not regular? – David Richerby Apr 22 '15 at 7:47

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.