Before any student can comfortably read a transition diagram or understand why a particular string is accepted by a machine, there is a small but essential layer of mathematics that needs to be in place first. Theory of Computation does not invent brand-new mathematics; instead, it borrows a handful of ideas from set theory and discrete mathematics and repurposes them to describe machines, languages, and computation itself. This chapter walks through exactly those building blocks.
Many students rush past this chapter, treating it as a formality before reaching the "real" content like automata and Turing machines. That approach usually backfires, because almost every later definition in TOC leans on the vocabulary introduced here. A string is defined as a sequence built from an alphabet. A language is defined as a set of strings. A transition function is, technically, a special kind of relation. Skipping this foundation makes every later chapter feel harder than it needs to be.
In this tutorial, you will learn what sets, relations, and functions mean in the context of TOC, how alphabets and strings are formally defined, what operations can be performed on strings, and how all of these ideas combine to define the concept of a formal language. Each idea is explained with simple, practical examples so that the notation feels familiar rather than intimidating.
A set is simply a well-defined collection of distinct objects, referred to as elements or members of the set. In Theory of Computation, sets are used constantly to describe collections of symbols, states, strings, and even entire languages. A set can be described in two common ways: by listing its elements directly, known as roster form, or by describing a rule that its elements must satisfy, known as set-builder form.
Roster form: A = { 1, 2, 3, 4, 5 }
Set-builder form: A = { x | x is a natural number and x <= 5 }
Both notations above describe exactly the same set. Roster form works well for small, finite sets, while set-builder form becomes essential once a set contains infinitely many elements, which happens frequently in TOC since most interesting languages contain infinitely many strings.
| Operation | Symbol | Description |
|---|---|---|
| Union | A ∪ B | Contains every element that belongs to A, to B, or to both. |
| Intersection | A ∩ B | Contains only the elements that belong to both A and B at the same time. |
| Difference | A − B | Contains elements that belong to A but do not belong to B. |
| Complement | A' | Contains every element in the universal set that does not belong to A. |
| Cartesian Product | A × B | Contains every possible ordered pair formed by taking one element from A and one from B. |
These operations reappear throughout TOC in disguised forms. For instance, combining two languages using union corresponds directly to the idea of accepting a string if either of two separate machines would accept it, a concept you will encounter again when studying regular expressions.
A relation describes a connection between elements of two sets. Formally, given two sets A and B, a relation R from A to B is simply a subset of the Cartesian product A × B. In plain terms, a relation is a collection of ordered pairs where the first element comes from A and the second comes from B, and together the pair represents some meaningful association between them.
A = { 1, 2, 3 }
B = { a, b }
R = { (1, a), (2, b), (3, a) }
Here, R is a valid relation from A to B because every pair in R has its first element taken from A and its second element taken from B. This exact idea reappears later in TOC when defining the transition function of a finite automaton, which is essentially a relation connecting a state and an input symbol to the next state the machine should move to.
Certain relations, particularly those defined on a single set, are studied because of special properties they may or may not have. These properties matter because a relation with all three of the following properties is called an equivalence relation, a concept used later when grouping equivalent states together in automata minimization.
A simple everyday example of an equivalence relation is "has the same birthday month as," since every person shares a birthday month with themselves, the relationship works in both directions, and if two people share a birthday month with a third person, they all share the same birthday month with each other.
A function is a special type of relation where every element of the first set, called the domain, is related to exactly one element of the second set, called the codomain. Unlike a general relation, a function cannot map a single input to more than one output. This restriction is precisely what allows functions to represent deterministic behavior, which becomes critical when defining how a deterministic finite automaton decides its next state.
f: A → B where A = { 1, 2, 3 }, B = { x, y }
f(1) = x
f(2) = y
f(3) = x
This is a valid function because every element of A maps to exactly one element of B, even though two different inputs happen to map to the same output. If element 1 mapped to both x and y at the same time, the mapping would no longer qualify as a function, only as a general relation.
This exact distinction is why deterministic finite automata use a transition function, producing exactly one next state for every combination of current state and input symbol, while non-deterministic finite automata are allowed to use a more general transition relation, permitting multiple possible next states for the same input.
With sets, relations, and functions established, the next step is to connect these ideas to computation. This connection begins with the concept of an alphabet, which in TOC has a much more specific meaning than the everyday use of the word.
An alphabet, usually written using the symbol sigma, is defined as a finite, non-empty set of symbols. These symbols do not need to be letters in the traditional sense; they can be digits, special characters, or entirely abstract symbols, as long as the set itself is finite.
Σ = { 0, 1 } (binary alphabet)
Σ = { a, b, c } (a three-symbol alphabet)
Σ = { start, stop } (an alphabet with word-like symbols)
A string, sometimes called a word, is defined as a finite sequence of symbols chosen from a given alphabet. Strings can be as short as a single symbol or as long as needed, and a special string containing no symbols at all, called the empty string and usually written as the Greek letter epsilon, is also considered a valid string over any alphabet.
| Term | Description |
|---|---|
| Length of a String | The total number of symbols present in the string, usually written as |w| for a string w. |
| Empty String | A string with zero symbols, having a length of 0, denoted using the symbol epsilon. |
| Concatenation | Joining two strings together in order to form a single longer string. |
| Reverse of a String | The same sequence of symbols written in the opposite order. |
| Substring | A contiguous sequence of symbols taken from within a larger string. |
| Prefix and Suffix | A prefix is the beginning portion of a string, while a suffix is the ending portion of a string. |
Σ = { a, b }
w1 = "ab"
w2 = "ba"
Length: |w1| = 2
Concatenation: w1w2 = "abba"
Reverse of w1: "ba"
Another important idea connected to alphabets is Σ*, read as "sigma star," which represents the set of every possible string that can be formed using symbols from the alphabet, including the empty string, with no limit on length. Since strings can be arbitrarily long, Σ* is always an infinite set, even when the alphabet itself contains only one or two symbols. This single idea explains why the study of languages in TOC almost always deals with infinite collections of strings rather than small, finite lists.
Once alphabets and strings are clearly defined, a language can finally be described in precise terms. A formal language is simply a subset of Σ*, meaning it is any collection of strings formed from a given alphabet, following whatever rule or pattern the language is meant to represent.
Σ = { 0, 1 }
L1 = { w | w contains an even number of 0s }
L2 = { w | w starts and ends with the same symbol }
L3 = { ε, 0, 00, 000, 0000, ... } (strings of only 0s)
This definition might look simple, but it is extraordinarily powerful, because almost every problem a computer can be asked to solve can be reframed as a language membership question. Asking whether a given number is even can be reframed as asking whether its binary representation belongs to a particular language of strings ending in 0. Asking whether a program contains a syntax error can be reframed as asking whether the source code belongs to the language defined by that programming language's grammar.
Since a language is simply a set of strings, the same set operations discussed earlier in this chapter apply directly to languages as well, along with a few operations unique to strings and languages.
| Operation | Description |
|---|---|
| Union of Languages | Contains every string that belongs to either language, combining both sets of strings. |
| Intersection of Languages | Contains only the strings that belong to both languages at the same time. |
| Concatenation of Languages | Contains every string formed by joining a string from the first language with a string from the second language. |
| Kleene Star of a Language | Contains every string formed by concatenating zero or more strings taken from the original language. |
| Complement of a Language | Contains every string over the alphabet that does not belong to the original language. |
These operations are not just theoretical exercises. They directly explain why regular expressions support union, concatenation, and repetition as their core building blocks, since regular expressions are essentially a compact notation for describing languages built using exactly these operations.
It is worth pausing to connect these ideas back to what comes next in this course. A finite automaton will later be formally defined using a set of states, an alphabet, and a transition function, all concepts introduced in this chapter. A context-free grammar will be defined using sets of terminals and non-terminals connected through production rules, which are themselves a kind of relation. Even the notion of a Turing machine deciding a language ultimately reduces to asking whether a particular string belongs to a particular set.
Students who take the time to feel comfortable with sets, relations, functions, alphabets, strings, and languages tend to find every later chapter noticeably easier, simply because the notation stops feeling unfamiliar. Instead of learning brand-new symbols in every chapter, they are simply seeing the same small set of mathematical ideas applied to increasingly interesting computational models.
| Mistake | Correct Understanding |
|---|---|
| Confusing a relation with a function. | Every function is a relation, but a relation only qualifies as a function if each input maps to exactly one output. |
| Assuming the empty string is the same as an empty language. | The empty string is a single string containing no symbols, while the empty language is a set containing no strings at all. |
| Thinking Σ* only includes short strings. | Σ* includes every possible string of every possible length over the alphabet, making it an infinite set. |
| Treating a language as something that must have finitely many strings. | Most languages studied in TOC contain infinitely many strings, since they are defined using a rule rather than a fixed list. |
This chapter introduced the mathematical vocabulary that the rest of Theory of Computation depends on. Sets provide a way to describe collections of symbols, states, and strings. Relations describe connections between elements, later reappearing as transition relations in automata. Functions add the restriction of determinism, forming the basis of deterministic machines. Alphabets and strings connect these abstract ideas to computation, and languages tie everything together by defining computational problems as simple set membership questions.
With this foundation in place, you are now ready to study the first true computational model of this course, finite automata, where these exact ideas of states, symbols, and transitions come together to build machines capable of recognizing entire families of languages.