Languages as Sets of Strings
What You'll Learn
You'll learn how formal languages in computer science are precisely defined as sets of strings formed from an alphabet, and how these sets can be finite or infinite.
The Core Idea
In the theory of computation, a formal language is simply a set of strings built from a particular alphabet. That's it—no more complicated than that!
Remember that an alphabet is a finite set of symbols (like {0, 1} or {a, b, c}), and strings are sequences of those symbols. A language is just a collection of some (or all, or none) of the possible strings you can make.
Finite Languages
Some languages contain a fixed, countable number of strings:
- Language L₁ =
{a, ab, aab}— exactly three strings over alphabet{a, b} - Language L₂ =
{00, 11}— two binary strings - Language L₃ =
{}— the empty language (contains no strings at all)
Infinite Languages
Other languages contain infinitely many strings. These are often described using patterns or rules:
- Language L₄ =
{0, 00, 000, 0000, ...}— all strings of one or more zeros - Language L₅ =
{a, ab, abb, abbb, ...}— the letterafollowed by zero or morebs - Language L₆ = all valid Python programs (yes, that's an infinite language!)
The Kleene star operation you learned earlier (Σ*) creates the language of all possible strings over alphabet Σ, which is always infinite (unless Σ is empty).
Key Takeaway: A formal language is a set of strings over an alphabet—it can be finite (specific strings) or infinite (described by a pattern or rule). This simple definition is the foundation for understanding what computers can and cannot compute.