Words equal to the concatenation of their odd and even position - characters

Question

Let $\Sigma = \{0, 1\}$ and $$L = \{ w \in \Sigma^* | w = \mathrm{odd}(w) · \mathrm{even}(w) \},$$ where $\mathrm{odd}(w) = w_1, w_3, w_5 \ldots{}$ and $\mathrm{even}(w) = w_2, w_4, w_6, \ldots{}$ are the words constructed from the characters in all the odd and even positions of the string. I.e. $w = 0110110110 \in L$, because $\mathrm{odd}(w) = 01101, \mathrm{even}(w) = 10110$ and $w = 01101 \cdot{} 10110 = \mathrm{odd}(w) \cdot{} \mathrm{even}(w)$.

Is $L$ regular?

I've tried using the Pumping Lemma for strings of the sort $0^{2n+1}1$ but I can't fix the value of $v^i$ from $w = uvx$ to have an either even or odd length.

I also tried to construct the DFA but it seems to need an infinite number of states to "track" which characters of $w$ get mapped to $\mathrm{odd}(w) \cdot \mathrm{even}(w)$, so my best bet is it's irregular, which means I need to find a way to prove it with the Pumping-Lemma.

Any ideas how I can find a suitable string for the Pumping Lemma?

Answer 1

It would be more convenient to index word positions starting with zero. Let us take a look at $L \cap \Sigma^{2^n}$. Any word $w \in L \cap \Sigma^{2^n}$ satisfies $$ w = w_0 w_2 \ldots w_{2^n-2} w_1 w_3 \ldots w_{2^n-1}. $$ You can check that for $0 \leq m < 2^{n-1}$ and $b \in \{0,1\}$, this is equivalent to $$ w_{2^{n-1}b + m} = w_{2m+b}. $$ In other words, if we think of the index as an $n$-bit string, then this is the same as $w_i = w_{\mathrm{rot}(i)}$, where $\mathrm{rot}(i)$ is obtained by rotating $i$ to the left.

A necklace is an equivalence class of words under rotation. What we have shown above is that $w \in L \cap \Sigma^{2^n}$ iff $w_i$, interpreted as a function $\{0,1\}^n \to \Sigma$, is constant on necklaces. Denoting the number of necklaces of length $n$ by $N_2(n)$, we deduce that $$ |L \cap \Sigma^{2^n}| = 2^{N_2(n)}. $$ The explicit formula for $N_2(n)$ shows that $N_2(n) \sim 2^n/n$.

---

It is known that if $L$ is a regular language then there exists a modulus $m \geq 1$ such that for every $0 \leq i < m$ there exist constants $C,d,\lambda \geq 0$ such that for $N \equiv i \pmod{m}$, $$ |L \cap \Sigma^N| \sim C N^d \lambda^N. $$ We can calculate $\lambda$ as $\lim_{N\to\infty} |L \cap \Sigma^N|^{1/N}$ (the limit taken over $N \equiv i \pmod{m}$).

Now suppose that our $L$ were regular. Choose $i$ so that infinitely many values $2^n$ satisfy $2^n \equiv i \pmod{m}$. We have $$ |L \cap \Sigma^{2^n}|^{1/2^n} = 2^{N_2(n)/2^n} = 2^{O(1/n)} \longrightarrow 1, $$ and so $\lambda = 1$. However, that implies that $|L \cap \Sigma^{2^n}|$ should have polynomial growth (in $2^n$), whereas it clearly has superpolynomial growth.