Course contentsShow
← Computer Science
Lesson 1760 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Languages as Sets of Strings

Define a formal language as a set of strings over an alphabet, including finite and infinite languages.

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 letter a followed by zero or more bs
  • 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.