How can I prove that the language $\{ab^kab^kab^k\subset \{a,b\}^* | k \geq 0\}$ is non context-free? I've tried applying the pumping lemma but can't write a proof without considering multiple different cases of possible subwords.

  • 1
    $\begingroup$ You can't recognize strings of given language with single stack. $\endgroup$ – Mithlesh Upadhyay Dec 6 '15 at 13:58

Assume that the language is context-free. Then the pumping lemma says (since the language is clearly infinite) that there is a string in the language that splits into $uvwxy$ such that $uv^nwx^ny$ is in the language for every $n\ge 0$ and $v, x$ are not both empty. In particular, both $uvwxy$ and $uwy$ are in the language.

Now neither $v$ nor $x$ can contain an $a$, because then $uvwxy$ and $uwy$ would have different numbers of $a$s, but every word in the language has exactly 3 $a$s. So both $v$ and $x$ must consist entirely of $b$s.

However, then going from $uvwxy$ ot $uwy$ would correspond to taking one or more $b$s away from at most two of the $b^k$ groups in $uvwxy$, so $uwy$ cannot be in the language after all.


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.