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

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.

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)$.

• Ah, brilliant! Seems almost obvious to prove looking at it now, thank you! – rawa Oct 29 '15 at 17:43
• @rawa The trick is to decompose the proof obligation; often you get multiple manageable goals "automagically". – Raphael Oct 29 '15 at 17:46
• I very much agree, just writing out the obligations often helps me tremendously in decomposing seemingly difficult proofs into something much simpler. Thank you for reminding me, really need to reinforce this notion for myself haha – rawa Oct 29 '15 at 17:55