Nondeterministic Finite Automata (NFA)
This section will be about Nondeterministic Finite Automata (NFA) and their connection to DFAs. You will see what an NFA is, how to walk through the computation of an NFA, and how NFAs and DFAs are related. You can find the notes related to this section here.
What's an NFA?
We’ve seen what DFAs are. Now, what is are NFAs? NFAs and DFAs share much of the same structure. Where they differ is in the choices that their transition function provides. DFAs are deterministic. This means that for each symbol the machine reads, there is exactly one possible transition it can take. Instead, NFAs allow for multiple possible transitions from a state when reading a letter. In fact, its transition function returns a set of states rather than a single state. The other nifty thing about NFAs is that they provide the possibility of \(\lambda\)-transitions. These are “for free” transitions that allow the machine to transition without reading a symbol on the input tape. All of this is described more formally in the next video.
How does an NFA work?
Ok so now you that you have an idea of what an NFA is, we’ll next see how an NFA runs through its computations.
Building NFAs to accept languages
We’ve looked at many examples and exercises where we create a DFA that accepts a given language. We can of course use some of the same ideas for building NFAs. In addition, however, we can also use the convenience of nondeterminism to create much more compact and elegant machines.
NFAs and DFAs
At this point, you might be thinking “Woah NFAs are pretty cool and this nondeterminism thing makes writing machines a lot easier!”. Some of you might even think that NFAs are more powerful that DFAs. That is, that NFAs can accept more languages than DFAs. In fact, although very convenient, NFAs and DFAs accept exactly the same set of languages! This has some important implications on regular languages. Namely, if DFAs and NFAs accept the same family of languages, then to prove that a language is regular we can either create a DFA or an NFA that accepts it. This surprised me at first because it really seemed like NFAs were doing something “more” than DFAs, but like the next video will show you that is simply not true!
The above video should have given you the intuition behind how any NFA can be converted to a DFA. In the next video, I formally present the conversion algorithm and walk through an example.
Equivalence between NFAs and DFAs
We are now equipped with an algorithm that converts any NFA to an equivalent DFA. What does this imply about the computational power of NFAs and DFAs? Does this help us at all in proving that a language is regular? The following video answers these questions and also gives you a high-level idea of what the proof of correctness for the conversion algorithm would look like.