1
$\begingroup$

So I am starting out with automata theory and I was reading a book and came across an example where the author tries to explain what exactly Nondeterministic Finite Automatas (NFAs) are. He gave an example of a language A such that:

$A = \{w \in \{0,1\}^*: w \text{ has a 1 in the third position from the right}\}$

He then constructs a NFA which is:

Now how he explained it is that the NFA "guesses" that the 1 is the third from right in the string and then it "verifies" that there are exactly two symbols remaining. If there are more than two remaining symbols, then the NFA hangs (in state $q_1$) after having read the next two symbols.

Now I don't know a lot about this topic, but from what I understand an automata can read a string only once. Also, the automata can proceed in either of the two options it has. So how is it that it will accept the string every time? Maybe some time it just stays on $q_1$ and never decides to go to $q_2$. Or maybe it goes to $q_2$ too early and hangs even though there is a 1 in third position from right.

It seems random, but the author mentions nothing about this. So I'm guessing I'm wrong.

Please someone point out what I'm not understanding right here.

$\endgroup$
4
  • $\begingroup$ I think what you're not understanding is that NFA's and languages they recognize are defined formally, not only by words like "guesses", "verifies" and so on. The thing is, a NFA recognizes a word if and only if there is a path labelled by this word that goes from a start state to an accept state. It doesn't matter whether all paths do, or two, or three, as long as there is one. And indeed, contrary to DFAs, there will sometimes be multiple paths for a single word. So here, if you have a word that has a $1$ in the third position to the right, surely you can find a path that does what I said ? $\endgroup$
    – Maxime Ramzi
    Jun 11, 2017 at 13:24
  • $\begingroup$ But surely you can also find a path that doesn't do what I said: the path that loops on $q_1$ for instance. What matters is that there is one. And conversely, if a word $w$ doesn't have a $1$ in the third position to the right, you can probably see that there is no path that goes from a start state to an accept state and that is labelled by this word $\endgroup$
    – Maxime Ramzi
    Jun 11, 2017 at 13:26
  • $\begingroup$ "Maybe some time it just stays on $q_1$ and never decides to go to $q_2$.'' But it does branch out to both $q_1$ and $q_2$ whenever it sees $1$. $\endgroup$
    – Prajwal Kansakar
    Jun 11, 2017 at 13:27
  • 1
    $\begingroup$ @Max Yeah, I think I understand more now. I was thinking about NFAs as physical "computers"/machines. It makes more sense to look at it as a mathematical construct, rather than as a physical thing. Thanks for your help :) $\endgroup$
    – Pratyush Yadav
    Jun 11, 2017 at 13:33

3 Answers 3

Reset to default
3
$\begingroup$

… the automata can proceed in either of the two options it has.

Well, yes. But for a Non-Deterministic Automaton, that means that it proceeds with both options. At the same time. It can do that precisely because it is non-deterministic.

Some people like to describe that fanciful references to time travel, psychic precognition (infallible oracles), or alternative realities, but no such violation of the rules of the physical universe is necessary in the case of Non-deterministic Finite State Automata.

No matter how much reality branching the machine does, the active possibilities are all in a subset of the set of states. In other words, we could easily produce a Deterministic FA whose states are precisely the elements of the power set of the set of states of the NFA, and in fact that is precisely what is done by real-life practical software. (Except that only reachable states are included, so the size of the DFA is often much smaller than exponential in the size of the NFA.)

$\endgroup$
1
$\begingroup$

Let us view a NFA as a graph. A path in this graph is called successful if it starts in some initial state and ends up in some final state. Now a word $w$ is accepted by the NFA if and only if there exists a successful path with label $w$.

This quantifier "there exists" is the crucial point. In particular, a word $w$ can be the label of several paths, some of which are successful, some other ones are not. But if at least one is successful, then $w$ accepted. Dually, $w$ is rejected if and only if no path with label $w$ is successful.

$\endgroup$
0
$\begingroup$

The automaton is non-deterministic because there are two transitions from state $q_1$ with input $1$, one is $q_1$ and the other is $q_2$. After moving to $q_2$, the transitions are deterministic to $q_3$ and then to $q_4$. Thus the assertion is correct.

$\endgroup$
2
  • $\begingroup$ I know the assertion is correct. I needed help in understanding why. $\endgroup$
    – Pratyush Yadav
    Jun 11, 2017 at 14:05
  • $\begingroup$ The guess comes in when you consider the transition from $q_1$ to $q_1$ or to $q_2$, when 1 is entered. The transitions form a relation (not a function). $\endgroup$
    – Wuestenfux
    Jun 11, 2017 at 14:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .