I'm interested in proving the irregularity of some language L, which is defined as follows:
$0, 1 \in L$
If $w \in L$, then $w 1^{|w|} \in L$
I tried to prove this using the pumping lemma, using the string: $w1^{|N|}$, where $N$ is the constant from the lemma. My initial idea was that if I 'force' $xy$ to either be a part of the first $N$ characters (i.e a substring of $w$) or a part of the last $N$ characters (in which case $xy$ would contain only $1$'s), then by pumping I'd get a string which doesn't belong to the language. However, the problem is that is that there can be a situation that xy is located exactly at the point of concatenation of $w$ and $1^{|N|}$, at which case its hard to know whether or not pumping leaves us in the language or out of it.
I'd be glad if you could give me some clues as to how to prove this language is irregular.
Thanks!
For any string $w \in L$ we must have either $w = 0, w = 1,$ or $w = w_21^{|w_2|}$ for some other $w_2$ in $L.$ So, we must have that $|w| = 2^x$ for some integer $x \geq 0.$
Here's why: suppose this was not true for every $w \in L.$ Then, there must be some shortest possible counterexample $s.$ If $s$ is $0$ or $1$ then we trivially have $x = 0.$ If $s$ is anything else, we must have $s = w1^{|w|},$ but because $s$ is a smallest example and clearly $|w| < |s|,$ we must have $|w| = 2^y,$ implying that $|s| = 2^y2^y = 2^{y+1},$ and $y \geq 0$ implies $x = y+1 > 0.$
Now, supposing $L$ had pumping length $p,$ consider the string $1^{2^p} \in L.$ (once again we can prove this is always in $L$ by induction, but I'll spare the details for time's sake)
The pumping lemma tells us that we have to be able to decompose this string as $xyz = 1^{2^p}$ so that $|y| \geq 1, |xy| \leq p,$ and $xy^az \in L$ for all integers $a \geq 0.$ Let's take $a = 2.$
Because $|xy| \leq p$ we can safely say $1 \leq |y| \leq p.$ Now, because $|xy^2z| = |xyz| + |y|,$ adding $2^p$ on all sides gives us $1 + 2^p \leq |xy^2z| \leq p + 2^p.$ Now because $2^p > p$ for all $p \geq 1,$ we can conclude that $2^p < |xy^2z| < 2^p + 2^p = 2^{p+1}.$
Now because $xy^2z$ must be in $L,$ we must have $|xy^2z| = 2^n$ for some integer $n \geq 0,$ giving us $2^p < 2^n < 2^{p+1}.$ Because $f(x) = 2^x$ is strictly increasing, this gives us that $p < n < p+1,$ so $0 < n-p < 1.$ This implies that $n - p$ is not an integer, which contradicts the closure of integers over addition and multiplication.