NFAs

Nondeterministic Finite Automata (NFA)

A Nondeterministic Finite Automaton (NFA) is a type of finite state machine used in automata theory to recognize regular languages. Unlike Deterministic Finite Automata (DFA), NFAs allow multiple possible transitions for a given state and input symbol, including ε-transitions (moves without consuming input).

---

1. Formal Definition of an NFA

An NFA is defined as a 5-tuple:

$$M = (Q, \Sigma, \delta, q_0, F)$$

Where:

• $Q$ → A finite set of states.
• $\Sigma$ → A finite input alphabet.
• $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ → A transition function that maps a state and input symbol (or ε) to a set of possible next states.
• $q_0 \in Q$ → The initial state.
• $F \subseteq Q$ → The set of accepting (final) states.

---

2. Key Characteristics of NFAs

A. Multiple Transitions for the Same Input

• An NFA can have multiple transitions from a single state on the same input symbol.
• Unlike a DFA, where each input determines exactly one next state, an NFA can transition to multiple states or none at all.

B. ε (Epsilon) Transitions

• An NFA can move to another state without consuming any input (i.e., transition on ε).
• This allows NFAs to have more flexibility in recognizing patterns.

C. Acceptance of Input

An NFA accepts a string if at least one of its computation paths leads to a final state.

• If there exists at least one sequence of transitions that reaches an accepting state, the string is accepted.
• Otherwise, the string is rejected.

---

3. Example of an NFA

Transition Table Representation

Consider an NFA that accepts strings ending in "01" over the alphabet {0,1}:

State	Input = 0	Input = 1	ε (Epsilon)
q0	{q0, q1}	{q0}	-
q1	-	{q2}	-
q2	-	-	Accepting State

• q0 transitions to q0 on 0 (loop) and moves to q1 on 0.
• q1 transitions to q2 on 1.
• q2 is an accepting state, meaning any string ending in "01" is accepted.

Graphical Representation (Transition Graph)

• q0 → (0) → q0, q1
• q1 → (1) → q2 (Accepting State)

The NFA can take multiple paths simultaneously due to nondeterminism.

---

4. NFA vs. DFA

Feature	NFA	DFA
Transitions per Input	Can have multiple transitions	Only one transition per input
Epsilon (ε) Transitions	Allowed	Not allowed
Deterministic Behavior	Nondeterministic (multiple paths)	Fully deterministic (one path per input)
Implementation Complexity	Simpler to define, harder to implement	Harder to define, easier to implement
Efficiency	Can be exponentially smaller than an equivalent DFA	Requires more states in some cases

Theorem: Every NFA has an equivalent DFA, but the DFA may have exponentially more states than the NFA (subset construction method).

---

5. Applications of NFAs

• Lexical Analysis: Used in token recognition in compilers.
• Regular Expressions: NFAs efficiently represent regular expressions in search engines and text processing.
• Pattern Matching: Found in AI, natural language processing, and bioinformatics.
• Network Protocols: Used in modeling communication protocols with nondeterministic behavior.

---

Conclusion

An NFA is a powerful computational model that generalizes DFAs by allowing multiple transitions per input and ε-moves. While NFAs may seem more flexible, they are not more powerful than DFAs in terms of language recognition, as any NFA can be converted into an equivalent DFA. However, NFAs are easier to construct and widely used in practical applications such as regex processing and lexical analysis.