2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 14 '17 at 14:05
  • $\begingroup$ 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? $\endgroup$ – Billy Joel Nov 15 '17 at 9:44
  • $\begingroup$ You don't need to find out all equivalence classes. It's enough to find infinitely many pairwise inequivalent words. $\endgroup$ – Yuval Filmus Nov 15 '17 at 10:20
  • $\begingroup$ 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? $\endgroup$ – Billy Joel Nov 17 '17 at 20:12
  • $\begingroup$ That's something you have to figure out. $\endgroup$ – Yuval Filmus Nov 17 '17 at 20:49
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.