A FSA(Finite State Automaton) is deterministic, a Deterministic Finite Automaton (DFA), if there is only one path to take for a given input. For example, if you are on state q1, and are given input 1, then you only have one state to go to. For example, q2.

However, there does exist Finite Automaton that have multiple paths to take given a given input. These are called Non-Deterministic Finite Automaton (NFA), as their path is undetermined (they have multiple paths!).

Let's take a look at an example:

First, every state of a DFA always has exactly one existing transition arrow for each symbol in the alphabet. The non-deterministic automaton shown above violates that rule. State q1 has one exiting arrow for 1, but it has two for 0; q2 has one arrow for 0, but it has none for 1. In an NFA, a state may have zero, one, or many exiting arrows for each alphabet symbol.

Second, in a DFA, labels on the transition arrows are symbols from the alphabet. This NFA has an arrow with the label ε . In general, an NFA may have arrows labelled with members of the alphabet or ε. Zero, one, or many arrows may exit from each state with the label ε. It acts as a bit of a wild card, which we will see in the regular expression section.

How does the NFA compute?

Suppose that we are running an NFA (Non-Deterministic Finite Automaton) on an input string and come to a state with multiple ways to proceed. For example, say that you are in state q1, in the NFA above, and that the next input symbol is 0. Without reading any input the machine splits into multiple copies of itself, and follows all the possible paths in parallel. Each copy of the machine takes one of the possible ways to proceed and continues as before. If there are subsequent choices, the machine splits again. If the next input symbol doesn't appear on any of the arrows exiting the state occupied by a copy of the machine, that copy of the machine dies, along with the branch of the computation associated with it. Finally, if any one of these copies of the machine is an accept state at the end of the input, the NFA accepts the input string.

If a state with a ε symbol on an exiting arrow is encountered, something similar happens. Without reading any input, the machine splits into multiple copies, one following each of the exiting ε-labelled arrows and one staying at the current state. Then the machine proceeds non-deterministically as before.

Non-deterministic may be viewed as a kind of parallel computation wherein several "processes" can be running concurrently. When the NFA splits to follow several choices, that corresponds to a process "forking" into several children, each proceeding separately. If at least one of these processes accepts, then the entire computation accepts.

This may seem really weird, but actually has practical purposes, such as if you were to traverse a tree structure to find all the leaves, or sum up the values of all the nodes. This application is called recursion. It could perform other recursive type computations, such as in a merge sort.

It is also used in regular expressions which we will look at next.

Take a look at the following example.

This machine demonstrates the convivence of having ε arrows. It accepts all strings where the zeros are in multiples of 2 and 3.

Fix up the following from : https://www.csfieldguide.org.nz/en/chapters/formal-languages/the-whole-story/

Why would you ever want a non Deterministic Finite State Automaton?

In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.

A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P vs NP.

Other examples:

1. Regular expressions

2. A concurrent algorithm can perform differently on different runs due to a race condition.

3. A probabilistic algorithm's behaviours depends on a random number generator.

4. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.

5. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one.

6. Primality testing

In the next section we will look at Regular Expressions which use Non-Deterministic Finite Automaton.