Day 5

Non-deterministic Finite Automata (NFA)

Introduction to Non-determinism

Non-determinism is a fundamental concept in computation theory that allows a machine to have multiple possible next states for a given input. Unlike deterministic machines where each input leads to exactly one next state, non-deterministic machines can “guess” or “pursue multiple paths simultaneously.”

Key Differences from DFAs

1. Multiple transitions possible for the same input symbol
2. Ability to move without consuming input (ε-transitions)
3. Acceptance criteria differs - accepts if ANY path leads to acceptance

Formal Definition of NFAs

An NFA is formally defined as a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$ where:

$$\begin{array}{rl}& Q:\text{finite set of states}\\ & \Sigma :\text{finite alphabet}\\ & \delta :Q\times (\Sigma \cup \{\epsilon \})\to \mathcal{P}(Q)\text{ (transition function)}\\ & q_0:\text{initial state}\\ & F:\text{set of accepting states}\end{array}$$

Mathematical Representation

For a state $q\in Q$ and input symbol $a\in \Sigma$:

$$\delta (q,a)=\{q_1,q_2,...,q_n\}\text{ where }{q}_i\in Q$$

ε-transitions (Epsilon Transitions)

Properties

• Allows movement between states without consuming input
• Can create “shortcuts” in computation
• Critical for certain constructions and proofs

ε-closure

For a state $q$, its ε-closure is defined as:

$$\epsilon \text{-closure}(q)=\{p\in Q\mid q\stackrel{{\epsilon }^{\ast }}{\Rightarrow }p\}$$

Examples

Basic NFA Example