Cheap and Secure Web Hosting Provider : See Now

[Solved]: When using the Pumping lemma, how do I deal with different cases of y?

, , No Comments
Problem Detail: 

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$

I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know how to handle different cases of y in pumping lemma.

Asked By : bsinowa

Answered By : Rick Decker

To review, the PL says that if a language $L$ is regular, then there is an integer $p$ such that for any string $s\in L$ of length, $|s|\ge p$ we can write $s=xyz$ with

  1. $|y|>0$
  2. $|xy|\le p$
  3. $xy^iz\in L$, for all integers $i\ge 0$

Assume your language is regular and select the string $ab^pab^pab^p$ to pump. Now, where can $y$ live? Since $|xy|\le p$ you know that $xy$ lives in the first $p$ or fewer characters of $s$, namely $xy=ab^k$ for some $k<p$. We then have two possibilities for $y$: it either contains the first $a$ or it doesn't, so we have two possibilities, where I've colored the string y: $$\begin{array}{c} (\color{red}{ab\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)\\ (a\color{red}{b\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b) \end{array}$$

Then for each case we argue thus:

  1. $y$ is $ab^n$ (i.e., $x=\epsilon$), with $0\le n\le p$. Then $xyz=ab^pab^pab^p=(ab^n)b^{p-n}ab^pab^p$. Then $xy^2z=(ab^n)(ab^n)b^{p-n}ab^pab^p=ab^nab^pab^pab^p$. It's not difficult to see that this cannot be in $L$, so we've reached a contradiction.
  2. $y$ is $b^n$ (i.e., $x=ab\dotsc b$). Then $xy^2z = ab^pb^nab^pab^p$ and again, this string can't be in $L$.

In all cases, we reach a contradiction, so our initial assumption, that $L$ was regular, was false.

By the way, it's easier to use the candidate string $a^pba^pba^pb$, since for this we only have one possibility for where $y$ could live, namely among the first string of a's.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32814

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback