11
$\begingroup$

If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?

$\endgroup$
  • $\begingroup$ I'd call a nondeterministic automaton that never has more than one transition on the same state and input symbol deterministic. It just doesn't fit the DFA definition. $\endgroup$ – reinierpost Jun 10 '13 at 10:30
  • 1
    $\begingroup$ If a DFA's rules are arranged so that it can never be in state q when the symbol on the tape is a, do we really need to define δ(q,a)? $\endgroup$ – Peter Shor Jun 10 '13 at 12:41
  • 4
    $\begingroup$ The answer is clearly that it depends on how one defines "deterministic finite automaton". As such, I'm not sure that this question is entirely constructive, as there's not a universally accepted correct answer - i.e., this question solicits opinion and debate. $\endgroup$ – Patrick87 Jun 10 '13 at 15:15
  • 1
    $\begingroup$ If $\delta$ is supposed to be a function, it has to be defined for all pairs $q, a$. $\endgroup$ – vonbrand Sep 5 '15 at 14:19
  • $\begingroup$ In my notion of a DFA, this is an "abort" condition, or if you prefer an implicit jump to a "reject" state. $\endgroup$ – Yves Daoust Dec 5 '15 at 14:42
21
$\begingroup$

You seem to have stumbled on a contentious issue. Apparently computer scientists like to argue. I certainly like to argue, so here goes!

My answer is an unequivocal: No. A deterministic finite automata does not need a transition from every state for every symbol. The meaning when $\delta(q,a)$ does not exist is simply that the DFA does not accept the input string.

While you can create a definition of DFA that requires that $\delta(q,a)$ does exist, it is simply not the case that a missing transition makes the resulting structure (whatever you call it) in any way nondeterministic as many of the commenters are claiming. If you are taking a course on automata theory then the next topic will be context-free languages and push-down automata where the distinction between nondeterministic and deterministic automata is crtical, and you need to use the correct definition of non-determinism.

Non-determinism is associated with having more than one legal transition.

I think we all agree with the following Wikipedia definition (which I'll show in just a second is slightly ambiguous):

A deterministic finite automaton $M$ is a 5-tuple, ($Q$, $\Sigma$, $\delta$, $q_0$, $F$), consisting of

  1. a finite set of states ($Q$)
  2. a finite set of input symbols called the alphabet ($\Sigma$)
  3. a transition function ($\delta : Q \times \Sigma \rightarrow Q$)
  4. a start state ($q_0 \in Q)$
  5. a set of accept states ($F \subseteq Q$).

Let $w = a_1 a_2 \cdots a_n$ be a string over the alphabet $\Sigma$. The automaton $M$ accepts the string $w$ if a sequence of states, $r_0, r_1, \ldots, r_n$, exists in $Q$ with the following conditions:

  1. $r_0 = q_0$
  2. $r_{i+1} = \delta(r_i, a_{i+1})$, for $i = 0, \ldots, n−1$
  3. $r_n \in F$.

The ambiguity, and the controversy is over the defintion of the transition function, $\delta$ (number "3" in the first bulleted list.) We all agree that what differentiates a DFA from an NFA is that $\delta$ is a function rather than a relation. But is $\delta$ a partial function or a total function?

The definition of the DFA works just fine if $\delta$ is a partial function. Given an input string, if you reach a state $q_i$ with an input symbol $a_j$ where there is no next state then the automata simply does not accept.

Moreover when you extend this definition to create the definition of push-down automata it will be the case that you must make the distinction that push-down automata with transition functions that are partial functions are classified as deterministic, not nondeterministic.

If the partial function bothers you then here is a trivial transformation that makes $\delta$ a total function. (This transformation is not like the subset construction algorithm, it adds at most O(1) states, is linear in the original number of states, and can be extended to work with PDAs. None of those facts is true of the subset construction algorithm.)

  1. add a state $q_{\mathrm{error}}$
  2. for every pair $(q_i, s_j)$ where $\delta$ is undefined, define $\delta(q_i, s_j) = q_{\mathrm{error}}$.

This automata has a $\delta$ that is a total function and accepts and rejects exactly the same set of states that your original automata accepted and rejected.

Edit, January 2019

Commenter @Alex Smart rightly critiques me for neither giving references, nor for explaining why we should care. So here goes:

The reason we care about the exact definition of determinism vs non-determinism, is that some classes of non-deterministic automata are more powerful than their deterministic cousins, and some classes of non-deterministic automata are not more powerful than their deterministic cousins. For finite automata and Turing machines the deterministic and non-deterministic variants are of equivalent power. For pushdown automata there are languages where the distinction is important: There are NPDA that accept the language, and no DPDA accepts the language. For the linear bounded automata the question is (or was last time I checked) open. The increase of power of NPDA over DPDA comes from allowing multiple transitions, not from turning the transition function from a total function to a partial function.

Books from the compiler community:

Aho and Ullman, Principles of Compiler Design, 1977: First defines NFA (page 88) with a transition relation, then (p. 90-91):

We say a finite automaton is deterministic if 1. It has no transitions on input $\epsilon$. 2. For each state $s$ and input symbol $a$, there is at most one edge labeled $a$ leaving $s$.

Aho, Sethi, and Ullman, Compilers, principles, tecniques, and tools, 1988 reprint, is similar, it first defines NFA with a transition relation, then (p. 115-116):

A deterministic finite automata (DFA, for short) is a special case of a non-deterministic finitie automaton in which ... there is at most one edge labeled $a$ leaving $s$.

(Note that in the comments @Alex Smart says, "the dragon specifically mentions that the function is total." I assume he is talking about the later edition with co-author Lam, which I don't have access to at the moment.)

Appel, Modern Compiler Implementation in Java, 1988 (p. 22):

In a deterministic finite automaton (DFA), no two edges leaving from the same state are labeled with the same symbol.

Appel then goes on to explain that when using DFA to recognize longest matches we explicitly make use of the missing transitions to decide when to stop (p. 23):

when a dead state (a nonfinal state with no output transitions) is reached, the variables [which record the longest match we've seen so far] tell what token was matched, and where it ended.

Books from the switching-theory community:

Kohavi, Switching and Finite Automata Theory, 2/e, 1978, p. 611 says:

Because a state diagram describes a deterministic machine, the next state transition must be determined uniquely by the present state and the presently scanned input symbol.

I would typically interpret uniquely to mean "exactly one", not "no more than one". (I.e., Kohavi seems to be saying that determinism requires a total function)

Books from the theory-of-computation community:

Here it seems to be more common to define DFAs before NFAs, and require DFAs to have a total transition function, but then define NPDAs before DPDAs, and define "determinism" as being a restriction of the transition relation to having no-more-than-one entry for each state/symbol pair.

This is true of Hopcroft and Ullman, 1979, Lewis and Papadimitriou, 1981, and, especially of Sipser, 2006, who uses the definition of DFA pedagogically to introduce precise formal definitions, and explain their importance and explicitly says (p.36):

the transition function, $\delta$, specifies exactly one next state for each possible combination of a state and an input symbol.

This seems to follow the historical development. Deterministic finite automata were introduced in the 40s and 50s. Non-determinisitc finite automata were introduced in the paper by Rabin and Scott, "Finite automata and their decision problems, IBM J. Rsrch and Dvpt, 3(2):114-125, 1959. Following earlier authors, Rabin and Scott define deterministic finite automata (which they call ordinary automata) as having a transition function "defined on the Cartesian product $s\times\Sigma$ of all pairs of states and symbols." (Which I would interpret as meaning a total function).

Interestingly Rabin and Scott, also define non-deterministic finite automata in terms of a total function! Page 120, Definition 9:

A nondeterministic (finite) automaton ... is a system where ... $M$ is a function[!] of $S\times\Sigma$ with values in the set of all subsets of $S$.

That is: the transition function being total does not make the system deterministic!

Sipser 2006 follows Rabin and Scott and uses a total transition function from states/symbols to the power set of states for his definitions of non-deterministic finite automata, non-deterministic PDA, and non-deterministic Turing Machines, but skips the topic of deterministic PDA.

Both Hopcroft and Ullman, 1979, and Lewis and Papadimitriou, 1981 use partial functions in their definitions of deterministic PDAs. They first define NPDAs with a transition relation, and then when they get to PDAs, Lewis and Papadimitriou say (p. 135),

A pushdown automaton is deterministic, intuitively speaking, if there is at most one transition applicable to each configuration.

While Hopcroft and Ullman say (p. 112):

The PDA ... is deterministic in the sense that at most one move is possible from any ID.

$\endgroup$
  • $\begingroup$ You're making the automaton deterministic when you add the state $q_{error}$. We can always convert an NFA to a DFA. You're right about one thing: partial function or total function? Most mathematicians would mean total function when they say function. They say partial function when they do not mean total function. That's why I think we need to include formal definition to the question. $\endgroup$ – scaaahu Jun 10 '13 at 12:43
  • 2
    $\begingroup$ The partial function version is the one given in Hopcroft and Ullman, if that makes a difference. So the idea that a partial function is inherently nondeterministic is by no means standard. $\endgroup$ – jmite Jun 10 '13 at 16:35
  • 1
    $\begingroup$ @jmite It's not that partial functions imply nondeterminism; it's that total functions imply determinism that makes total functions the better choice. Of course, it's a more or less arbitrary matter of the definitions you're using. $\endgroup$ – Patrick87 Jun 10 '13 at 20:10
  • 3
    $\begingroup$ It is called Incomplete Deterministic Finite Automaton when $\delta$ is a partial function. $\endgroup$ – scaaahu Jun 11 '13 at 8:25
  • 1
    $\begingroup$ As you have shown, the partial function version has an easy translation to total function version, and as far as I can see you gain absolutely nothing, pedagogically or otherwise by allowing the translation function to be partial. The dragon specifically mentions that the function is total. Why in the world are we creating an argument about something that has been defined clearly in a standard textbook that most people follow when there is absolutely nothing to gain out of choosing a non-standard definition? $\endgroup$ – Alex Smart Dec 26 '18 at 8:23
8
$\begingroup$

As scaaahu notes in the comments, by a common definition, a deterministic finite automaton (DFA) must have a transition from every state on every alphabet symbol, i.e. the transition function $\delta(q,a)$ is defined for all $q \in Q$ and $a\in \Sigma$ where $Q$ is the set of states and $\Sigma$ is the alphabet.

Once you start leaving out transitions, or adding multiple transitions on the same symbol from the same state you have a non-deterministic finite automaton (NFA). NFAs also have an additional possibility, $\varepsilon$-transitions, where they can move from one state to another without reading a symbol from the input.

In terms of computability, NFAs are equivalent to DFAs - there's an algorithm to convert from an NFA to a DFA, and a DFA is just trivially an NFA that doesn't use any nondeterminism, so they both define the set of regular languages.

$\endgroup$
  • 2
    $\begingroup$ This depends on the definition; there are several which are equivalent in power. $\endgroup$ – Raphael Jun 10 '13 at 11:17
  • 3
    $\begingroup$ +1 Best to stick to this definition, IMHO, as everybody would agree that a FA that defines exactly one transition for each (state, symbol) pair constitutes a valid DFA. $\endgroup$ – Patrick87 Jun 10 '13 at 15:19
  • 1
    $\begingroup$ And this definition is flat out wrong when you try to extend it to deciding whether a context free language is deterministic or nondeterministic. A pushdown automata with missing transitions can always be transformed into a pushdown automata with exactly one transition per state/input symbol/stack symbol. A nondeterministic pushdown automata with multiple possible transitions per state/input symbol/stack symbol can not necessarily be transformed into a deterministic pushdown automata. (For example: in the case that the recognized language is nondeterministic context free.) $\endgroup$ – Wandering Logic Jun 10 '13 at 19:56
  • 2
    $\begingroup$ @jmite Just define trim automata independently of DFAs. I think it's much more important that minimal DFAs have the right number of states according to the Myhill- Nerode theorem, which you only get with dead states. $\endgroup$ – Patrick87 Jun 11 '13 at 13:08
  • 4
    $\begingroup$ This is getting silly. Partial functions never create nondeterminism while $\epsilon$ transitions create nondeterminism in all but very special cases (e.g., every state $\epsilon$ transitions to itself, or the states that have $\epsilon$ transitions have no transitions on any regular symbols (i.e. the states have transition functions that are partial!)) I'm talking about the tightest bounds we can provide on worst-case behavior across all inputs, not special cases (like your "sometimes linear" sorts.) $\endgroup$ – Wandering Logic Jun 11 '13 at 16:07
5
$\begingroup$

There are definitions of DFA along the lines of

If $A$ is NFA and $|\delta(q,a)| \leq 1$ for all $q$ and $a$ (and if $\delta(q,\varepsilon) \neq \emptyset$, then $\delta(q,a) = \emptyset$ for all $a \in \Sigma$) then $A$ is DFA.

In that case, you don't need all transitions. If the automaton does not have a transition fitting the next input symbol, it rejects.

It is a nice exercise to show that both definitions are equivalent in terms of which languages can be accepted.

$\endgroup$
  • $\begingroup$ I think the OP's question needs to be edited to include the formal definition of DFA. $\endgroup$ – scaaahu Jun 10 '13 at 12:10
0
$\begingroup$

In the definition of DFA, every states should have all the alphabet that in £. For an example if the £={a,b,c} and Q={q0,q1,q2} , all of this states should have the all a,b,c symbols that transition to other state or same state.

$\endgroup$
  • 1
    $\begingroup$ What's the difference from existing answers so that you post a new answer? $\endgroup$ – xskxzr Dec 26 '18 at 10:45
0
$\begingroup$

The simplest answer for this is, you add dead state for left symbol. As in conversion from NFA to DFA, we get Φ transion for some symbols, which signifies we create Dead state for it.

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