1
$\begingroup$

A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states.

Does the automaton uniformly randomly choose one out of the several states?

So different runs on the same input will give different sequence of states?

Does the automaton have to run in all the possible sequences of states on a given input? Or just one random run?

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
10
$\begingroup$

A non-deterministic automaton runs in all possible sequence of states on a given input. It is not a random run.

An input symbol is accepted only if in at least one of the runs it has reached an accepting state after reading the given input.

Hope this helps :D

Improve this answer
$\endgroup$
8
  • $\begingroup$ thanks. does the automaton run multiple times each with different sequence of states, or run just one time but in some way (?) that it can go over all sequences of states? $\endgroup$
    – Tim
    Commented Jun 3, 2014 at 13:47
  • $\begingroup$ I used to think of it as it runs just one time in some way. Not so sure if it's correct $\endgroup$
    – da4kc0m3dy
    Commented Jun 3, 2014 at 13:50
  • 8
    $\begingroup$ @Tim It helps to think of a nondeterministic automaton as a machine in the multiverse. Every time it makes a transition with more than one possible move, it magically splits reality into several universes, running a different move in each. In any of these universes, then, the machine appears to be deterministic. The machine accepts an input string if it accepts in any of these universes. $\endgroup$
    – Rick Decker
    Commented Jun 3, 2014 at 13:57
  • 1
    $\begingroup$ For non-deterministic Turing Machines a (less philosophical) way of interpreting the semantics is to simulate via a 3-tape deterministic Turing Machine, essentially by doing a breadth first search across all possible non-deterministic executions. $\endgroup$
    – Wandering Logic
    Commented Jun 3, 2014 at 14:00
  • 1
    $\begingroup$ This description puzzles me. Why not just say: a non-deterministic automaton's run is influenced by decisions made along the way, and say that an input symbol is accepted if it is accepted in at least one of the possible runs?? $\endgroup$
    – reinierpost
    Commented Jun 3, 2014 at 15:10
7
$\begingroup$

Non-deterministic machines are not realistic devices. They are conceptual devices useful for developing some theories. There are several possible ways of conceiving of the operation of a non-deterministic automaton:

  1. Whenever the non-deterministic automaton has to make a choice, it "forks" or "splits" to several different automata running in parallel, each making a different choice. The automaton accepts if at least one of its "copies" accepts.

  2. Whenever the non-deterministic automaton has to make a choice, it asks a "deity" for a "hint" (sometimes known as a "witness"), and follows the hint. The automaton accepts if some sequence of hints given it by the deity will make it accept.

  3. The non-deterministic automaton considers all possible execution paths sequentially (one by one). If any of them accepts, it accepts the input.

All these different views are valid. Choose whichever you like the most.

Regarding the second viewpoint, more can be said. You can think of it as a one-player game. The deity is trying to "convince" the automaton to accept the input. It's up to the deity to come up with a convincing sequence of hints. If the input does not belong to the language, then nothing the deity does will convince the automaton. If the input does belong to the language, then the deity can convince the automaton somehow.

A good example is the language of true propositions. Here a hint is a proof. Every true proposition has a proof, and no false proposition has one.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Does the "deity" give the whole proof at once or suggest statements? $\endgroup$
    – mrk
    Commented Jun 3, 2014 at 18:51
  • 1
    $\begingroup$ @saadtaame It doesn't matter. The deity knows your algorithm, so it knows which questions you are going to ask in advance, and can prepare the entire answer once and for all. Whether you ask it one question or several is up to you – the deity supports both modes. $\endgroup$
    – Yuval Filmus
    Commented Jun 3, 2014 at 21:17
6
$\begingroup$

The computation of a non-deterministic automaton can be modeled by a tree. The input is accepted if there is a root-to-leaf path that eats the input and terminates in an accepting state.

When the automaton branches, each branch carries the computation on its own. So you can imagine that all possible root-to-leaf paths are being considered at the same time, meaning that the overall running time is bound by the height of the tree.

This process can be simulated on a real machine by trying out every possible path. The simulation takes more time naturally. Each branch contributes a factor of $2$, so the simulation takes $2^n$ or something similar.

Improve this answer
$\endgroup$
4
$\begingroup$

Strictly speaking I do not answer your question, but I will hint at a broader automaton model. (It is meant as a PS to the answer by Yuval.) I will not anwer questions here: it might get off-topic.

The nondeterministic automaton is "existential": it accepts a string iff a run on that string exists. How you want to visualize that is your own choice, and Yuval has sketched three possibilities: try all possibilities in parallel, one-by-one, or accept divine hints.

There is a larger type of automata, called alternating, that have existential and universal states. In an existential state one requires the existence of at least one succesful continuation, while in a universal state all continuations should end in a final state.

For finite state automata, the existential extension is equivalent in power as the original FSA, whether deterministic or nondeterministic). For Turing machines there is an additional layer of complexity classes for alternation: e.g., $P \subseteq NP \subseteq AP$. And there is an even much nicer connection to games and logic: alternation is like a two player game.

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.