I was given the following question:
Use the Pumping Lemma with length to prove that the following language is non-regular:
$L = \{b^na^{100}b^{2n}, \text{where n} = 1, 2, 3,...\}$
Use the prompts below to complete the proof
Assume
Then there exists
We choose any word w =
Thus we can write w =
The according to the pumping lemma with length,
There is/are __ possible choice(s) for y
If y is pumped in each of the above case(s),
Now, my answer, actually how far I came, is as follow:
Assume L is a regular language.
Then there exists an FA with, say k states that accepts L.
We choose any word w = $b^na^{100}b^2n$ in L.
Thus we can write w = $b^ka^{100}b^{2k}$
The according to the pumping lemma with length, w may be written as w = xyz such that |x| + |y| <= k and |y| > 0
Then I don't know further. I do know that y is 1 b or more. y is also at most k b's.
I would appreciate it if you will correct my mistakes and also finish the answer. Thank you
You’ve filled in the first two blanks correctly, but after that you’ve gone a bit astray, I think because you’re not seeing how the contradiction is going to arise.
It’s true that you can start with any word in $L$, so $w$ could be $b^na^{100}b^{2n}$ for any $n\in\Bbb Z^+$, and the pumping lemma would say something about other members of $L$, but if we want to make matters easy for ourselves, we’ll take $w=b^ka^{100}b^{2k}$. Then the pumping lemma says that we can write $w=xyz$, where $|y|\ge 1$, $|xy|\le k$, and $xy^nz\in L$ for each $n\ge 0$. So what can $y$ be? We know that $xy$ is the first $|xy|$ characters of $w$, and $|xy|\le k$, so $xy$ is contained in the first $k$ characters of $w$. And $w$ begins with $k$ $b$s, so $xy$ is a string of $b$s, say $xy=b^\ell$. What are the possible choices for $\ell$? It has to be at least $1$: $x$ can be the empty string, but we know that $|y|\ge 1$. And it can be at most $k$, since we know that $|xy|\le k$. Thus, $1\le\ell\le k$, and there are therefore $k$ possible choices for $y$, from $b^1$ through $b^k$.
Suppose that we pump $y$ in any of these cases: if we pump $y$ up to $y^2$, we change $y=b^\ell$ to $y^2=b^{2\ell}$, adding $\ell$ $b$s, and we get the word $b^{k+\ell}a^{100}b^{2k}$. And this is our contradiction: on the one hand the pumping lemma says that this must be in $L$, but on the other hand it clearly is not in $L$, since $2k\ne 2(k+\ell)$ (because $\ell\ne 0$). Thus, the initial assumption that $L$ is regular must have been false.
It is possible to use other initial words to get a contradiction, but this is the simplest.