Conceptually, to track the multitude of "state positions" arising in an NFA while it is processing a given input string, a quantitative notion of memory/cache/storage is required per "fork" of execution over the automaton, for keeping track of the states where the computation is currently "at".

What is the typical theoretical treatment, regarding the complexity of this degree of concurrency?!


1 Answer 1


The theoretical treatment is just to say "It's what happens: that's what nondeterminism is." The machine accepts if there's any computational path that finishes in an accepting state.

Anything about memory, caches or concurrency is a matter of implementation. The simplest implementation is to keep a vector of Booleans that records whether or not the machine "could be" in each of the states at the current step of the computation.

  • $\begingroup$ That is indeed the approach I have always seen. No doubt though, some theoretically interesting things can be said, about the necessary size of that obvious vector $\endgroup$
    – matanox
    Commented Sep 26, 2017 at 16:30

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.