0
$\begingroup$

I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular.

My suggestion is as follows:

Assuming $L\in{}REG$, let $p$ be the number that exists for $L$ according to the pumping lemma.

Let $w=ab^{p}ba^{p}$ with $|w|=2p+2>p$.

Since $w\in{}L$, $w$ can be written as $w=xyz=ab^{p}ba^{p}$, so that:

  1. $|xy|\leq{}p$, in this case $xy=ab^{q}$ with $q\leq{}n-1\leq{}p$
  2. $|y|\geq{}1$, in this case $y=b^{n}$
  3. $\forall{}i\geq{}0,xy^{i}z\in{}L$

But for $i=0$ we have $xy^{0}z=xz=aba^{n}\in{}L$ which violates the definition of $L$, so that $L\notin{}REG$.

Does this constitute a sufficient proof with the pumping lemma or am I at least on the right track? I would appreciate any feedback.

$\endgroup$
  • $\begingroup$ $x$ could be empty, so in your step (2), $y$ could be of the form $ab^n$. You have to show that this possibility also leads to a contradiction. Fortunately, this isn't hard. $\endgroup$ – Rick Decker Apr 30 '15 at 18:32
1
$\begingroup$

It's not sufficient proof because you only proved that if you choose the decomposition $x=ab^q$ and $z$ the rest does not meet the three points of the pumping lemma but remember that the lemma says:

If $L$ is regular then there is a constant $N>0$ associated to $L$ such that $\forall \sigma \in L$ with $|\sigma|\geq N$ $\textbf{exist}$ a decomposition $\sigma = xyz$ ...

Summarizing. you proved that your decomposition doesn't work. Now you have to try all other possible decompositions.

$\endgroup$

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.