-1
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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 questions for more examples.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.