I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple and epsilon transitions, they are defined which means that the machine is deterministic for those transitions. Which means it's deterministic.
$\begingroup$
$\endgroup$
9
-
14$\begingroup$ Nondeterministic as used in theoretical computer science is different from random. $\endgroup$– adrianNCommented Sep 6, 2017 at 13:32
-
11$\begingroup$ It's the choice between the transitions that is nondeterministic. $\endgroup$– reinierpostCommented Sep 6, 2017 at 15:35
-
$\begingroup$ What is a NFA? (For the unenlightened among us) $\endgroup$– DarcyThomasCommented Sep 7, 2017 at 3:42
-
$\begingroup$ @DarcyThomas, the first introduction I had was swtch.com/~rsc/regexp/regexp1.html. It's a good read—it's not the purpose of the article to introduce NFAs, but it does a good job of doing so in discussion of regular expressions. $\endgroup$– WildcardCommented Sep 7, 2017 at 4:24
-
1$\begingroup$ @Trilarion cs.stackexchange.com/questions/5008/… $\endgroup$– adrianNCommented Sep 7, 2017 at 9:51
|
Show 4 more comments
9 Answers
$\begingroup$
$\endgroup$
7
"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times".
"Non-deterministic" means "not deterministic", or in other words, "if you put the system in the same situation twice, it might or might not make the same choice both times".
A non-deterministic finite automaton (NFA) can have multiple transitions out of a state. This means there are multiple options for what it could do in that situation. It is not forced to always choose the same one; on one input, it might choose the first transition, and on another input it might choose the same transition.
Here you can think of "situation" as "what state the NFA is in, together with what symbol is being read next from the input". Even when both of those are the same, a NFA still might have multiple matching transitions that can be taken out of that state, and it can choose arbitrarily which one to take. In contrast, a DFA only has one matching transition that can be taken in that situation, so it has no choice -- it will always follow the same transition whenever it is in that situation.
-
$\begingroup$ "it can choose arbitrarily which one to take." So it basically has a probabilistic nature? $\endgroup$ Commented Sep 7, 2017 at 9:16
-
$\begingroup$ @Trilarion, no, it depends on whether or not it leads to accepting state. In fact probabilistic FA is a generalization for NFA. $\endgroup$– rus9384Commented Sep 7, 2017 at 9:38
-
$\begingroup$ "Non-deterministic" means "not deterministic", or in other words, "if you put the system in the same situation twice, it might or might not make the same choice both times". by this do you mean that the machine can accept and reject the same string in two different cases. $\endgroup$ Commented Sep 7, 2017 at 12:40
-
4$\begingroup$ @MadhusoodanP Your intuition is correct from what was written here, and that leads us to what is missing from this answer: When analysing NFAs we always consider all possible execution paths. As long as any path in that machine leads to an accepting state, we consider the input as accepted. So it's not about probability at all, it's simply about whether an accepting state can be reached or not. This intuition becomes clearer when thinking about how NFAs are reduced to DFAs: We have to simulate all possible executions of the NFA, which leads to the exponential blowup in the construction. $\endgroup$ Commented Sep 7, 2017 at 13:05
-
3$\begingroup$ A way to visualize it is to assume that, where multiple transitions could be chosen, the NFA takes all transitions. You create a tree-like structure of all states reached by an input string, and if any of the branches end on an acceptance state, the string is accepted. In other words, with a DFA, you are asking "is the state reached by my input an accept state?", whereas with an NFA, you are asking "is any state that could be reached by my input an accept state?". $\endgroup$ Commented Sep 7, 2017 at 18:23
$\begingroup$
$\endgroup$
6
Take this automaton for instance, it's an NFA and it accepts the string $0110$. To be more pedantic, it accepts strings that end in $10$.
To see that we just need to check whether it reaches an accept state.
\begin{align*} q_0 & \rightarrow 1\\ q_0 & \rightarrow 0\\ \color{red}{q_1} &\rightarrow \color{red}{1}\\ q_2 &\rightarrow 0\\ \end{align*}
Now in the red line there was another possibility, that is when reading the second $1$ I could stay in $q_0$ and then stay in $q_0$ when reading the last $0$. Automata have no memory, so there's no way to 'save' a state and check later if my string ends with $10$, it's like this NFA it's making a guess whether the string ends with $10$ before branching to an acceptable state. The nondeterminism here is making lots of choices and always making the right ones.
It's easier to construct an NFA than it is to construct an DFA, the good thing is that both are equivalent.
answered Sep 6, 2017 at 13:14
-
$\begingroup$ Yes I know the theory part of NFA. But what I was asking was even though there are multiple transitions for a single input characters, the machine is deterministic about what all states it can reach (say by creating threads). Hence it's literally DFA. [Or do you think I am misinterpreting the meaning of determinism] $\endgroup$ Commented Sep 6, 2017 at 13:21
-
1$\begingroup$ The example might be improved wth a slightly more complicated NFA, since a DFA for the same purpose would use the same number of states as your NFA and wouldn't be particularly complicated. By contrast, matching a more complicated regular expression may require a complicated and messy DFA but be trivial in an NFA. $\endgroup$– supercatCommented Sep 6, 2017 at 15:52
-
$\begingroup$ @supercat, at least it would be good to see $\varepsilon$-transitions. $\endgroup$– rus9384Commented Sep 7, 2017 at 9:36
-
1$\begingroup$ @Aristu If you're implementing an NFA in your favourite programming language, threads are a terrible choice. Rather, you should just keep track of the set of states that the automaton "might be in" after each character of input is read. The resulting code will be almost as fast as an implementation of DFAs. $\endgroup$ Commented Sep 7, 2017 at 11:09
-
1$\begingroup$ @Aristu Cycles of $\epsilon$-transitions would be awkward, yes, but the main problem is that threads have huge overheads compared to such a simple unthreaded scheme. The threaded solution requires concurrency control, some way of killing the threads once an accepting computation has been found, some way of noticing that all the threads rejected, ... $\endgroup$ Commented Sep 7, 2017 at 14:51
$\begingroup$
$\endgroup$
2
The transition function of an NFA specifies the allowed transitions at any point in time. There could be more than one option, and the NFA chooses a transition nondeterministically with the goal of eventually reaching an accepting state.
Perhaps you should wait until you learn about nondeterministic Turing machines. Nondeterminism means the same thing in both cases.
answered Sep 6, 2017 at 13:14
-
$\begingroup$ can you please highlight that "a transition nondeterministically". And also please review my answer $\endgroup$ Commented Sep 6, 2017 at 13:52
-
$\begingroup$ I think both of our answers are not super good, though your intuition is sound. $\endgroup$ Commented Sep 6, 2017 at 13:57
$\begingroup$
$\endgroup$
2
Start off with a Finite Automaton. It has states and acceptance states and transitions.
Now, give it more than one trasition rule of of each state, and say that it accepts if there exists a set of transition rules picked after the fact that lead to the acceptance state given an input string.
Once you have your input string, there is a fixed set of concrete transitions and states it goes through (one at a time) to accept that string. But which transitions it picks are only chosen at the end of the string. While the string is being read, which path to take is not determined.
It is non-deterministic. It gets to pick its path through the graph after you give it the entire problem, not as it reads the input.
Now, we formalize this differently than this thought experiment, but this gives you motivation why it got that name.
This explains how it got the name in the first place. Yes, you can model NDFA in a completely deterministic way, but names are sticky. Once you have called something Bob, there is a communication cost to renaming it to something else as nobody knows what you are talking about when you call it Alice.
-
$\begingroup$ yes! I agree with your explanation about NFA. But my question is about why it's Non-deterministic even though the set of states are defined for a single input $\endgroup$ Commented Sep 7, 2017 at 13:07
-
$\begingroup$ @MadhusoodanP It is called non-deterministic because of how it was invented/envisioned. And names are sticky, even after we define multilpe fully deterministic ways to model it. $\endgroup$– YakkCommented Sep 7, 2017 at 13:24
$\begingroup$
$\endgroup$
NFA and DFA are both used to (amongst other things) recognize certain strings.
Non-deterministic finite automaton works like it had an influence on its decisions - it can "choose" to follow a path, or not.
On the image above, when we are dealing with string "00111", notice that when encountering the first "1", there are two possible ways to follow. One can stay at "p" or go to "q". If the automata was to move to the "q", it wouldn't accept the string(since there are no edges coming out of the "q"). But the string can be accepted by this automata by going to the "q" with only the last 1, while staying at "p" for everything else(and that's what's happening).
NFA makes it look like the automata "knew" what is ahead, and chooses accordingly.
Of course it doesn't. DFA and NFA are equivalent in terms of power(you can reduce NFA to DFA and make DFA (probably) simpler with use of NFA), but NFA is useful, because it has allows to define the same languages as DFA while keeping the graphs much shorter and more readable.
There is nothing random in there. The non-deterministic part puts emphasis on the fact that there is some "choice" to take, but the truth is that the automata doesn't take any decisions.
$\begingroup$
$\endgroup$
Both DFA and NFA are deterministic in the sense that they will always accept a string that is part of the language they recognize and reject it otherwise. However, when reading a same string repeatedly, i.e. when put in the same initial conditions, not only an NFA may chose different state transitions (and hence different paths, order of paths, etc.) but the exact state in which it ends up may differ as a result.
Consider this NFA, which accepts strings of 0s in multiples of 2 or 3 (borrowed from Sipser's Theory of Computation):
If the input is 0000, the final state will always be the accept state of the upper branch. If it is 000, it will always be the accept state of the lower branch. However, if it is 000000, it can be any of them, depending on the initial choice of branch. A similar situation occurs for rejected strings like 00000.
So the automaton is really non-deterministic in the usual sense of the word, as opposed to its DFA equivalent, in which the final state of the system is unique and predictible for any given string.
$\begingroup$
$\endgroup$
Determinism: upon reading the current input letter, there is a single successor state that we move to.
So, upon reading an input word $w$, the future is resolved and is based only on the current state we're in.
Nondeterminism: upon reading the current input letter, there is a subset of candidate successor states that we can move to each.
So, upon reading an input word $w$, the future is not necessarily resolved and we have to guess it.
answered Jul 24 at 19:06
$\begingroup$
$\endgroup$
1
From wikipedia, the best way to think about this is to start with deterministic finite state machines(DFA). For a DFA, each transition is uniquely determined by the current state and the input symbol to be processed. Nondeterministic finite state machines (NFA) are simply what you get when you relax this determinism rule to permit transitions to not be uniquely defined. It's what you get when you remove the determinisim rule from DFAs.
-
$\begingroup$ It's a bit more complicated, since nondeterminism is also a specific acceptance condition. $\endgroup$ Commented Sep 6, 2017 at 19:21
$\begingroup$
$\endgroup$
4
Well here is the mix of some content from book [Introduction to Formal Languages and Automata by Peter Linz 4E] and my understanding.
Consider a game-playing program where the machine needs to make the decision for the next move [say for tic-tac-toe]. Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one. Even though the selection process was deterministic and there were many possible moves, the final move made was a single one and was chose as best move while hiding all the tried move-computations from the opponent. [Here we assume that the evaluation process of each possible move was hidden from the opponent].
Hence only one choice was made and opponent is given a illusion such that the move was non-deterministic.
Well if you are not convinced yet by asking that the best move was the product of some deterministic calculations then you must consider the machine which makes perfectly random moves (may be machine looses but it's an NFA).
-
1$\begingroup$ Another way of putting this: to the opponent, your choice was nondeterministic. When modelling the system from the opponent's view, your move is a nondeterministic choice, unless the opponent has figured out the deterministic process behind it. $\endgroup$ Commented Sep 6, 2017 at 15:34
-
$\begingroup$ @reinierpost exactly what I wanted to tell $\endgroup$ Commented Sep 7, 2017 at 8:53
-
$\begingroup$ A more interesting example might be a limited-information moving-pieces game (e.g. "cops and robbers" style). One player moves a robber around a maze while the other player moves cops. At any time when a cop can see a robber, the robber's state will be its location, but on any turn when none of the cops see the robber, the robber may transition to any squares that are adjacent to its position and that the cops can't see at that moment. $\endgroup$– supercatCommented Sep 7, 2017 at 16:54
-
$\begingroup$ @supercat Nice one, but transition made is always a single state, and if you hide the computation of the best move it seems non-deterministic $\endgroup$ Commented Sep 8, 2017 at 12:39