Powerset construction is used to convert a non-deterministic finite automaton (NFA) into a deterministic finite automaton (DFA). Is the method/algorithm used to do this deterministic itself and if so, why?

  • 3
    $\begingroup$ Have you inspected the algorithm? At which point do you think non-determinism might come into the picture? $\endgroup$ – Raphael Aug 28 '16 at 0:25
  • $\begingroup$ I haven't actually found an implementation of the algorithm. As the construction is defined in my course notes, I don't really see why it wouldn't be non-deterministic. But I'm having a hard time grasping how/why it is deterministic, as it is rather vaguely formulated as also noted in the answers. $\endgroup$ – FHannes Aug 28 '16 at 0:36
  • $\begingroup$ @FHannes The answer notes that your question is vague. The powerset construction is not remotely vague: it is specified by a couple of lines of mathematics. $\endgroup$ – David Richerby Aug 28 '16 at 9:22
  • $\begingroup$ @DavidRicherby I'm not confused about the powerset construction. I am confused about that question myself. It's a possible exam question that has been asked in the past. I was assuming I was missing some key insight, as I'm having a hard time answering it myself. $\endgroup$ – FHannes Aug 28 '16 at 9:44
  • $\begingroup$ @DavidRicherby My assumption is that "Is the transformation NFA => DFA deterministic?" could be answered as yes, because the output is unique for any given NFA or, for a given NFA, there can't be 2 different DFA's resulting from the powerset construction method. $\endgroup$ – FHannes Aug 28 '16 at 10:09

The method itself is (or at least can be made), though the question is somewhat ill posed. What do you mean by deterministic?

The algorithm cannot be run on an NFA or DFA, so it's not deterministic/non-deterministic in that sense.

In most cases, the algorithm will run on a Turing Machine, or some similar model (RAM machine, programming language, lambda calculus, etc.).

It's known that any non-deterministic Turing Machine can be simulated by a deterministic one, using backtracking. So in this sense, the algorithm certainly can be made deterministic.

Is it possible to define the powerset construction in such as way that it's non-deterministic? Yes. There's some element of choice in which states you process first, which NFA states you choose to expand, whether you look breadth-first or depth-first, etc.

But it's trivial to remove these choices, either by resolving them arbitrarily, or by making the choice with some heuristic.

| cite | improve this answer | |

The usual description of the powerset construction corresponds to a deterministic algorithm whose running time is polynomial in the output size.

Although non-deterministic Turing machines are equal in power to deterministic ones, they are (probably) not equivalent in terms of complexity (a particular case is the well known P vs. NP conjecture).

| cite | improve this answer | |
  • $\begingroup$ I'm not sure why you describe it as polynomial in the output size, rather than exponential in the input size: it seems misleading not to even mention that the output is exponentially larger. And I don't see the relevance of Turing machines (Help! Help! The CS police are chasing me) since the question is about automata, where nondeterminism is known not to add more power. $\endgroup$ – David Richerby Aug 28 '16 at 9:21
  • $\begingroup$ @DavidRicherby You seem to have answered your own questions. I'm describing the algorithm as polynomial in the output size since it is not too meaningful to measure the running time with respect to the input size in this case; usually the output size is polynomial in the input size, but here things are different. Therefore the correct definition of efficient should be polynomial in the output size. Regarding non-determinism, as I explain in my answer, it does affect the efficiency of algorithms, and does add more power (assuming, e.g., that NP differs from P). $\endgroup$ – Yuval Filmus Aug 28 '16 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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