Show that ANFA is NL-complete.© BrainMass Inc. brainmass.com March 21, 2019, 2:05 pm ad1c9bdddf
Consider the logspace algorithm for A DFA. Now for an NFA, follow the same algorithm,
except when there are mutliple states to transition to, chose one nondeterministically. Since
this is essentially the same algorithm, it will still be logspace. And there will be an accept-
ing branch of the computation exactly when there is an accept bath through the NFA. So ...
Automata and Computability are emphasized.