Proving that picking odd-numbered symbols can create the universal set from a non-regular language

Question

Let's define the following operations:

$odd(string) = $ odd characters of $string$, $even(string) = $ even characters of $string$

Now say we have some language $L$, we will then define the following languages:

$odd(L) = \{odd(w): w \in L\}$, $even(L) = \{even(w): w \in L\}$

Need to prove that there exists a non-regular language, $L_N$, such that $odd(L_N)$ and $even(L_N)$ are both regular languages.

I thought of a few examples that might produce obvious regular languages with $odd$ and $even$, one of which was the language:

$L_1 = \{w \in \{a,b\}^*: |a|_w = |b|_w\}$, where $|x|_w =$ # of $x$'s in the string $w$

I know how to prove that this is non-regular, and upon inspection of a lot of values of $odd(L_1)$ and $even(L_1)$, it appears both produce the language $\{a,b\}^*$ which is obviously a regular language. Don't really know how I could prove that equality though.

Answer 1

You want to show that $\operatorname{odd}(L_1) = \{a,b\}^*$. This is a set equality claim, and you show it the way you can approach any such claim:

1. Show $\operatorname{odd}(L_1) \subseteq \{a,b\}^*$.

   That's trivial.

2. Show $\operatorname{odd}(L_1) \supseteq \{a,b\}^*$.

   Let $w \in \{a,b\}^*$. Can you construct $w' \in L_1$ so that $w = \operatorname{odd}(w')$?

   You only need to fix symbol counts, so brute force works: $w' = w_1 \overline{w_1} \cdots w_n \overline{w_n}$ with $\overline{x}$ the "inverse", i.e. it maps $a$ to $b$ and vice versa.

   Thus, $w \in \operatorname{odd}(L_1)$. Since $w$ was chosen arbitrarily, the claim follows.

A similar proof works for $\operatorname{even}(L_1)$.