1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Jan 30 '16 at 13:16
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you very much!! (I have edited it back to original) $\endgroup$ – avivk Jan 30 '16 at 13:55

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.