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

Question

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?

Answer 1

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.