Functions: What the Transition Function Actually Is
Chapter Five
Syllabus topic Module 1, "Mathematical Foundations (Sets, Relations, Functions, Proof Techniques)"
Pages 21 to 24 of 438
In one line
A function is a relation that gives exactly one answer for each input it is given.
In the wording a student can write in an examination: a function f from a set A to a set B is a relation from A to B in which every element of A appears as the first component of exactly one pair. A is the domain, B is the codomain, and we write f(a) for the unique element of B paired with a.
Why this subject needs functions
Because the definition of every machine in this book has a function in it, and the machine's whole behaviour is that function.
A finite automaton's transition function takes a state and a symbol and returns a state. A Mealy machine has a second function that takes a state and a symbol and returns an output symbol. A Turing machine's takes a state and a tape symbol and returns a state, a symbol and a direction. Learn the vocabulary here and those three definitions become three readings of the same sentence.
The definition, carefully
A function f from A to B is written f from A to B. For it to be a function, two things must hold for every element a of A:
At least one. There is some b in B with f(a) equal to b. Nothing in the domain is left without an answer.
At most one. There is only one such b. Nothing in the domain gets two answers.
Domain is A, the set the inputs come from. Codomain is B, the set the answers live in. Range or image is the part of B that is actually reached: the set of f(a) for all a in A. The range is a subset of the codomain and need not be all of it, and mixing the two up is the commonest error in this chapter.
Total and partial, which is the distinction that matters here
A function as defined above is called total: every element of the domain has an answer.
A partial function from A to B relaxes the first condition. Some elements of A may have no answer at all. It keeps the second condition: no element has two.
This is not a technicality in this subject; it is the difference between two ways of writing the same machine. A finite automaton is usually defined with a total transition function, so every state has a move on every symbol. In practice a machine is often drawn with some moves missing, meaning "if that happens, reject". Those two are the same machine in different clothes, and chapter 9 says how to turn one into the other: add a single extra state that is not final and whose every move returns to itself, then send all the missing moves there. It is called a dead state or a trap state, and the checker behind this book adds one automatically whenever it has to compare two machines.
Functions: What the Transition Function Actually Is
One to one, onto, and both
Three properties a function may have. All three are asked directly in examinations, and two of them are used in this book's proofs.
One to one, also called injective: different inputs always give different answers. Equivalently, if f(x) equals f(y) then x equals y. The function that doubles a whole number is one to one. The function that gives the length of a string is not, because ab and ba both give 2.
Onto, also called surjective: every element of the codomain is reached, so the range is the whole codomain. Length, from strings over {a} to whole numbers, is onto, because every number is the length of some string of a's. Doubling, from whole numbers to whole numbers, is not onto, because 3 is not double anything.
Bijective: both one to one and onto. A bijection pairs the two sets off exactly, one element of A for one element of B with nothing left over on either side.
Bijections are how the two sizes of infinity in chapter 7 are defined. A set is countable when there is a bijection between it and the whole numbers, that is, when its elements can be listed in one endless sequence with none repeated and none missed.
| Property | Means | Fails when |
|---|---|---|
| one to one | no two inputs share an answer | two different inputs give the same answer |
| onto | every possible answer is used | some element of the codomain is never produced |
| bijective | both | either of the above fails |
Composition
If f goes from A to B and g goes from B to C, then applying f and then g is a function from A to C, written g after f, with (g after f)(a) equal to g(f(a)).
Note the order: the one written on the right is applied first. It is written that way so that the notation matches the nesting of the brackets, and it catches students every time.
Composition is how the extended transition function of chapter 11 works. Running a machine on a string of length 5 is the transition function composed with itself five times, and the reason a machine's behaviour on a whole string is well defined is that composing functions gives a function.
Worked example
Let f be the function from strings over {a, b} to whole numbers that returns the number of a in the string.
Is it a function? Yes. Every string has a definite number of a in it, so there is at least one answer, and a string has only one count, so there is at most one.
Functions: What the Transition Function Actually Is
Domain, codomain, range. The domain is all strings over {a, b}. The codomain is the whole numbers. The range is also the whole numbers, because for any n the string a to the n has exactly n of them.
One to one? No. f(ab) and f(ba) are both 1, and ab is not ba.
Onto? Yes, by the reason just given.
Now a transition function, which is the one that matters. Take the three state machine that counts a modulo 3 from chapter 4. Its transition function delta has domain {q0, q1, q2} times {a, b} and codomain {q0, q1, q2}:
| C1 | State | a | b |
|---|---|---|---|
| start final | q0 | q1 | q0 |
| q1 | q2 | q1 | |
| q2 | q0 | q2 |
Accepts: ε, b, aaa, bbb, aaab
Rejects: a, aa, ab, aab
Every cell of C1 is filled, so delta is total, and every cell holds exactly one state, so it is a function rather than a relation. Six pairs in the domain, six entries in the table. That correspondence is worth noticing: a transition table is nothing but a function written out in full, and its number of cells is the size of the domain, which is the number of states multiplied by the number of symbols.
Is delta one to one? No, and it does not need to be: delta(q0, b) and delta(q1, a) are different inputs, and in this machine delta(q0, b) is q0 while delta(q1, a) is q2, but delta(q0, b) and delta(q0, b) aside, plenty of pairs collide in other machines. Nothing in the definition of an automaton requires the transition function to be one to one, and a machine whose transitions are one to one is a special and rather rare object.
What it does NOT mean
The codomain is not the range. The codomain is declared when the function is declared; the range is discovered by looking at what comes out. A function is onto exactly when they coincide.
A function is not required to be one to one. Most functions in this book are not.
A partial function is not a broken function. It is a perfectly respectable object and it is what a machine with missing moves has. What is not allowed, ever, is two answers for one input: that is a relation, and a machine whose transitions do that is nondeterministic, which is chapter 14.
f(a) is an element, f is a function. Writing "the function f(x)" is sloppy and it leads to confusion later when the same letter is used for a function on strings and a function on symbols.
Functions: What the Transition Function Actually Is
Quick revision
- A function from A to B pairs each element of A with exactly one element of B: at least one, at most
one.
- Domain A; codomain B; range is the part of B actually reached, and is a subset of the codomain.
- Total: every element of the domain has an answer. Partial: some may not, which is a machine with
missing moves, completed by adding a dead state.
- One to one: different inputs, different answers. Onto: every element of the codomain is reached.
Bijective: both, and bijections define countability.
- Composition g after f applies f first. The extended transition function is composition repeated.
- A transition table is a function written out in full; it has one cell per pair of state and symbol.
Test yourself
1. Give the domain, codomain and range of the transition function of a DFA with 4 states over {0, 1}. Domain: the 4 states times {0, 1}, so 8 pairs. Codomain: the 4 states. The range is whichever states actually appear in the table, which may be fewer than 4.
2. Is the reversal function on strings one to one? Onto? Bijective? All three. Two different strings have different reversals, every string is the reversal of something, namely its own reversal, and so reversal is a bijection from Sigma star to itself.
3. A machine is drawn with no move from state q on symbol b. Is its transition function total? What do you do about it? It is partial. Add a dead state that is not final, send the missing move there, and give the dead state a move to itself on every symbol. The language accepted does not change.
4. Explain why a transition function may not be a relation that gives two answers. Because a function must give at most one answer per input. A transition that offers two next states is a relation, and a machine built on one is nondeterministic, which is a different definition with a set as its codomain.
5. If f has 8 pairs in its domain and 4 elements in its codomain, can f be one to one? No. Eight inputs cannot have eight distinct answers among four possible answers, so at least two inputs must share one. This is the pigeonhole principle of chapter 6.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.