Work in progress!

Nondeterministic Finite Automata

Nondeterministic finite automata (NFAs) are a type of finite state machine.
Unlike DFAs, they may be in many states at once and allow for transitions on the null symbol.

Depicted is the state-transition diagram for an NFA that recognizes unary strings with less than three symbols.

The initial state is q₀.
The final states are q₁, q₂, and q₄.
Formally, we say S = q₀ and F = { q₁, q₂, q₄ }

There are four transitions:

• δ(q₀, ε) = q₁
• δ(q₀, 1) = q₂
• δ(q₀, 1) = q₃
• δ(q₃, 1) = q₄

Recall that ε is a special symbol denoting a null word.
Here, it means the NFA can undergo a transition from q₀ to q₁ without reading an input symbol.
This type of transition cannot be performed by a DFA, which must read an input symbol on every transition.

The NFA can undergo a transition from q₀ to q₁ and q₂ on the same input symbol "1".
After reading this symbol, the NFA will be in both states at once.
This type of transition also cannot be performed by a DFA, which can only be in one state at at time.

Due to this flexibility:

• The NFA's transition function may not always be represented as a table.
  In this case, the cell in row q₀ and column 1 would have two elements.
• The transition path of an input word may not be represented in a linear form.
  In this case, the transition path for the word "11" would include a branch.

Both of these are caused by the existence of two transitions on 1 from q₀.

---

Constructing NFAs from Language Descriptions

Because NFAs are less restrictive than DFAs, they can be easier to construct from natural language descriptions.

Example 1: Union

Example 2: Concatenation

Example 3: Kleene Closure

There is no limit to the size of a sandwich.
The kitchen contains the following ingredients: Σ = { Bread, Cheese, Ham, Lettuce, Mayo, Mustard, Tomato, Turkey }

A sandwich always starts and ends with a slice of bread.