2
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ "delta from cue cross sigma to cue"? $\endgroup$ – JeffE Feb 14 '13 at 13:06
  • $\begingroup$ Lol, true, but too literal and vague. $\endgroup$ – trusktr Feb 15 '13 at 6:32
5
$\begingroup$

$\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".

$\endgroup$
4
$\begingroup$

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\}.$$

$\endgroup$
1
$\begingroup$

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:

enter image description here

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.