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

Question

How do you say δ: Q × Σ → Q in English? Describing what × and → mean would also help.

Chard

the A in DFA acronym stands for Automaton – Ragamuffin

This is a CS theory question, and thus belongs on cs.stackexchange.com (I don't think it's at the level where it would belong on cstheory since this is pretty basic). – Panicle

Answer 1

δ is like a mathematical function called the transition function . Something like.

z = f(x, y) 

A function in mathematical defines mapping of elements in one set to another set. In function set of input arguments are called Domain of a function and output is the rage.

[ANSWER]   

In expression "δ:Q×Σ → Q",

× means Cartesian product (that is a set), and → is a mapping.
"δ:Q×Σ → Q" says δ is a transition function that defined mapping from Q×Σ to Q. Where, Domain of δ is Q × Σ and Range is Q.

Note: Cartesian Product itself a mathematical that all possible order pair (mapping) between two sets.

You can also say:

δ is a transition function that defined mapping between(or say associates) Cartesian product of set of statesQ and language symbolsΣ into set of stateQ. This is abbreviated by δ: Q×Σ → Q

Here, Q is finite set of states and Σ is a finite set of language symbols.

Additionally in any automated you can represent transition function in tree ways.
1. Transition Table
2. Transition graph or say state diagram.
3. Transition function: a finite set of mapping rules. e.g. {δ(q0, a) → q1, δ(q1, a) → q2}
_{All for same purpose define maping}

In DFA. δ:Q×Σ → Q can also be written like δ(Q,Σ) → Q It's similar to function. In δ function two input arguments are state Q and a language symbol Σ and returned value is Q.

What is meaning of δ(Q,Σ) → Q

Suppose in your set of transition function δ you have an element δ(q0, a) → q1 this means. If the present state is q0 then by consuming a symbol you can shift to state q1. And the state-diagram for δ(q0, a) → q1:

(q0)---a---►(q1)  

and transition table is:

+----+----+
|Q\Σ | a  |
+----+----+
| q0 | q1 |
+----+----+

and all defines mapping (q0, a) to (q1).

Some authors write δ ⊆ Q×Σ → Q in formal DFA definition that means δ is a Partial function (not defined on full Domain Q×Σ). We can always defined δ on the full domain that is required sometime for example to find complement DFA. Here(Complement DFA), I wrote two DFAs for the same language one is partial DFA other is complement DFA.

Slapup

I am thinking to prepare for GATE. Need some text book suggestions, would you help me ? – Doings

@ArupRakshit for toc I suggested some books here just read books and pick last 10-15 years gate papers. – Slapup

Can you just suggest text books for the subjects.. From which college you did M.Tech ? – Doings

@ArupRakshit Not for each subject but on some subjects I am pretty confident – Slapup

Answer 2

Sorry if the terms are not exactly right (in English). I've studies automaton theory about 3 or 4 years ago in a different language so the terms might not be exactly accurate.

δ is like a partial function with two arguments which takes as an input a state (that automaton's state; element of Q) and an "input action" (element of Σ which is the alphabet accepted by the automaton*) and produces the new state the automaton should have after providing it the input action.

Basically this can be read as:

delta transition function defined on the Q set of automaton states and sigma alphabet

The × in the formula represents a Cartesian product of the states and actions sets, while the → represents that what is returned by the function belongs to the set following it (in your case, Q).

*not to be confused with the language accepted by the automaton which would be all the "input actions" sequences that have valid transitions (i.e. δ(stateX, input) is defined) and lead the automaton into a final "acceptable" state.

Vitality

If you spot something that needs correcting or need more info, post a comment :) – Vitality

Why is δ a partial function? If it was an NFA, I'd agree (sort of, it would be a relation then), but doesn't a DFA force every combination of "input state" and "input action" in Σ to have a defined output state? I thought that if a particular transition was not defined, then it would by necessity be only an NFA and not a DFA. – Hekking

If δ is a partial function the DFA is and incomplete DFA. If it is a complete function, then the DFA is complete. The difference between NFAs (afaik) is that in the case of a NFA, the δ functions produces values of subsets of Q and, when providing input to the automaton, any of the elements in that output subset can be chosen as the next state (non-deterministic). Usually all elements are considered the next state and an extended δ is defined as δ:P(Q)×Σ→P(Q), P(Q) being the set of subsets of Q. cgi.csc.liv.ac.uk/~pwg/COMP218/Notes/note1up2.pdf – Vitality

@DPenner δ ⊆ Q×Σ → Q means δ is subset of Q×Σ → Q mapping and partial function read my answer. for example: read this Complement DFA – Slapup

The OP doesn't say ⊆ or P(Q) though, just a simple δ:Q×Σ→Q which leads me to believe their definition is that of a complete function. I googled it, and here it implies (in Q. 21) that an incomplete DFA is a type of NFA. However, it doesn't look like theres a 100% consensus on the subject. Makes no real practical difference though as its trivial to convert from an incomplete DFA to a complete one. Thanks, for the info though, I've never heard of it before! – Hekking

@DPenner Yes that I mean to say δ:Q×Σ→Q means δ is complete and δ ⊆ Q×Σ → Q means δ is partial – Slapup

Answer 3

Delta from cue cross sigma to cue

or

The transition function, delta, which maps ordered pairs of states and input symbols, cue cross sigma, to states, cue.

Cirillo

Why use "eeh" for Σ instead of "Sigma"? – Byte

@MikeSamuel Good point, not entirely sure why I wrote "eeh". Of course it's "Sigma". I suppose I had in my mind something I read recently where they didn't use standard notation. Amending... – Cirillo

Answer 4

It's easy to cite from Wikipedia:

δ is the state transition table: I would read "×" as table, and "→" as entries in that table.

Then in natural language: specify which state (element of Q) will result from the machine being in a specified state and seeing a defined symbol (element of Σ).

Ragamuffin

At your wiki page: a transition function (δ : Q × Σ → Q), you are given link to function-wiki from there × is for X × Y cartesian product and → for mapping. – Slapup