Finite vs. Infinite Languages

1. Defining Finite and Infinite Languages

At its core, the distinction is straightforward and rests on the definition of a language as a set of strings.

• A language is finite if it is a finite set of strings. That is, the number of strings in the language is a specific, non-negative integer.
• A language is infinite if it is an infinite set of strings.

Let's look at some examples to make this concrete. Consider the alphabet $\Sigma =\{a,b\}$.

Examples of Finite Languages:

• $L_1=\{a,ab,ba,bbb\}$. This language contains exactly four strings.
• $L_2=\{w\in {\Sigma }^{\ast }\mid |w|=3\}$. This language consists of all strings of length 3: $\{aaa,aab,aba,abb,baa,bab,bba,bbb\}$. It has $2^3=8$ strings.
• The empty language, $L_3=\varnothing$. It contains zero strings.
• The language containing only the empty string, $L_4=\{ϵ\}$. It contains one string.

Examples of Infinite Languages:

• $L_5=\{a^n\mid n\ge 1\}$. This language is $\{a,aa,aaa,aaaa,\dots \}$ and clearly has no upper limit on the length or number of its strings.
• $L_6={\Sigma }^{\ast }$. This is the language of all possible strings over $\Sigma$, which is infinite.
• $L_7=\{w\in {\Sigma }^{\ast }\mid w{\text{ starts with }}^{\prime }{a}^{\prime }\}$. This includes $\{a,aa,ab,aaa,aab,aba,abb,\dots \}$.

The following image provides a clear, side-by-side comparison.

To see these concepts explained with more examples, the following short video is very helpful.

As we saw in the last lesson, the Kleene star operation is our primary tool for generating infinite languages from finite ones. If a language $L$ contains any string other than the empty string $ϵ$, then its Kleene closure $L^{\ast }$ will be an infinite language.

2. A Deeper Look: Countability and Its Implications

The distinction between finite and infinite leads to a fascinating and profound result in computation theory. To appreciate this, we need to briefly touch upon the idea of countability, which you may have encountered in discrete mathematics.

• A set is countably infinite if its elements can be put into a one-to-one correspondence with the natural numbers ($\mathbb{N}$). In essence, you can create a list that enumerates every element in the set without missing any.
• A set is uncountable if it is infinite, but its elements cannot be listed in this way.

So, how does this apply to languages?

All Languages are Countable

First, let's consider the set of all possible strings over an alphabet, ${\Sigma }^{\ast }$. If the alphabet is not empty, this set is countably infinite. We can prove this by listing all strings, first grouped by length, and then alphabetically within each group.
For $\Sigma =\{a,b\}$, the list would look like this:

1. $ϵ$ (length 0)
2. $a$ (length 1)
3. $b$ (length 1)
4. $aa$ (length 2)
5. $ab$ (length 2)
6. $ba$ (length 2)
7. $bb$ (length 2)
8. $aaa$ (length 3)
   ...and so on.

Since every possible string appears somewhere on this infinite list, the set ${\Sigma }^{\ast }$ is countably infinite. Because any language $L$ is a subset of ${\Sigma }^{\ast }$, it follows that every formal language is countable (either finite or countably infinite).

The Set of All Languages is Uncountable

Here is the surprising twist. While any single language is countable, the set of all possible languages is uncountably infinite.

Why? The set of all languages over $\Sigma$ is the power set of ${\Sigma }^{\ast }$, written $\mathcal{P}({\Sigma }^{\ast })$. Cantor's theorem in set theory states that the power set of any set $A$ always has a strictly greater cardinality than $A$ itself.

• The cardinality of ${\Sigma }^{\ast }$ is countably infinite, denoted ${\aleph }_0$.
• The cardinality of $\mathcal{P}({\Sigma }^{\ast })$ is $2^{{\aleph }_0}$, which is uncountably infinite ($\mathfrak{c}$, the cardinality of the real numbers).

The following reading provides a more formal treatment of these ideas and their crucial consequence.

This is a central idea in the theory of computation. We have an uncountable number of possible languages, but we only have a countable number of tools to describe them (e.g., programs, grammars, regular expressions, all of which are finite strings of symbols). This means there must be an infinite number of languages that are simply beyond our ability to describe or compute. This is a limit we will explore throughout this course.

Conclusion

In this lesson, we established the fundamental classification of languages as either finite or infinite.

Key Takeaways:

• A finite language contains a countable, limited number of strings.
• An infinite language contains an unlimited number of strings.
• Operations like the Kleene star are a primary mechanism for generating infinite languages from finite specifications.
• While every individual language is countable (either finite or countably infinite), the total number of possible languages is uncountably infinite.
• This countability mismatch proves that there must be languages that cannot be described by any finite representation, a foundational concept for the limits of computability.

We've now completed our initial exploration of the basic concepts: alphabets, strings, and languages. We are ready to move from simply describing languages to processing them.

Preview of the Next Lesson:
In our next lesson, we will begin Module 2 by introducing our first formal model of computation: the Finite Automaton. We will learn how to define these abstract machines, visualize them, and see how they can act as "recognizers" for a specific class of (often infinite) languages.