Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
4  
"delta from cue cross sigma to cue"? –  JeffE Feb 14 '13 at 13:06
    
Lol, true, but too literal and vague. –  trusktr Feb 15 '13 at 6:32
add comment

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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