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

Question

$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?

Answer 1

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.

Answer 2

I'm assuming that n is the number of states in your FA and you chose your string so the length of x is equal to or greater than n

in Which case you have to remember that one of the conditions for the pumping lemma is that the length of the string xy is equal to or smaller than n.

this means that if you choose $t=\{a^n b^i a^{2n}\}$,
y cannot contain any b's since $a^n$ has to be in xy.