In very simple terms please, all resources I'm finding are talking about tuples and stuff and I just need a simple explanation that I can remember easily because I keep getting them mixed up.
$\begingroup$
$\endgroup$
2
-
6$\begingroup$ N = nondeterministic, D = deterministic. What aspects are you confusing about automata? Ignore the tuples: they're a low-level representation meant for proving things and making precise statements, not for human intuition. $\endgroup$– user14972Nov 12, 2013 at 13:16
-
$\begingroup$ Pretty easy illustration: youtube.com/watch?v=Gt8TavZVcX4 $\endgroup$– cevingFeb 25 at 9:41
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
6
Each input to a DFA or NFA affects the state of the automaton: if it was in state $q$ immediately before the input, either it will be in some state $q'$ after the input, or the input will cause it to choke. (Note that $q'$ may be the same as $q$.) Suppose that we have an automaton in a state $q$. The difference in behavior between a DFA and an NFA is this:
If it’s a DFA, each possible input determines the resulting state $q'$ uniquely. Every input causes a state change, and the new state is completely determined by the input. Moreover, the automaton can change state only after reading an input.
If it’s an NFA, some inputs may allow a choice of resulting states, and some may cause the automaton to choke, because there is no new state corresponding to that input. Moreover, the automaton may be constructed so that it can change state to some new state $q'$ without reading any input at all.
As a consequence of this difference in behavior, DFA’s and NFA’s differ in another very important respect.
If you start a DFA in its initial state and input some word $w$, the state $q$ in which the DFA ends up is completely determined by $w$: inputting $w$ to the DFA will always cause it to end up in state $q$. This is what is meant by calling it deterministic.
If you start an NFA in its initial state and input some word $w$, there may be several possible states in which it can end up, since some of the inputs along the way may have allowed a choice of state changes. Consequently, you can’t predict from $w$ alone in exactly which state the automaton will finish; this is what is meant by calling it nondeterministic. (And it’s actually a little worse than I’ve indicated, since an NFA is also allowed to have more than one initial state.)
Finally, these differences affect how we determine what words are accepted (or recognized) by an automaton.
If it’s a DFA, we know that each word completely determines the final state of the automaton, and we say that the word is accepted if that state is an acceptor state.
If it’s an NFA, there might be several possible final states that could result from reading a given word; as long as at least one of them is an acceptor state, we say that the automaton accepts the word.
What I’ve described informally is the view of an NFA that makes it look most like a DFA and that I think best explains why it’s called nondeterministic. There is, however, another way of looking at NFAs: it’s also possible to think of an NFA as being in multiple states at once, as if it were making all possible choices at each input. If you think of it in those terms, you can say that it accepts a word provided that at least one of the states in which it ends up after reading that word is an acceptor state. This point of view is perhaps most useful for understanding the algorithm used to turn an NFA into an equivalent DFA.
answered Nov 12, 2013 at 13:51
-
$\begingroup$ Thanks for the detailed reply. You say that a non-deterministic finite automation can change state without reading any input at all, does that mean that a deterministic finite automation HAS TO have every possible transition at every state? (Because I'm assuming they're opposite). $\endgroup$– OgenNov 13, 2013 at 2:38
-
1$\begingroup$ @Clay: Yes, at each state a DFA must have a transition for each symbol in the input alphabet. It cannot have any $\epsilon$ transition, however (transitions with no input). $\endgroup$ Nov 13, 2013 at 10:51
-
3$\begingroup$ Can you clarify what you mean by choke the NFA. Do you mean link to the same state, or unsuccessful completion of the NFA? $\endgroup$– Andrew SMar 15, 2014 at 6:32
-
$\begingroup$ I think all that is missing on this answer is Construction Complexity and Execution Complexity comparison. Nicely written. $\endgroup$– FawarMar 5, 2015 at 17:08
-
$\begingroup$ DFAs can be defined with partial transition function as well. If a state does not have a transition for a particular letter, the word is rejected. It’s simply syntactic sugar for a sink state where you can go after reading the missing letter. It doesn’t have to do with nondeterminism. Specularly, at times you may want to restrict to total NFAs for simplicity. $\endgroup$ Jun 10, 2019 at 12:20
$\begingroup$
$\endgroup$
1
Automata are abstract machines that have a finite set of states. Given some input, they transition from state to state. You can think of them sort of like flowcharts.
An NFA is a Nondeterministic Finite Automaton. Nondeterministic means it can transition to, and be in, multiple states at once (i.e. for some given input).
A DFA is a Deterministic Finite Automaton. Deterministic means that it can only be in, and transition to, one state at a time (i.e. for some given input).
The major important difference is that an NFA is usually much more efficient.
-
13$\begingroup$ "NFA is usually much more efficient." In what way is it more efficient? Construction time? Execution time? Space used? Why? $\endgroup$ Aug 24, 2015 at 4:53
$\begingroup$
$\endgroup$
For Every symbol of the alphabet, there is only one state transition in DFA.
We do not need to specify how does the NFA react according to some symbol.
DFA cannot use Empty String transition.
NFA can use Empty String transition.
DFA can be understood as one machine.
NFA can be understood as multiple little machines computing at the same time.
DFA will reject the string if it end at other than accepting state.
If all of the branches of NFA dies or rejects the string, we can say that NFA reject the string.
$\begingroup$
$\endgroup$
1.“DFA” stands for “Deterministic Finite Automata”, while “NFA” stands for “Nondeterministic Finite Automata.”
2.Both are transition functions of automata. In DFA the next possible state is distinctly a set, while in NFA each pair of state and input symbol can have many possible next states.
3.NFA can use empty string transition, while DFA cannot use empty string transition.
4.NFA is easier to construct, while it is more difficult to construct DFA.
5.Backtracking is allowed in DFA, while in NFA it may or may not be allowed.
6.DFA requires more space, while NFA requires less space.
7.While DFA can be understood as one machine and a DFA machine can be constructed for every input and output, NFA can be understood as several little machines that compute together, and there is no possibility of constructing an NFA machine for every input and output.
