0

$K = \{a^kba^lba^n|kk+l=n\} $
$L=\{a^kba^lba^n|kl=n\} $

Firstly, let's consider language $K$. I use pumping lemma to show that $K\notin CFG$.
Let $s=a^pba^pba^{2p}=uvxyz$
Thanks to pumping lemma: $$(1)|vy|>0$$$$(2)|vxy|\le p$$$$(3)\forall_{i\ge 0}uv^ixy^iz\in K$$

First of all, $v$ and $y$ can't contain $b$ - in against case we violate structur of word. The key to solve this is the fact that thanks to $(2)$ $v$ and $y$ can't contain all of part with letters $a$. So we always violete constraint: $k+l=n$.
Is it ok ?
Moreover, I think that the same solution work for language $L$. Help me, please

user220688
  • 509

1 Answers1

1

What if $u=a^pba^{p-1}$, $v=a$, $x=b$, and $y=a$? Then

$$uv^kxy^kz=a^pba^{p-1+k}ba^{2p-1+k}\in K\;.$$

In fact $K$ is context-free: it can be recognized by a PDA. Start in state $q_0$. Each time you read an $a$, push an $A$ onto the stack and remain in state $q_0$. When you read a $b$, go to state $q_1$. Each time you read an $a$, push an $A$ onto the stack and remain in state $q_1$. When you read a $b$, to to state $q_2$. Each time you read an $a$, pop an $A$ off the stack and remain in state $q_2$. The NFA accepts by empty stack.

Your idea works fine for $L$, though, with $s=a^pba^pba^{p^2}$. Without loss of generality assume that $p>1$. Argue as you did that it’s not possible for $v$ or $y$ to contain a $b$. If $vy$ is contained in just one of the three blocks of $a$s, obviously pumping takes us outside of $L$. The same is true if $vy$ is contained in the union of the first two blocks of $a$s. Suppose, then, that $v=a^k$ is contained in the second block of $a$s, and $y=a^\ell$ is contained in the third block of $a$s. Then

$$uv^ixy^iz=a^pba^{p+(i-1)k}ba^{p^2+(i-1)\ell}\;,$$

and

$$p\big(p+(i-1)k\big)=p^2+(i-1)pk>p^2+(i-1)\ell$$

for $i>1$, since $pk\ge p>\ell$.

Brian M. Scott
  • 616,228