3
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Ah, brilliant! Seems almost obvious to prove looking at it now, thank you! $\endgroup$
    – rawa
    Oct 29, 2015 at 17:43
  • $\begingroup$ @rawa The trick is to decompose the proof obligation; often you get multiple manageable goals "automagically". $\endgroup$
    – Raphael
    Oct 29, 2015 at 17:46
  • 2
    $\begingroup$ 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 $\endgroup$
    – rawa
    Oct 29, 2015 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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