CIS 2620 Notes 2.2

Nondeterministic Automata#

The definition of nondeterministic automata(NFA) just means that at a given character and state, the next state could be ambiguous. More formally, in state $q_0$, on symbol $a$, the choice of next state is not unique: could be either $q_0$ or $q_1$. What follows is that some states can have no next states, and will not process additional symbols.

We know that the deterministic function of a deterministic automata will give you the next state when given the current state and processed character. However, a nondeterministic function will return a set of multiple possible future states(or none) given a current state and character.

When a nondeterministic automata comes to a fork, where it has multiple possible ways it could go, we treat those as separate execution paths. This means that a nondeterministic automata could possibly have multiple execution paths, all of which need to be considered when analyzing it.

We consider a string $s$ to be in the language of an NFA $M$ if and only if there exists at least one successful execution of $M$ on $s$. Generally we simulate this by simulating an execution tree on a string. You can also instead compute the set of all possible states after processing each input symbol(think of it like a BFS).

Defining an NFA#

A nondeterministic finite automata $M$ consists of:

• A finite set of states $Q$
• A finite alphabet $\Sigma$
• An initial state $q_0$ that belongs to $Q$
• A subset $F$ of $Q$, called accepting states
• A transition function $\Delta: Q \times \Sigma \to 2^Q$

Note that NFAs don’t follow computational models of Turing machines, which can only execute one path at a time. Despite this, NFAs are important to study as they are critical to the theory of NP-complete problems and regular expressions.