Proving a language is not regular using the pumping lemma

Question

Let $$ L =\Big\{ \ ba^{2^k}b^{i_1}ab^{i_2}a\dots b^{i_k}a \ \Big|\ k\ge 1,\ i_j\ge1 \ ,\ 1\le j \le k\ \Big\}\ . $$ Using the pumping lemma prove that $L$ isn't regular.

The answer given to this is:

Assuming $L$ is regular, from the pumping lemma there is $n\in\mathbb{N}$ such that for $z=ba^{2^n}b^{i_1}ab^{i_2}a\dots b^{i_n}a$, $z\in L$, $|z|\ge n$ can be expressed as $z=uvw$ where $u=ba^s (0\le s\le n-2)$, $v=a^t (1\le t\le n)$, and $w=a^{2^n-s-t}b^{i_1}ab^{i_2}a...b^{i_k}a$. Choosing $i=2$ we get $$ \begin{aligned} uv^iw &=b\ a^sa^{2t}a^{2^n-s-t}\ b^{i_1}ab^{i_2}a\dots b^{i_k}a \\ &=b\ a^{2^n+t}\ b^{i_1}ab^{i_2}a\dots b^{i_k}a \end{aligned} $$ but $n>1$ so $$2^n < 2^n + t \le 2^n + n < 2^n + 2^n = 2\cdot 2^n =2^{n+1}$$ a contradiction therefore $L$ is not regular.

I don't understand why the last inequality leads to a contradiction

Answer 1

If the language were regular, the pumped word $$ uv^2w=ba^{2^n+t}b^{i_1}ab^{i_2}a\dots b^{i_k} $$ would have to be in $\ L\ $, which would require $\ 2^n+t=2^k\ $, by the definition of $\ L\ $. But since $\ 2^n<2^n+t<2^{n+1}\ $, it is impossible for $\ 2^n+t\ $ to be any integral power of $\ 2\ $.

Answer 2

Note that a string $x\in L$ if and only if it takes the form $ba^{2^k}b\text{(stuff)}$. In particular, the number of $a$'s in the first "block" must be a power of $2$. Here, you see that the number of $a$'s in the first block lies strictly between $2^n$ and $2^{n+1}$ and thus cannot be a power of $2$, yet $x$ is in $L$, a contradiction.

Answer 3

This answer is not exactly answering the question about why the given argument is working. Because the argument makes a contradiction work for a lot of strings of a general shape involving variables $i_1,i_2,\dots,i_k$. And the contradiction is not really transparent in such a not needed generality. Instead, it would be simpler to take one special word in $L$, show a contradiction for this one word. This is done in the answer, the argument being related with the one in the question.

---

We note first the following special requirement for an element of $L$. Each word $w\in L$ has a specific (let's call it) "key" $k$ among $1,2,3,\dots$ being explicitly of the shape $$ \begin{aligned} w &= ba^2b^{i_1}a &&\text{ with key $k=1$ or } \\ w &= ba^4b^{i_1}ab^{i_2}a &&\text{ with key $k=2$ or } \\ w &= ba^8b^{i_1}ab^{i_2}ab^{i_3}a &&\text{ with key $k=3$ or } \\ &\vdots \\ w &= ba^{2^k}b^{i_1}ab^{i_2}a\dots ab^{i_k}a &&\text{ with key $k$ or } \\ \vdots \end{aligned} $$ and apply now the pumping lemma, assuming that $L$ is regular.

(We try to get a contraction. Above, the $b$-powers $i,j,s,i_1,i_2,\dots,i_k$ are each $\ge1$. Note that the "first subword $a$-power" is at least $a^2$.)

Then there exists some pumping length $p$, so that for each word $w\in L$ of length $|w|\ge p$ can be split as $w=xyz$ with $y$ non-empty, $xy$ has length $\le p$, and all words $xz$, $xyz=w$, $xyyz$, $xyyyz$, ... are also in $L$.

Let us consider the first / minimal $n$ so that $2^n>p$. Consider the following special element in $L$: $$ w = b\ a^{2^n}\ \underbrace{b\ a\ b\ a\ b\ a\ \dots\ a\ b\ a}_{n\text{ occurrences of }b}\ . $$ Then $|w|=1+2^n+2n>p$. This word has the "key" equal to $n$. Write this $w$ as $w=xyz$, as insured by the pumping lemma, and from $|xy|\le p<2^n$ we obtain $xy$ as a left substring of $ba^{2^n}$.

• The case of $x$ empty is immediately excluded, since then $y$ is of the shape $ba^s$, and then a word of the shape $xyyyy\dots yz$ has the "key" determined from its left $xy$ part, but can contain then more $b$-occurrences then the "key" allows, from the $yyy\dots y$ part, contradiction.

• The case of $x$ not empty makes $x$ of the shape $x=ba^s$ with $s\ge 0$ and so $y=a^t$ with $t\ge 1$. Then every word $$w_q:=x\underbrace{yyy\dots y}_{q\text{ times}}z$$ has the same amount $(n+1)$ of $b$'s, the same one as $xyz=w_1=w$, it determines thus a fixed "key" equal to $n$, but then the $y^q=yyy\dots y$ part in $w_q$ gets length bigger $2^n$ already for $q=2$, contradiction. (Or delete $y$, i.e. $q=0$ to get a shorter length and an other contradiction.)

$\square$