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

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?

• If you think it's not regular, why not use the Myhill-Nerode criterion? In contrast to the pumping lemma, it is guaranteed to work. – Yuval Filmus Nov 14 '17 at 14:05
• Can't quite see what the equivalence classes will be in this language. Every string has it's unique suffix - even(w), which means that there are infinitely many classes, thus proving it is irregular? – Billy Joel Nov 15 '17 at 9:44
• You don't need to find out all equivalence classes. It's enough to find infinitely many pairwise inequivalent words. – Yuval Filmus Nov 15 '17 at 10:20
• I tried comparing the indices of two different words x,y concatenated with a random word z . By comparing xz with yz I get that odd(x).odd(z).even(x).even(z) is equivalent to odd(y)odd(z)even(y)even(z), but that doesn't seem to lead to a concrete answer. What feature of these words distributes them in different classes? – Billy Joel Nov 17 '17 at 20:12
• That's something you have to figure out. – Yuval Filmus Nov 17 '17 at 20:49

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.