Cheap and Secure Web Hosting Provider : See Now

[Answers] Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma?

, , No Comments
Problem Detail: 

In order to show that $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ isn't CFL, I was trying to use a pumping lemma this way: At first we assign $w= A^jB^jA^jB^j ,$ $(w^i=uv^ixy^iz), p<|vxy|, p<j.$

  • if $vy$ contains just $a$s we choose i=0 for $w^i$, so in this case the number of $a$s isn't equal to the $b$s.
  • if $vy$ contains just $b$s we choose i=0 for $w^i$, so in this case the number of $b$s isn't equal to $a$s.
  • if $vy$ contains both $a$s and $b$s then for any i there will be a difference in there quantity compare to the $n$ $a$s and $b$s that aren't in $vy$. Also $vy$ can't contain the whole world since the number of $a$s larger than $p$.
  • Isn't it CFL? Can pumping lemma help here?

I was told in class that it isn't correct to use pumping lemma here, why?

Asked By : avivk

Answered By : Nehorai

Sure you can use the pumping lemma,

String in $L$ consists of four consecutive segments: a $A$ segment followed by a $B$ segment followed by another $A$ segment followed by another $B$ segment. Assume that $L$ is context free and let $p$ denote the pumping length of $L$. consider the string $A^pB^pA^pB^p\in L$.We can write this string as $uvxyz$ where $|uxy|\leq p$ and $|uv|>1$. We look at two cases:

  • case 1: Either $v$ or $y$ contains more than one type of character (i.e at least one of $v$ and $y$ contains both $A$'s $B$'s). In this case, pumping up once to $uv^2xy^2z $ inserts an extra $A^iB^j$ sequence into $s$ i.e the resulting string will contain at least $3\quad A$ segments and $3\quad B$ segments. For instance, if $v=AABB$, then pumping once would result in an additional $AA$ segment followed by an additional $BB$ segment. But string in $L$ contain only four segments

  • case 2: Both $v$ and $y$ contain only one type of character (i.e they are both all $A$'s or all $B$'s). Since $uxy\leq p$, $uxy$ contains letters from at most $2$ segments of $s$. Pumping once to $uv^2xy^2z$ increases the number of characters in one or two of the segments, but leaves the remainig segments untouched. Thus, the number of characters in each segment will be unbalanced.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback