Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $s = a^pb^{2p}$, now which one of those decomposition is correct:
$x=a^k$, $y=a^l$, $z=a^{p-k-l}b^{2p}$, where $k+l \leq p$
$x=a^{p-k}$, $y=a^k$, $z=b^{2p}$, where $1\leq k \leq p$
$x=\epsilon$, $y=a$, $z=a^{p-1}b^{2p}$
or are they the same? I've read in multiple answers that we don't get to pick the decomposition, but I'm not sure how to understand this, because to me all of those decompositions are legitimate.
Here is the statement of the pumping lemma:
If $L$ is a regular language then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) for all $i \geq 0$, $xy^iz \in L$.
Here is the contrapositive, which is how you usually apply the lemma:
Suppose that $L$ is a language such that for every $p$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w = xyz$ satisfying $|xy| \leq p$ and $y \neq \epsilon$, there exists $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.
When you apply the lemma to show that a language is not regular, you have to consider all possible decompositions satisfying $|xy| \leq p$ and $y \neq \epsilon$. For each of them you need to find an $i$ such that $xy^iz \notin L$.
