1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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". $\endgroup$ – Dmitry Feb 14 at 22:36
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ 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^*$. $\endgroup$ – Dmitry Feb 14 at 22:41
  • $\begingroup$ You are right. This can be solved way more simply. $\endgroup$ – nir shahar Feb 14 at 22:42
  • 1
    $\begingroup$ Feel free to post it as a separate answer. I will definitely upvote it :) $\endgroup$ – nir shahar Feb 14 at 22:51
  • 1
    $\begingroup$ 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. $\endgroup$ – nir shahar Feb 14 at 23:11
  • 1
    $\begingroup$ @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. $\endgroup$ – orlp Feb 15 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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