0
$\begingroup$

This question already has an answer here:

I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong?

L={ab}, assume the language is regular so by the pumping lemma there exists some n, and σ = αβγ and σ' = αβ^kγ ∈ L for all non negative k.

σ = aaabbb

α = aa

β = ab

γ = bb

then σ'= αβ^2γ for k=2, σ' =aaababbb

σ'∉ L, a contradiction, thus L is not regular.

L as described I know to be a regular language so I would expect to find ∈ L. This is due to my choice of β spanning across two characters but there is nothing I can find in the pumping lemma which forbids this.

$\endgroup$

marked as duplicate by David Richerby, dkaeae, Apass.Jack, Evil, Yuval Filmus regular-languages Jun 12 at 12:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

The pumping lemma gives you a pumping length $n$ and $\alpha, \beta, \gamma$ under the conditions specified in it so that $\alpha \beta^k \gamma \in L$ for all $k \ge 0$. You do not get to choose $\alpha, \beta, \gamma$ as you please. Also, the pumping lemma works for all words of length at least $n$, not simply an arbitrary word $\sigma$.

The trick when using the pumping lemma, then, is picking a word longer than the pumping length and such that any decomposition into $\alpha, \beta, \gamma$ (obeying the conditions specified in the lemma) can be used to derive the contradiction that you need.

$\endgroup$
  • $\begingroup$ Can you put this in the context of the above example? you say any decomposition works, what makes my above decomposition invalid? Even if n were the length of word it wouldn't pass the pumping step. $\endgroup$ – Kaari Landry Jun 11 at 15:00
0
$\begingroup$

Take $n=3$. Since there are no words of length $\ge n$, trivially all such words can be pumped.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.