13
$\begingroup$

Tomorrow is my presentation and I want to clear my concepts…

I've read that in DFA, "For each state, transition on all possible symbols (alphabet) should be defined."

Is for each state, defining transition on all possible symbols mandatory in DFA? If its not, then please give any examples?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to CS.SE! We prefer that you ask only one question per post. This looks like two separate questions. It would be better to post the second one (about NFA's) separately. Also, have you searched thoroughly on this site, and checked the formal definition in your textbook? If not, you should do that before asking; and you should show us in the question what you found when you did that. $\endgroup$
    – D.W. ♦
    Commented Nov 23, 2016 at 19:24
  • $\begingroup$ Thank you for warm welcome, I did actually searched on this site and on google as well, but I am getting contrary views which is actually confusing me.. $\endgroup$
    – HQuser
    Commented Nov 23, 2016 at 19:39
  • $\begingroup$ The second question has been removed, but you can find it in the edit history and post it separately as a separate question using the 'Ask Question' button in the upper-right. However, before asking, please do make sure to do the research suggested and tell us in the question what research you've done, including telling us which textbook(s) you've read. As far as this question, you could still edit this question to address the feedback I gave here by looking up the formal definition in your textbook, including it in the question, and showing your interpretation of that definition. $\endgroup$
    – D.W. ♦
    Commented Nov 23, 2016 at 20:51
  • 9
    $\begingroup$ Anyway, this seems covered by cs.stackexchange.com/q/12587/755. Community votes, please: is this a duplicate? $\endgroup$
    – D.W. ♦
    Commented Nov 23, 2016 at 20:54
  • 1
    $\begingroup$ I don't really understand your question. It seems to be "I've read that the definition is X. Is the definition X?" $\endgroup$
    – David Richerby
    Commented Nov 24, 2016 at 0:24

3 Answers 3

Reset to default
12
$\begingroup$

A DFA is specified by the following data:

  • An alphabet $\Sigma$.
  • A set of states $Q$.
  • An initial state $q_0 \in Q$.
  • A set of final states $F \subseteq Q$.
  • A transition function $\delta\colon Q \times \Sigma \to Q$.

As you can see from the signature of $\delta$, it specifies a transition at every state for every symbol.

Improve this answer
$\endgroup$
3
  • 8
    $\begingroup$ Except that DFAs are sometimes defined with a partial transition function. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Nov 23, 2016 at 21:31
  • 6
    $\begingroup$ You're right, there is no "official" definition of a DFA. But the OP's reading betrays influence of this particular definition. $\endgroup$
    – Yuval Filmus
    Commented Nov 23, 2016 at 21:37
  • $\begingroup$ Should explicitly say that the transition function is total. $\endgroup$
    – Ryan Dougherty
    Commented Nov 24, 2016 at 17:51
24
$\begingroup$

Suppose a DFA was allowed to have missing transitions. What happens if you encounter a symbol which has no transtion defined for it? The result is undefined. That would seem to violate the "deterministic" characteristic of a DFA.

However, it's trivial to transform such an incomplete DFA into a complete DFA. Simply add a new state, illegal, and map any undefined transitions to the illegal state. Finally, add transitions for every symbol from the illegal state back to itself. This illegal state is often called a sink state, because once data falls into the sink there's no way to get out.

So, from a practical perspective, it's kind of moot, as long as you have a well-defined way to handle missing transitions.

Improve this answer
$\endgroup$
4
  • 10
    $\begingroup$ Careful: A transition being undefined doesn't make the automaton non-deterministic, just incomplete. There are some definitions of DFA that allow such undefined transitions precisely because it's trivial to complete it systematically. $\endgroup$
    – Darkhogg
    Commented Nov 23, 2016 at 22:58
  • 1
    $\begingroup$ @Darkhogg, I don't necessarily disagree, but wouldn't determinism of an incomplete DFA be dependent on how a particular implementation handles these undefined / missing transitions? And wouldn't such an implementation implicitly complete the DFA? $\endgroup$
    – Nathan Davis
    Commented Nov 24, 2016 at 1:08
  • 1
    $\begingroup$ No, it doesn't depend on the implementation, it depends on the definition. If you define DFAs as having a total transition function and then use a partial function sure, you have undefined behaviour and might end up with non-determinism, but that's not a given. However, DFAs are sometimes explicitly defined to use a partial function, and when encountering an undefined transition the behaviour is "not accept", period. No non-determinism or anything funky there, for any implementation because the result is defined even if the transition is not. $\endgroup$
    – Darkhogg
    Commented Nov 24, 2016 at 8:50
  • $\begingroup$ BTW: you can also make the converse transformation. Take a "total automaton" and remove a sink state to obtain a "incomplete automaton". In the end the only difference is that a total automaton is always able to read a word to the end, and after that it decides whether it accepts the word or not, while a partial automaton is able to reject some words before reading all of their characters. $\endgroup$
    – Bakuriu
    Commented Nov 24, 2016 at 13:37
5
$\begingroup$

A DFA is often defined as a restricted type of NFA. If $\Sigma$ is the input alphabet and $Q$ is the set of states, the transition structure of an NFA is specified as either a relation $\rho \subseteq Q \times \Sigma \times Q$, or as a function $\delta : (Q \times \Sigma) \to 2^Q$. If we adopt the latter definition, then we can say that an NFA is deterministic if $|\delta(q,\sigma)| \leq 1$ for all $q\in Q$ and $\sigma \in \Sigma$, and complete if $\delta(q,\sigma) \neq \emptyset$, again, for all $q \in Q$ and $\sigma \in \Sigma$.

A word is accepted by an NFA if it has an accepting run. A deterministic automaton has at most one run. A complete automaton has at least one run.

Some authors define trim automata as those in which each state is on some path from an initial state to a final state. For certain languages, you cannot have automata that are both trim and complete. In those cases, it is convenient to keep the completeness requirement out of the definition of deterministic automaton.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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