the Cartesian product
/ kar-TEE-zhuhn /
The Cartesian product of two sets A and B is the set of all ordered pairs you can make by taking one element from A and one from B. Picture a grid: A labels the rows, B labels the columns, and every cell of the grid is one pair. A chessboard is a small Cartesian product — files {a,...,h} crossed with ranks {1,...,8} give the 64 squares, each named by a (file, rank) pair like (e, 4). Unlike a set, a pair is ordered: (e, 4) and (4, e) are different things.
We write it A × B = {(x, y) : x ∈ A and y ∈ B}, where (x, y) is an ordered pair (first coordinate x, second coordinate y). If A = {0, 1} and B = {a, b, c}, then A × B has 2 × 3 = 6 pairs: (0,a), (0,b), (0,c), (1,a), (1,b), (1,c). In general the size multiplies: |A × B| = |A| × |B|, which is exactly where the name 'product' comes from. You can extend this to three or more sets to get ordered triples and longer tuples, which is how the formal definition of an automaton is packaged as a tuple.
This operation is everywhere in the theory. A transition function of a DFA takes a (state, symbol) pair to a next state, so its domain is the Cartesian product (set of states) × (alphabet). The product construction, used to prove that regular languages are closed under intersection, runs two automata at once by making its state set the Cartesian product of the two original state sets — a pair of states remembers where each machine is. And a relation, defined next, is simply a subset of a Cartesian product.
If Q = {q0, q1} is a DFA's states and Σ = {a, b} its alphabet, then Q × Σ = {(q0,a), (q0,b), (q1,a), (q1,b)} — the four (state, symbol) inputs the transition function δ (delta) must answer for.
The domain of a DFA transition function is the Cartesian product of states and alphabet.
Pairs are ordered and the product is generally not commutative: A × B and B × A contain different pairs (unless A = B). Do not confuse the pair (a, b) with the two-element set {a, b}.