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