The Non-Equivalence of DFAs and NFAs

Original post: here.

A review on a proof given in the book Introduction to Automata Theory, Languages, and Computation by Hopcroft and Ullman.

The theorem is that Deterministic Finite Automata (DFAs) and Non-Deterministic Finite Automata (NFAs) are equivalent classes of objects (or at least class equivalence is heavily heavily suggested if never quite explicitly claimed).

Of course, to be said up front, the author of this post believes that it is an unnecessary trivialization of the nuanced differences between each class of object.

The Equivalence Argument

The section in the book providing the proof already begins with the conclusion that every DFA is an NFA. Great, off to a bad start.

The reasoning is thus: both DFAs and NFAs accept only regular sets. Of course, the circular definition for a regular set is given earlier in the book as:

Def. 0 - Regular Set - a language is a regular set if it the set accepted by some finite automaton.

And to ensure that we have all of our bases formally covered, we can also include the definition for what a finite automaton is according to the authors:

Def. 1 - Finite Automaton - consists of a finite set of states and a set of state transitions that occur on input symbols chosen from an alphabet $A$.

Then of course, we should also provide a working definition of what a "language" is from the book as well:

Def. 2 - Language - the set of all strings accepted by a finite automaton (FA) whereby "accepted" means that given the string and an initial state in the FA as inputs to the transition function of the finite automaton, the FA will terminate at a final state.

Now that we have established our foundations, let's return to the discussion of testing whether a supposed equivalence between Deterministic Finite Automata (DFAs) and Non-deterministic Finite Automata (NFAs) exists.

We should establish the working definition for non-determinism in a finite automata:

Def. 3 - Non-Deterministic Finite Automata - is a finite automata with states, inputs, start state, and final states. The transition function is a map from the set of all ordered pairs of {states. inputs} to $2^{Q}$, where $Q$ is the set of states of the FA. $2^{Q}$ is the power set of $Q$.

The Argument

Now, let's outline the books' full argument:

The proof hinges on showing that DFAs can simulate NFAs ... that is, for every DFA we can construct an equivalent NFA -- one which accepts the same language.

So here, we have our definition of what "equivalence" means in regards to this "proof". But, what we will show is contentious is the reliance on this premise as justification of the word "equivalence". It suggests a proven over-arching "equivalence" of the entire classes of objects.

But, another question is what "simulate" actually means.

The way a DFA simulates an NFA is to allow the states of the DFA to correspond to sets of states of the NFA.

So, we have setup the proof with the premises and what is actually being attempted to be proven. So let's dive in.

We begin with the theorem that is being proven:

Thrm. 0 - Let L be a set accepted by a NFA. Then there exists a DFA that accepts L.

And here is the proof:

Proof 0 - Let $M$ be an NFA accepting L. Define a DFA $M'$ as follows. The states of $M'$ are all the subsets of the set of states of M. That is $Q'$, the set of states of $M'$, is equivalent to $2^{Q}$ where $Q$ is the set of states of $M$. In this way, the $Q'$ keeps track of the state of all the states $M$ could be in at any given time. $F'$ is the set of all states in $Q'$ containing a final state of $M$.

Now, let's pause here for a moment and recognize the definition of $F'$. It is the set of subsets of states of $M$ that contain a final state from $M$.

Now, the proof requires two more assumptions:

Firstly, the transition function of the DFA maps a subset of states in the NFA, to a final subset of states of the NFA given an input string $a$. And, that this is true iff the transition function of the NFA applied to each of the states in the starting subset of states, with the same string $a$, gets taken to one of states in the set of states from the DFA's final state.

Then the proof shows by induction that this assumption allows for verifying the theorem.

However, there is a final assumption that is only very briefly alluded too at the very end of the "proof" and is quite easy to miss if you are not paying attention to it.

Recall our paused focus and emphasis on the containing definition of final states in the DFA.

Well, the proof ends thusly:

To complete the proof, we have only to add that the final state upon application of the transition function to an accepted string $a$ in the DFA is in the set of final states $F'$ exactly when the transition function of the NFA applied to the same string contains a final state of the NFA. Thus the language accepted by the NFA is the same as the language accepted by the DFA.

Now, give it a thought for a moment.

If we were to run these two machines side by side would we actually get the results from the simulation and the simulated. Would the simulation be the corporeality? Not at all. We could choose to interpret it as such. But the NFA is running coin tosses while the DFA is attempting to never do such. The DFA will run the same sequence every time (with high probability). Whereas the NFA will only probabilistically run the same sequence. Now, we still see that the set of strings acceptable by the NFA are indeed acceptable by the simulating DFA. But, in fact, we miss the obvious second half of this: that those strings are not always "accepted". They are only probabilistically accepted. This an entirely new dimension to the analysis that is blatantly ignored.

Now, because all simulations are wrong. We can be forgiving to the authors.

But, this is very clearly, in no way, a "proof" of the "equivalence" of DFAs and NFAs. However, the authors did define what they meant by "equivalence", so touché (I guess?).

And in fact, everything that is non-deterministic can in no way be "simulated" equivalently by something attempting to be deterministic. This becomes a simple argument of distribution differentials. The distributions over sequences in the case of each class of machine (and each individual machine) changes regardless of chosen interpretations.

Non-Deterministic Turing Machines

Further in the book, the same basic ideas behind the "equivalence" of DFAs and NFAs is used to justify the idea that non-deterministic Turing machines (NTMs) have no "power" beyond deterministic Turing Machines (DTMs).

This is blatantly false.

A NTM responds probabilistically to the input language by the simulating DTM. It does not always accept the strings that the DTM always accepts. And it does such according to a very precise probability distribution.

This is profoundly powerful. The architecture of the NTM guarantees that a given program over the simulating DTM will only compute according to a well-defined probability distribution. That could be utilized in regards to the programs given by the shared language $L$. They can compute a certain output only some of the time.

If our input string is instead a sequence of events rather than a sequence of characters then this has profound implications for real-world physical systems. It means that we can architect machines to probabilistically and conditionally compute certain outputs at certain times.

Why pretend like the difference between these two classes of machines is trivial? It is far from.

Conclusions

To the credit of the author's they did suggest a non-equivalence of these two classes earlier when they said the following:

Later we shall meet automata whose deterministic and non-deterministic versions are known not to be equivalent, and others for which equivalence is a deep and important suggestion.

But, this was a statement that was not emphasized whereas the supposed "equivalence" of these two classes of objects was indeed emphasized and to the detriment of the reader.