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$
1
  • $\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$ Apr 30, 2015 at 18:32

1 Answer 1

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 and acknowledge you have read our privacy policy.