Introduction to Nondeterministic Finite Automata (NFA)

Before you continue reading, I would recommend reading my “Introduction to Deterministic Finite Automata (DFA)” article before reading this one, as this is a continuation of that article.

Introduction to Deterministic Finite Automata (DFA) → https://medium.com/@gregorycernera/introduction-to-deterministic-finite-automata-dfa-40aac64b9895

Photo by Green Chameleon on Unsplash

What is an NFA?

Similar to a DFA, an NFA is a state machine consisting of states and transitions that can either accept or reject a finite string. And like a DFA, we must use circles to represent states, and directed arrows to represent transitions. But, what’s the difference?

Essentially, NFAs have less restrictions than DFAs, and can therefore make complicated automata easier to understand and depict in a diagram.

What is the difference between an NFA and a DFA?

There are essentially three main differences between an NFA and a DFA…

1. As you may recall, a DFA can only have one transition for each symbol going outwards from the state. But, an NFA can have multiple transitions for a symbol from the same state. If you see the figure below, the NFA diagram has both a and b looping back to itself, and also has a second a point towards another state. (Note: These diagrams are not functionally equivalent. They are simply created to show differences in transitions)

2. Another difference is that an NFA is not required to have a transition for each symbol. So if we are creating an NFA for a language with the alphabet {a, b}, it is valid to have a state like this:

In this case, if we do happen to get the symbol b, we would still remain in the state. This is because this state is only interested in getting the symbol a so that it can continue to the next state.

3. The last difference between an NFA and a DFA is that an NFA can have a transition for an empty string. A DFA cannot transition on an empty string, as this is an invalid transition, but an NFA is allowed to do this. See below:

An important component of an NFA to note is that an NFA can have multiple outcomes with the same language, but if at least one of those outcomes results in an accepting state, then the diagram and language accept the string. We will demonstrate this in the next section.

NFAs are tricky to get the hang of. It took me a while before I actually understood why we are able to use multiple transitions for a symbol. It requires a different way of thinking, but as you keep practicing, you’ll eventually get the hang of it. I want to try to introduce the concept so that you can get familiar with how NFAs differ from DFAs.

How can we build an NFA?

Let’s use the same example that we used in the DFA article. That is, we will again be using the language: {ax | x ∈ {a, b}*}, which states that we want all strings that begin with the letter a.

For this language, our DFA looks like this:

Instead of building the NFA step by step, I’ll show you what the NFA is for this language now so that you can look at the diagram yourself before I explain each component. Here is the NFA equivalent for the language…

Now, let’s break each component down and explain how this diagram works.

The first thing we do is begin with the start arrow pointing to the start state. This is where we begin our processing of the string. Because we need at least an a to be in the string, our language cannot accept an empty string. Therefore, the start state, S, cannot be an accepting state. See the figure below:

Now, we must handle the rule of our language that the string must begin with the symbol a. We only care if our machine gets the symbol a as it’s first symbol, and we want the machine to crash/fail if the first symbol is anything other than a.

So, with the power of an NFA, we can simply specify that if we get an a, jump to the next state to continue with the string processing. But, if we get anything other than an a, remain in the state and reject the string. See the figure below:

Now that we have an a in the first position, we can now move into an accepting state for our string. See below:

Finally, our language {ax | x ∈ {a, b}*} states that our string can be followed by any symbol in any order in the set {a, b} by using the x in ax. In other words, after we get the initial a in our string, anything can happen after that. We don’t care.

That means we must have a and b looping back to itself in the accepting state. See below:

And that is how we create the NFA for our language!

Formal Definition of an NFA

The formal definition of an NFA consists of a 5-tuple, in which order matters.

Similar to a DFA, the formal definition of NFA is: (Q, 𝚺, δ, q0, F), where

1. Q is a finite set of all states
2. 𝚺 is a finite set of all symbols of the alphabet
3. δ: Q x 𝚺 → Q is the transition function from state to state
4. q0 ∈ Q is the start state, in which the start state must be in the set Q
5. F ⊆ Q is the set of accept states, in which the accept states must be in the set Q

The only difference between an NFA and a DFA for their formal definitions is that for an NFA, you must specify the empty string (𝜀) within your delta function, along with the other symbols. See below to see how we do it.

For our NFA above, the formal definition would be:

• Q → {s, f}
• 𝚺 → {a, b}
• Start state → s
• F → { f }
• δ functions:

δ(s, a) = { f }
δ(s, b) = { }
δ(s, 𝜀) = { }
δ(f, a) = { f }
δ(f, b) = { f }
δ(f, 𝜀) = { }

There you have it. An informal and formal definition for a sample NFA. This is a very simple, explanatory process to illustrate the power of an NFA and it’s differences from the DFA

I hope this article can help you!