Let's say that we have a language $L$ that is finite.
How can I prove that the complement of $L$, i.e., $\bar{L}$, is always an infinite language?

Obs.: infinite language in this case means that is possible to construct an infinite set of words that are acceptable by $\bar{L}$.


The set $\Sigma^*$ is an infinite set (you can build a bijection between the naturals and the words in $\Sigma^*$ if you wish to prove this, or you can observe that, for every $k \in \mathbb{N}$, $\Sigma^*$ contains at least one word of length $k$).

Let $L$ be a finite language and suppose towards a contradiction that $\overline{L} = \Sigma^* \setminus L$ is finite. Then $\Sigma^* = L \cup \overline{L}$ must also be finite (since it's a finite union of finite sets). This provides the sought contradiction.


Here is a formal proof for the statement (warning, this really is a formal proof, and hence is not very intuitive):

Let $\Sigma$ be a non-empty alphabet (either finite or infinite), and let $L\subset \Sigma^*$, with $|L|\in \mathbb{N}$ ($L$ is finite).

Let $\alpha \in \Sigma$. By definition of the klenee-star operator, we can construct a function $g:\mathbb{N}\rightarrow \Sigma^*$ by $g(k)=\alpha^k$ ($\alpha$ repeated $k$ times). This function is one-to-one, since $|g(k)|=|\alpha^k|=k$ (where $|w|$ denotes the length of the string $w$), and thus for any $k_1, k_2$ with $g(k_1)=g(k_2)$ we must have $k_1=|g(k_1)|=|g(k_2)|=k_2$.

Thus, we proved that $\aleph_0=|\mathbb{N}|\le |\Sigma^*|$.

Now, let us begin showing that $\aleph_0\le |\Sigma^* \setminus L|$. Denote by $n_{max}:=\max\{|w|\mid w\in L\}+1$, and define $f:\mathbb{N}\rightarrow (\Sigma^*\setminus L)$ by $f(k)=\alpha^{n_{max}+k}$.

First, we have to show that this really is a function (by showing that $f(k)\in \Sigma^*\setminus L$ for all $k\in\mathbb{N}$). Indeed, if we assume towards contradiction that $f(k)\in L$ for some $k$ - we get that $|f(k)|<n_{max}$ by the definition of $n_{max}$. But $|f(k)|=|\alpha^{n_{max}+k}|=n_{max}+k \ge n_{max}$ which is clearly a contradiction (we got that $n_{max}<n_{max}$).

Now we have to show that $f$ is one-to-one. By a similar argument to what we did before to prove that $\Sigma^*$ is infinite, we can conclude that $f$ is one-to-one, and hence $\aleph_0=|\mathbb{N}|\le |\Sigma^*\setminus L|=|\bar L|$ which is exactly what we wanted to show.


Lets denote $n:=|L|\in \mathbb{N}$.

For any nonempty $\Sigma$, it is clear that $\Sigma^*$ is infinite.

By definition, $\bar L = \Sigma^*\setminus L$. Therefore, $|\bar L| = |\Sigma^*\setminus L| = |\Sigma^*|-|L| = \infty - n=\infty$.

It is not a formal proof (neither a valid one), but it should suffice for you as intuition to understand why $\bar L$ is infinite.

  • $\begingroup$ Sorry, in your answer you mean that $\Sigma$ is a finite alphabet? In this case, what do you mean by $\Sigma^*$ ? $\endgroup$
    – igorkf
    Nov 19 '21 at 17:44
  • $\begingroup$ -1, I find subtracting cardinalities is handwavy at best and wrong at worst (and in all cases potentially confusing to beginners). For example, $|\mathbb{Z}\setminus\mathbb{N}| = \infty - \infty = 0$, despite negative integers existing. $\endgroup$
    – ComFreek
    Nov 19 '21 at 18:18
  • $\begingroup$ Yes, I agree with @ComFreek. This is not a valid proof. $\endgroup$
    – igorkf
    Nov 19 '21 at 18:25
  • $\begingroup$ I never said this is a valid proof. Its just intuition. Substracting cardinalities is only well-defined when the RHS of the subtraction is finite (as in this case) $\endgroup$
    – nir shahar
    Nov 19 '21 at 18:36
  • $\begingroup$ Ok, you didn't said that this was a valid proof. $\endgroup$
    – igorkf
    Nov 19 '21 at 18:42

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.