0
$\begingroup$

i want to prove that the following Language isn't CF

$L=\{a^kba^kba^k|k\in \mathbb{N}\}$

Let $z=a^nba^nba^n$ be a String from $L$

$n$ is the pumping length and $|z|=3n+2 > n$

and $z=uvwxy$ with $|vx|\geqslant 1$, $|vwx|\leqslant n$

but i'm not sure how to determine the correct substrings, how should i consider them ? I tried the ones below are thy correct ?

Case 1 : $u=a^n,\ uwx=ba^n,\ y=ba^n$

Case 2 : $u=a^{n-l},\ uwx=a^lb,\ y=a^nba^n$

Case 3 : $u=a^nb,\ uwx=a^nb,\ y=a^n$

Case 4 : $u=a^nba^{n-l},\ uwx=a^{l-k},\ y=a^kba^n$

Case 5 : $u=a^nb,\ uwx=a^n,\ y=ba^n$

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 9 '17 at 16:23
0
$\begingroup$

The pumping segments $v$ and $x$ can be anywhere in the string assuming they are at most $n$ apart, i.e., $|vwx|\le n$. Like you I get five possibilities, but I think you wrote some special cases rather than the general picture.

Inside one of the $a$-segments, for instance :

  • the first $u=a^i$, $vwx=a^j$, $y=a^{n-i-j}ba^nba^n$ where $i+j\le n$ and $j\ge 1$. Or
  • the second $u=a^nba^i$, $vwx=a^j$, $y=a^{n-i-j}ba^n$ where $i+j\le n$ and $j\ge 1$. Or
  • the third $\dots$ .

Or overlapping with one of the $b$'s. Of course because of the lengths we cannot overlap with both $b$'s.

  • First: $u=a^{n-i}$, $vwx=a^iba^j$, $y=a^{n-j}ba^n$ where $0\le i,j\le n$, $i+j< n$ .
  • Second $\dots$ .

However this does not solve the pumping problem. Note we repeat the strings $v,x$ when pumping. In these last cases we do not know how $v,x$ look. Do they contain the $b$? More cases.

A shortcut to the proof would be to make the following observation.

  1. The pumping segments cannot contain $b$.

That leaves five cases for the position of $v$, $x$ in the three $a$-segments. Either deal with them or argue

  1. Now that $v$, $x$ can only contain $a$'s we can pump either one or two of the three $a$-segments in $z$. That means after pumping they cannot all contain the same number of $a$'s
$\endgroup$
  • $\begingroup$ thank you for the help, this helped me, i wrote these special cases because my professor told us that we must consider all possible cases of sub strings and then argue for each one by choosing a random pumping length mostly from $i\in\{0,1,2\}$ and pumping each case then see if it's still from the given Language $\endgroup$ – proless8 Jul 10 '17 at 16:33

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.