Show: The set of all languages in which every word has odd length contains non-regular languages.

429 Views Asked by At

Prove that $\xi = \text{The set of all languages in which every word has odd length}$ over $\Sigma = \{a,b\}$ contains non-regular languages.

So I offered this proof and I really think that it has many holes (and I am not even certain if it is correct):

If we look at $\Sigma^*$ then it is obvious that it consists of two types of words: (1) Words of even length (2) Words of odd length

Now if we look at the part of $\Sigma^*$ which are the words of odd length, denoted ${\Sigma^*}_o$, and put it in one set $L$, then $L$ is obviously the (only) language in $\Sigma^*$ that contains ALL the words of odd length. It is trivial to assume that this language is infinite.

Thus, $\xi$ is exactly the set that contains all the subsets of $L$, therefore $\xi$ is infinite also, and non-countable.

Now if we look at $P(\xi)$ (the power set of $\xi$) which we know that it should be of much higher magnitude, then we come to the conclusion that it can not be countable, therefore there must be non-regular languages in $\xi$.

What do you think? If it is wrong, I would be happy for a direction.

1

There are 1 best solutions below

0
On

Your argument is correct but it is non-constructive and there are simpler arguments. For instance, consider the language $L = \{a^nb^{n+1} \mid n \geqslant 0 \}$. Every word in $L$ has odd length, but it is easy to see that $L$ is not regular (for instance by using the pumping lemma).