[Solved]: Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA

Problem Detail: 

$L = \{a^i b^j a^k \ | \ k > i + j\}$

Use the pumping lemma to show that this language cannot be accepted by an FA.

Proof:

Suppose $L$ can be accepted by an FA.

Suppose a string $s = xyz \in L$, where

$$\begin{align} &x=a^n \\ &y=b \\ &z=a^{n+2} \end{align} $$.

Then a string $t = a^n b^i a^{n+2}$ should also be in $L$ for $i \ge 0$, $n+i<n+2$ and should also be accepted by an FA. But if $i=3$,

$$\begin{align} n+i = n + 3 \\>n + 2 \end{align}$$

and $t \not \in L$, which is a contradiction. Thus, $L$ cannot be accepted by an FA.

---

Is this proof thorough? I am worried about the line $n+i<n+2$, because it doesn't work for all values of $i$. Should I pick a string that works for all possible cases?

Asked By : badjr

Answered By : Raphael

Your basic idea (in particular the choice of $t$) works, but there are some issues with the "proof" as such:

• What is $n$?
• Why do you have $y=b$ have to be pumped? You have to work against all allowed decompositions of $t$!
• $n+i < n+2$ does indeed not work for all $i$, but that's kind of the point. Just drop that condition.

I suggest you read our reference posts about how to read and apply the Pumping lemma properly, and then browse our pumping-lemma questions for more examples.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11317