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$$ - for a.
• 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

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.

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.

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 5-tuple

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

1. $$Q = \{q_0, q_1, q_2, q_3, q_4\}$$,
2. $$Σ = \{$$a$$,$$b$$\}$$
3. $$q_0 = q_0$$,
4. $$F = \{q_4\}$$.
5. $$δ$$ is described as a transition table

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 state States.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.

Download (GitHub)