NFA in Java
In previous tutorial (see Theory of DFA ) we talked about DFA and implemented one in Java (see DFA in Java ). Here we will focus on NFA (Nondeterministic Finite Automaton) or NFSM (Nondeterministic Finite State Machine).
NFA vs. DFA
Just by looking at the names of NFA and DFA, we can see the main difference between them. That is, DFA is a deterministic while NFA is nondeterministic. But what exactly means for automaton to be deterministic? From Image 1.0.0 of DFA we see that given any state and any symbol there is only one transition to the next state. Thus, next state is determined. While NFA has no such constraint. For example, Image 1.0.3 shows NFA which recognises language of $$\{aa, aab\}^*\{b\}$$.
From image above we see that some states in NFA,
 Don't have transition for every symbol in the alphabet. For example, $$q_1$$ and $$q_2$$ don't
have transition for
b
, while $$q_3$$  fora
.  Can have no transitions at all. For example, $$q_4$$ doesn't have any arrow pointing out.
 Can have more than one transition for a given symbol. For example, if input symbol is
a
, then $$q_0$$ can transition to $$q_1$$ and $$q_2$$.
One of the advantage of NFAs over DFAs, are their simplicity. State diagrams of NFAs tend to have less nodes and edges. For example Image 1.0.5 shows equivalent DFA which recognises same $$\{aa, aab\}^*\{b\}$$ language.
How NFA computes?
First of all, given symbol from the alphabet, NFA can transition to zero, one, or many states. Thus, transition function output is not just one state as in DFA, but set of states. So, if a state doesn't have a transition to other state for a given input, then an empty set is returned. On the other hand, if a state has one or more transitions, then a set with all applicable states are returned. One way of thinking about NFA, is to imagine many parallel computations. For example, if NFA is in the start state $$q_0$$, then input symbol $$a$$ forces it to split itself into two machines computing simultaneously, one of which has $$q_1$$, other one  $$q_2$$ as current state. NFA accepts a string if at least one of the machines ends up in the accept state.
One way of representing NFA computation is a tree. For example,
Image 1.0.4
shows how NFA from
Image 1.0.3
accepts aaaab
string.
First symbol of aaaab
is a
. From
Image 1.0.3
we see
that,
given symbol a
, start state $$q_0$$ has two transitions: one to $$q_1$$, other  to
$$q_2$$.
Both those transitions are represented as a first split in the tree. So, left and right branches stands for two
parallel machines.
When NFA receives second symbol a
, then actually two machines receives it. First one
transitions to
$$q_0$$, while another to $$q_3$$ state. After third input symbol, which again is a
,
first machine splits into two, while second dies, because state $$q_3$$ doesn't have transition for symbol
a
. After fourth symbol a
NFA is in two states: $$q_0$$ and
$$q_3$$. And after the last symbol b
one machine transitions from $$q_0$$ to $$q_4$$,
another
 from $$q_3$$ to $$q_0$$. One of the final states $$q_4$$ is an accept state, thus NFA accepts string aaaab
.
Formal definition of NFA
A nondeterministic finite automaton (NFA) $$M$$ is a 5tuple $$(Q, Σ, δ, q_0, F)$$, where
 $$Q$$ is a finite set called the states,
 $$Σ$$ is a finite set called the alphabet,
 $$δ : Q × Σ → P(Q)$$ is the transition function,
 $$q_0 ∈ Q$$ is the start state, and
 $$F ⊆ Q$$ is the set of accept states.
The only difference between
Definition 1.0.0
of DFA and
Definition 1.0.6
of NFA is a transition function
$$δ$$.
In the first case it is $$δ:Q × Σ → Q$$, while in later  $$δ:Q × Σ → P(Q)$$. In other words, DFA's transition
outputs
only one state from $$Q$$, while NFA  one set of states from $$P(Q)$$. Notation of $$P(Q)$$ denotes power
set of $$Q$$.
In other words all subsets of $$Q$$. For example, let $$Q = \{a, b, c\}$$, then
$$$P(Q) = \{\{∅\}, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$$$
Notice, $$∅$$ is included in the power set. Therefore, is perfectly valid for transition function to return an empty
set.
For example (see
Image 1.0.3
), if the first argument is a state $$q_1$$ and the second is a symbol
b
, then transition function $$δ$$ is $$ δ(q_1, b) = ∅$$.
Extended transition function for NFA
For DFA we defined extended transition function in Definition 1.0.2 . The same thing we will do for NFA.
Let $$M = (Q, Σ, δ, q_0, F)$$ be a nondeterministic finite automaton (NFA). We define the extended transition function
$$$δ^* : Q × Σ^* → P(Q)$$$as follows:
 For every $$q ∈ Q$$, $$δ^∗(q, ε) = \{q\}$$
 For every $$q ∈ Q$$, every $$y ∈ Σ^*$$, and every $$a ∈ Σ$$,
$$$δ^∗(q, ya ) = \bigcup \{δ(p,a) \mid p ∈ δ^∗(q, y)\}$$$
The first thing what we should notice, $$δ^*$$ is defined recursively. Note the difference between base case in Definition 1.0.2 and Definition 1.0.7 . Former, given a state and empty string, returns same state. While latter, returns set of states. And it does make sense, because at the end, NFA may end up in more than one state.
While the base case of $$δ^*$$ for NFA looks almost the same as for DFA, recursive case doesn't. The most notable difference is an operation over set of sets $$\bigcup$$ called infinitary union. For example, let $$S = \{\{a, b\}, \{d\}, \{b, c\} \}$$, then $$$ \begin {align} \bigcup S &= \bigcup \{\{a, b\}, \{d\}, \{b, c\}\}\\ &= \{a, b\} ∪ \{d\} ∪ \{b, c\} \\ &= \{a, b, c, d\} \end {align} $$$ So, infinitary union takes a set and applies a union operation $$∪$$ between all its elements. Note, set elements must be set themselves, because union can be applied only between sets.
We know that recursive case of $$δ^*$$ returns a union of multiple sets. Each set is an output of transition function $$δ(p, a)$$, where $$a$$ is the last symbol of a string $$ya$$, and $$p$$ is a member of set of states which extended transition function $$δ^*(q, y)$$ returns, given a state $$q$$ and original string $$ya$$ without last character $$a$$. Yes, I know, it is too confusing. The best way too understand how $$δ^*$$ function works is by using a specific example.
Image 1.0.4
shows how NFA from
Image 1.0.3
accepts string aaaab
. We will do
the same thing
using $$δ^*$$ function. Meaning, we will trace $$δ^*$$ with start state $$q_0$$ and a string aaaab
as input. Thus,
$$$ \begin{align}
δ^*(q_0, aaaab) &= \bigcup \{δ(p,b) \mid p ∈ δ^∗(q_0, aaaa)\} \\
δ^*(q_0, aaaa) &= \bigcup \{δ(p,a) \mid p ∈ δ^∗(q_0, aaa)\} \\
δ^*(q_0, aaa) &= \bigcup \{δ(p,a) \mid p ∈ δ^∗(q_0, aa)\} \\
δ^*(q_0, aa) &= \bigcup \{δ(p,a) \mid p ∈ δ^∗(q_0, a)\} \\
δ^*(q_0, a) &= \bigcup \{δ(p,a) \mid p ∈ δ^∗(q_0, ε)\} \\
δ^*(q_0, ε) &= \{q_0\}
\end {align}
$$$
Notice, how recursively applying definition of $$δ^∗$$ we end up at the base case. But we are not done yet, by
recursive substitution,
$$$ \begin{align}
δ^*(q_0, a) &= \bigcup \{δ(p,a) \mid p ∈ \{q_0\}\} \\
&= δ(q_0, a) \\
&= \{q_1, q_2\} \\\\
δ^*(q_0, aa) &= \bigcup \{δ(p,a) \mid p ∈ \{q_1, q_2\}\} \\
&= δ(q_1,a) ∪ δ(q_2,a) \\
&= \{q_0\} ∪ \{q_3\} \\
&= \{q_0, q_3\} \\\\
δ^*(q_0, aaa) &= \bigcup \{δ(p,a) \mid p ∈ \{q_0, q_3\}\} \\
&= δ(q_0,a) ∪ δ(q_3,a) \\
&= \{q_1, q_2\} ∪ \{∅\} \\
&= \{q_1, q_2\} \\\\
δ^*(q_0, aaaa) &= \bigcup \{δ(p,a) \mid p ∈ \{q_1, q_2\}\} \\
&= δ(q_1,a) ∪ δ(q_2,a) \\
&= \{q_0\} ∪ \{q_3\} \\
&= \{q_0, q_3\} \\\\
δ^*(q_0, aaaab) &= \bigcup \{δ(p,b) \mid \{q_0, q_3\} \} \\
&= δ(q_0,b) ∪ δ(q_3,b) \\
&= \{q_4\} ∪ \{q_0\} \\
&= \{q_4, q_0\}
\end {align}
$$$
Notice, corresponding between set of resulting states after each substitution in $$δ^*$$ and each level of leaves in
Image 1.0.4
.
Equipped with power knowledge of extended transition function we can precisely define what means for NFA to accept a string.
Let $$M = (Q, Σ, δ, q_0, F)$$ be a nondeterministic finite automaton (NFA or εNFA), and let $$a ∈ Σ^*$$. The string $$a$$ is accepted by $$M$$ if
$$$δ^*(q_0, a) ∩ F \neq ∅ $$$and is rejected by $$M$$ otherwise.
This is just a fancy way of saying: If an output of $$δ^*$$ has at least one accept state, then NFA accepts a string.
NFA as 5tuple
There are two fundamental ways of implementing NFA:
 Converting NFA to DFA and implementing the latter.
 Implementing NFA directly.
DFA computes in the linear, while NFA in exponential time, thus first option would result in much faster algorithm. Unfortunately, we don't know how to convert NFA to DFA yet, therefore we will leave it for the next time. For the second option we have two choices:
 We can use backtracking, where given a choice we would recursively cycle through each of them.
 We can keep track of the states that NFA could be in any given moment.
Second approach is more intuitive than the first one. Also, it conforms with Definition 1.0.7 . But before we start, it would be good to check DFA in Java , because implementation of NFA will be very similar. For guinea pig, we will use NFA from Image 1.0.3 . Its formal definition is
$$M = (Q, Σ, δ, q_0, F )$$, where
 $$Q = \{q_0, q_1, q_2, q_3, q_4\}$$,
 $$Σ = \{$$
a
$$,$$b
$$\}$$  $$q_0 = q_0$$,
 $$F = \{q_4\}$$.
 $$δ$$ is described as a transition table
$$a$$  $$b$$  

$$q_0$$  $$\{q_1, q_2\}$$  $$\{q_4\}$$ 
$$q_1$$  $$\{q_0\}$$  $$∅$$ 
$$q_2$$  $$\{q_3\}$$  $$∅$$ 
$$q_3$$  $$∅$$  $$\{q_0\}$$ 
$$q_4$$  $$∅$$  $$∅$$ 
Implementing states
First, we will implement private enum States {...}
which represents all the states
of NFA. In other words  $$Q$$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private enum States {
Q0(false), Q1(false), Q2(false), Q3(false), Q4(true);
final boolean accept;
States(boolean accept) {
this.accept = accept;
}
Set<States> a;
Set<States> b;
static {
Q0.a = new HashSet(Arrays.asList(Q1, Q2));
Q0.b = new HashSet(Arrays.asList(Q4));
Q1.a = new HashSet<>(Arrays.asList(Q0));
Q1.b = Collections.EMPTY_SET;
Q2.a = new HashSet<>(Arrays.asList(Q3));
Q2.b = Collections.EMPTY_SET;
Q3.a = Collections.EMPTY_SET;
Q3.b = new HashSet<>(Arrays.asList(Q0));
Q4.a = Collections.EMPTY_SET;
Q4.b = Collections.EMPTY_SET;
}
Set<States> transition(char ch) {
switch (ch) {
case 'a':
return this.a;
case 'b':
return this.b;
default:
return Collections.EMPTY_SET;
}
}
}
First part of the code is nothing new. In Line 3 we create five states and pass boolean
accept
to the constructor, to indicate accepting and not accepting states $$F$$. Line 11 declares two instance variables.
Which
will hold current state's next set of states for every input symbol. In static {...}
block
we initialise those variables. Think of it as a transition table. In fact, there is a direct correspondence between
static {...}
block and
Table 1.0.1
. And lastly,
Set<States> transition(char ch) {...}
method returns next set of states.
At this stage, in the DFA implementation we faced a problem: What to do with all the symbols not in the alphabet? There were few choices:
 Throw an exception.
 Encapsulate alphabet.
 Change DFA itself by introducing a dead state.
That was for DFA. On the other hand, NFA doesn't have this problem. Because if a state doesn't have a transition for
a given
symbol, then it returns an empty set, which is already in the codomain of $$δ$$ function.
But what about a case when NFA had to split itself? In that case, all
current states would return an empty set, from which is impossible to reach accepting state, thus any string with
symbol not in the alphabet is rejected automatically. The only thing we need to do, is to make sure that by
default Set<States> transition(char ch) {...}
returns an empty set.
Implementing $$δ^*$$
As I said before, we will implement extended transition function by tracking all the current states.
To do this we have a few options. For example, we could use a tree where each node would
represent a state, while edges  transitions. A start state would be a root node, while current states 
all the leafs in the tree. For example,
Image 1.0.4
shows a tree for aaaab
string.
This approach would enable use to keep track not just current states, but all the previous states as well.
Another way to implement transition function is by using sets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class NFA {
private enum States {
//...
}
// Accepts or rejects a string
public boolean accept(String string) {
Set<States> currStates = new HashSet<>();
currStates.add(States.Q0);
for (int i = 0; i < string.length(); i++)
currStates = union(currStates, string.charAt(i));
return currStates.stream().anyMatch(s > s.accept);
}
// Helper method which returns set of next states
private Set<States> union(Set<States> currStates, char ch) {
Set<States> nextStates = new HashSet<>();
for (States cState: currStates)
nextStates.addAll(cState.transition(ch));
return nextStates;
}
}
So we have two methods:

public boolean accept(String string) {...}
. Which is very similar to DFA's. Both have same signature as well as functionality. In the first few lines we create set of current states. Initially it has only a start stateStates.Q0
. Then, by looping through each character in the string, we reassign set of current states to the union of next states, which becomes current states. It is like in the Definition 1.0.7 of transition function, except we use loop for iteration, instead of recursive calls. The last line corresponds to the Definition 1.0.8 which checks if there is an accept state in the last set of states. 
private Set<States> union(Set<States> currStates, char ch) {...}
. It is a helper method which given a set of current states and a symbol returns the union of all the next states.