# Show that $L$ and $\overline L$ cannot be both finite

Let $$L$$ be any language on a nonempty alphabet. Show that $$L$$ and $$\overline L$$ cannot be both finite.

This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz.

My attempt: $$L$$ is a subset of $$\Sigma^*$$, so it can be either finite or infinite. If $$L$$ is finite, then $$\overline L$$ is infinite. If $$L$$ is infinite, that is, $$L = \Sigma^*$$, then $$\overline L = \Sigma^* - L = \Sigma^* - \Sigma^* = \emptyset$$. Therefore, $$L$$ and $$\overline L$$ cannot be both finite.

Is it correct? I tried to write a direct proof. Thanks in advance.

• Please check cs.meta.stackexchange.com/questions/597/…. If you have a doubt about a specific part of the solution, please specify it. Anyway, "If $L$ is infinite, that is, $L = \Sigma^*$" is not correct. I would also explain why "If $L$ is finite then $\bar L$ is infinite". – Dmitry Feb 14 at 22:36

## 2 Answers

If $$L$$ and $$\overline{L}$$ were both finite, then so would $$\Sigma^* = L \cup \overline{L}$$ be, which we know is false.

This is a qualitative statement. We can make it quantitative by considering densities. Let us say that a language is dense if for infinitely many $$n$$, it contains at least half the words of length $$n$$. It is easy to check that at least one of $$L,\overline{L}$$ is dense.

Your intuition is correct, however I wouldn't call it a "formal" proof. A really formal proof (but seriously, its too formal) can be stated like that:

If $$L$$ is infinite, we are done. Otherwise, $$|L|<\infty$$. In particular, there is some $$w\in L$$ such that $$|w|\ge |w'|$$ for every other $$w'\in L$$ - that is, $$w$$ is the longest in $$L$$. Denote $$n:=|w|$$, and notice that $$\{w'\in \Sigma^*\mid |w'|>n\} \subseteq \Sigma^* \setminus L = \bar L$$. Define $$f:\Sigma^*\rightarrow \{w'\in \Sigma^*\mid |w'|>n\}$$ by $$f(w)=0^{n+1}w$$ (instead of $$0$$, you can choose some other letter from $$\Sigma$$). Clearly, $$f$$ is injective, and therefore $$|\Sigma^*|\le |\{w'\in \Sigma^*\mid |w'|>n\}|\le |\bar L|$$. Since $$\Sigma^*$$ is infinite, then $$\bar L$$ is infinite as well, just as required.

Once again, this is a formal solution to the question. Your solution is still definitely valid, but note that $$L$$ being infinite does not automatically imply that $$L=\Sigma^*$$ (Thanks Dmitry for pointing this out in the comments).

• Sounds like an overkill. You can simply say that if both $|L|, |\bar L| < \infty$, then $|\Sigma^*| = |L \cup \bar L| = |L| + |\bar L| < \infty$ - contradiction with infinity of $\Sigma^*$. – Dmitry Feb 14 at 22:41
• You are right. This can be solved way more simply. – nir shahar Feb 14 at 22:42
• Feel free to post it as a separate answer. I will definitely upvote it :) – nir shahar Feb 14 at 22:51
• No, for example, if $\bar L$ would have been all words with even length, then $L$ would be all words with odd length. Clearly, $\bar L$ is infinite, but $L$ is not empty and not even finite. – nir shahar Feb 14 at 23:11
• @Dmitry The network-wide policy is to not post answers in the comments. You lose out on reputation, the asker can't accept your answer, it's easier to miss, etc. – orlp Feb 15 at 0:30