Which one of the choices is the correct one and how do I get to the answer:
The following question is given: Use the Pumping Lemma with length to prove that the following language is nonregular: $$L=\{bab^{n-2}a^n,\text{ with }n\in\{3,4,5,\ldots\},n\in\Bbb Z\}\;.$$ The solution to this question is partly given as follows:
Assume $L=\{bab^{n-2}a^n,\text{ where }n\in\{3,4,5,\ldots\},n\in\Bbb Z\}$ is regular. Then there exists an FA with, say $k$ states that accepts $L$.
Let $w=bab^{k-2}a^k$ be a word in $L$.
According to the pumping lemma, $w$ may be written as $w=xyz$ such that $\operatorname{length}(x)+\operatorname{length}(y)\le k$ AND $\operatorname{length}(y)>0$.
Which one of the following is not one of the possible correct choices for $y$?
- $y$ comprises the $a$ in between $b$ and $b^{k-2}$.
- $y$ comprises the first $ba$-substring.
- $y$ comprises $ba$ followed by possible $b$’s.
- $y$ comprises $ba$ followed by a possible second $ba$ substring.
I would like to know the answer and how to get to the answer. How do I know what can be $x$, $y$ and $z$. That's the part I don't understand. Thank you.
The answer is choice 4 and here is why that is so:
We know that xy is an initial segment of w, and we know that its length is at most k. The first k characters of w are $bab^{k−2}$, so xy is an initial segment of $bab^{k−2}$. We know that y has to be a non-empty string, because its length is greater than 0, but x can be empty or non-empty. And by this information we can eliminate one of the four choices as a possible value of y.