How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite acceptor)?

Question

How do you say $\delta\colon Q \times \Sigma \to Q$ in English? Describing what $\times$" and $\to$ mean would also help.

Answer 1

$\delta$ is a function which takes a current state and a letter from the alphabet as arguments and produces next state.

It might be easier to understand when you realize that it is just a function that takes a pair, for instance $(q_0, a)$ where $q_0 \in Q$ is a state and $a \in \Sigma$ is a letter in the alphabet, and $\delta(q_0, a) = q_1$ means that if in state $q_0$ you read an 'a', proceed to state $q_1$.

It is the definition of a transition function which is used for example in Turing machines.

$\times$ means Cartesian product and $\to$ means "produces" or "maps to".

Answer 2

The statement $\delta\colon Q \times \Sigma \to Q$ translates to: The function $\delta$ assigns every pair formed by an element of $Q$ and an element of $\Sigma$, an element of $Q$. Instead of "assigns" you could also say "maps to". I assume that $\delta$ is the transition function for a finite automaton. Then you can say, $\delta$ assigns every pair, formed by a state and character a new state.

Here is a short explanation how to interpret the symbols you are asking for:

• In mathematics we often don't want just name a function $f$, we also want to say something about it by defining its domain $I$ and codomain $O$. To use an algorithmic analogue, the domain represents all possible inputs, and the codomain all possible outputs. (Of course a function can describe more complicated things than an algorithm can do.) If we want to denote the function we write $f\colon I \to O$.

• The $\times$ operator denotes the cartesian product. Simply speaking it is used to define tuples. For example, if you want to make a mathematical statement about pairs (with a distinguished first and second entry) you write $A\times B$ for the set of pairs, where the first entry is taken form $A$ and the second entry is taken from $B$. Analogously you can define larger tuples. The formal definition is $$ A_1 \times A_2 \times \cdots \times A_n := \{(a_1,a_2,\ldots,a_n)\mid a_1\in A_1,\ldots ,a_n\in A_n\}.$$

Answer 3

The statement $\delta: Q\times\Sigma\mapsto Q$ can be read as follows: given a state and a symbol the automaton moves to another state (possibly the state it was in). The $\times$ is like "and" in English meaning that you can pick any element from the first set $Q$ and any element from the second set $\Sigma$. More precisely, it's called the Cartesian product of the sets $Q$ and $\Sigma$. You can think of it as an operator that takes sets and outputs a new set that is the combinations of elements from $Q$ and $\Sigma$. Here is a simple example:

$Q=\{q_0,q_1\}$

$\Sigma=\{a,b\}$

$Q\times\Sigma=\{(q_0,a),(q_0,b),(q_1,a),(q_1,b)\}$

The symbol $\mapsto$ assigns elements taken from the right set to elements taken from the left set. You can think of it as a 2-column table, here is an example:

$(q_0,a)$ maps to $q_1$ and so on.