Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 59 · Getting Started

Alphabets, Strings and Languages

Learn the building blocks of automata theory: alphabets, strings, length, concatenation, powers, Kleene star and operations on languages, with Python code.

Before you can build machines, you need a precise vocabulary for what they read. Theory of computation uses three nested ideas: an alphabet (the available symbols), strings (finite sequences of symbols) and languages (sets of strings). Everything else in the course, from DFAs to Turing machines, is a way to describe or recognize a language.

Alphabets

An alphabet is a finite, non-empty set of symbols, written with the Greek letter Sigma (Σ). Common examples are Σ = {0, 1} for binary, Σ = {a, b} for small examples, and Σ = {a, ..., z} for lowercase letters. The word "finite" matters: a machine must be able to tell its input symbols apart with a fixed rule.

Strings

A string (or word) over Σ is a finite sequence of symbols from Σ. The string 0110 is a string over {0, 1}. Some basic notation:

  • Length |w| is the number of symbols: |0110| = 4.
  • The empty string ε (epsilon) has length 0. It is a real string, not "nothing".
  • Concatenation of x and y, written xy, puts y after x: ab followed by ba gives abba. Concatenating with ε changes nothing.
  • Reversal w^R writes the string backwards: (abc)^R = cba.
  • Power w^n repeats w n times, with w^0 = ε. So (ab)^3 = ababab.
  • A prefix of w is a leading part, a suffix a trailing part, and a substring any contiguous part. ε and w itself are both prefixes and suffixes of w.

Σ^n is the set of all strings of length n over Σ, so it has |Σ|^n members. Σ^* (the Kleene star of the alphabet) is the set of all finite strings, including ε. It is infinite, but countable: you can list it by length, then alphabetically.

Python Strings and the set Sigma^n

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The empty string prints as '', and the counts follow 2^n: 1, 2, 4, 8.

Languages

A language over Σ is any subset of Σ^*. It can be finite, infinite, or even empty. Examples over Σ = {a, b}:

  • L1 = {a, ab, abb} (finite).
  • L2 = all strings that end in b (infinite).
  • L3 = {a^n b^n : n ≥ 0} = {ε, ab, aabb, aaabbb, ...} (infinite, and not recognizable by any finite automaton).
  • ∅, the empty language with no strings at all. Do not confuse it with {ε}, which has exactly one string, the empty one.

Because languages are sets, the usual set operations apply: union, intersection, difference and complement, where the complement of L is Σ^* minus L.

Operations specific to languages

Since the members are strings, languages also have operations that sets in general do not.

  • Concatenation L1 L2 = {xy : x in L1, y in L2}.
  • Power L^n is L concatenated with itself n times; L^0 = {ε}.
  • Kleene star L^* = L^0 ∪ L^1 ∪ L^2 ∪ ... : zero or more strings of L glued together.
  • Kleene plus L^+ = L^1 ∪ L^2 ∪ ... : one or more.
  • Reversal L^R = {w^R : w in L}.

These operations are the raw material of regular expressions, which you will meet in Regular Expressions and Regular Languages. Concatenation and star of infinite languages produce infinite languages, so in code we usually truncate by length.

Python Language operations with a length cutoff

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines show the difference between ∅ and {ε}: concatenating with ∅ wipes everything out (no pair exists), while concatenating with {ε} leaves the language unchanged. These are the same roles that 0 and 1 play in arithmetic.

Counting languages

How many languages exist over Σ = {0, 1}? Σ^* is countably infinite, but the set of all subsets of a countably infinite set is uncountable (Cantor's diagonal argument). Yet there are only countably many programs, because each is a finite string. So almost all languages are not recognized by any machine at all. This simple counting fact is the first hint that some problems are unsolvable, and the later chapters on decidability will return to it.

flowchart LR
    A["Alphabet Σ<br/>finite set of symbols"] --> B["Strings Σ*<br/>finite sequences, countable"]
    B --> C["Languages<br/>subsets of Σ*, uncountable"]
    C --> D["Machine-recognizable<br/>languages, countable"]

Each level is vastly bigger than the one before, except the last: machines can only name countably many languages.

Common mistakes

  • Treating ε as a symbol. It is the string with no symbols, and it is never part of an alphabet.
  • Writing L^* and forgetting it always contains ε, even when L does not.
  • Confusing ∅ (no strings) with {ε} (one string).
  • Assuming a language must be infinite. Finite languages are perfectly good, and (as you will see) always regular.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. How many strings of length 3 exist over the alphabet {0, 1, 2}?

    There are |Σ|^n = 3^3 = 27 strings of length n = 3.
  2. 2. Which statement about the empty string ε is true?

    ε has length 0 and is a prefix and suffix of every string. The empty language ∅ is a set with no strings, which is a different thing.
  3. 3. What is L^* when L = {ab}?

    L^* is zero or more copies of strings from L glued together, so it includes ε (zero copies).
  4. 4. What is L ∅ (concatenating a language L with the empty language)?

    Concatenation needs one string from each language. With no strings in the second language, no pairs exist, so the result is empty.
  5. 5. Why are almost all languages not recognized by any machine?

    A machine has a finite description, so machines can be listed. The set of all languages is uncountable by Cantor's argument.

Summary

  • An alphabet Σ is a finite set of symbols; a string is a finite sequence of them; Σ^* is the set of all strings, including ε.
  • A language is any subset of Σ^*, finite or infinite; ∅ and {ε} are different languages.
  • Besides set operations, languages support concatenation, powers, Kleene star, plus and reversal.
  • Σ^* is countable but the set of all languages is not, so most languages cannot be recognized by any machine.

Next: Grammars and the Chomsky Hierarchy