Finite automata: DFA, NFA and equivalence notes — Unit 1

Automata Theory is the study of abstract computational devices (machines) and the mathematical problems they can and cannot solve. It is the absolute theoretical foundation of computer science, compiler design, and artificial intelligence.

Before we build a physical CPU, we must define mathematically what computation is. We start with the simplest possible mathematical machine (a Finite Automaton) and slowly add memory and capabilities until we reach the ultimate theoretical computer (the Turing Machine).

⇒1.1 Core Terminology

• Symbol: An abstract entity that has no meaning by itself. Examples: letters `a`, `b`, digits `0`, `1`, or even a picture. It is the atomic unit of data.
• Alphabet ($\Sigma$): A finite, non-empty set of symbols.
  Examples:
  - Binary Alphabet: $\Sigma = \{0, 1\}$
  - English Alphabet: $\Sigma = \{a, b, c, ..., z\}$
• String (or Word): A finite sequence of symbols chosen from a specific alphabet.
  Examples: If $\Sigma = \{0, 1\}$, valid strings are `001`, `10110`, `0`, etc.
• Length of a String ($|w|$): The total number of symbols in the string $w$. If $w = 1011$, then $|w| = 4$.
• Empty String ($\epsilon$ or $\lambda$): The unique string containing absolutely zero symbols. Its length is exactly 0. ($|\epsilon| = 0$). Do not confuse it with an empty set.

In computer science, a "Language" is not English or French. It is defined strictly mathematically.

⇒2.1 Powers of an Alphabet

If $\Sigma$ is an alphabet, we can define exponents of that alphabet:

• $\Sigma^0 = \{\epsilon\}$ (The set containing only the empty string).
• $\Sigma^1 = \Sigma$ (The set of all strings of length 1).
• $\Sigma^2 =$ The set of all strings of length exactly 2. If $\Sigma = \{0, 1\}$, then $\Sigma^2 = \{00, 01, 10, 11\}$.
• $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...$ (The Kleene Star). This is the infinite set of ALL possible strings of ALL possible lengths that can be formed using $\Sigma$, including the empty string $\epsilon$.

⇒2.2 Definition of a Language

A Language $L$ over an alphabet $\Sigma$ is simply any subset of $\Sigma^*$.

Languages can be finite or infinite.
Example 1 (Finite): $L_1 = \{\text{All strings of length 2}\} = \{00, 01, 10, 11\}$.
Example 2 (Infinite): $L_2 = \{\text{All strings that start with '1'}\} = \{1, 10, 11, 100, ...\}$.

The core problem of Automata Theory is this: Given an infinite language $L$ and a specific string $w$, build a mathematical machine that can definitively answer "YES" or "NO" to the question: "Does string $w$ belong to Language $L$?"

The DFA is the simplest possible computational model. It has absolutely no memory (no stack, no hard drive) other than knowing exactly which single "State" it is currently in.

It reads a string character by character from left to right. It cannot go backward, and it cannot look ahead.

⇒3.1 Formal 5-Tuple Definition

A DFA is strictly defined as a 5-tuple: $M = (Q, \Sigma, \delta, q_0, F)$

• $Q$: A finite, non-empty set of internal states. (e.g., $Q = \{q_0, q_1, q_2\}$).
• $\Sigma$: A finite set of input symbols (The alphabet).
• $\delta$: The Transition Function. $\delta: Q \times \Sigma \rightarrow Q$. This is the brain of the machine. It takes the current state and the current input symbol, and definitively returns exactly ONE next state.
• $q_0$: The Initial (Start) state. It must be an element of $Q$. There is only ever exactly one start state.
• $F$: A set of Final (Accepting) states. $F \subseteq Q$. There can be zero, one, or multiple final states.

⇒4.1 How it Computes

1. The machine always starts in state $q_0$.
2. It reads the first symbol of the input string.
3. It uses the transition function $\delta$ to determine the next state.
4. It repeats this process until the string is completely exhausted.
5. Acceptance Rule: If, after reading the very last symbol, the machine stops inside a state that belongs to the set $F$, the string is ACCEPTED. If it stops in any non-final state, the string is REJECTED.

⇒4.2 The Meaning of "Deterministic"

The 'D' in DFA is critical. It implies strict, absolute certainty.

For every single state in $Q$, and for every single symbol in $\Sigma$, there must exist exactly one transition. You cannot have two transitions leaving the same state on the same symbol. You cannot have zero transitions (a dead end) for a valid symbol. The machine must always know exactly what to do.

While the 5-tuple is mathematically rigorous, humans prefer visual representations. A Transition Diagram is a directed graph that perfectly represents a DFA.

⇒5.1 Diagram Notations

• States: Represented by circles containing the state name ($q_0$).
• Start State: Represented by a circle with an incoming arrow that originates from nothing (no source node).
• Final States: Represented by a Double Circle.
• Transitions: Represented by directed arrows between states, labeled with the input symbol that triggers the movement.

⇒5.2 Designing DFAs: The Trap State

Because a DFA must be deterministic, every state must have an outgoing arrow for every alphabet symbol. What if the language requires a string to start with '0', but the user inputs a '1'?

We must explicitly draw a Dead State (Trap State). If the user inputs invalid data, the transition points to this Dead State. The Dead State loops back to itself for every possible input symbol. Once you enter the Dead State, you can never leave, and it is never a Final State. The string is permanently doomed to be rejected.

A DFA models realistic computer hardware. An NFA introduces a magical, theoretical concept: Nondeterminism (guessing).

In an NFA, the strict rules of the DFA are completely shattered.

⇒6.1 Breaking the Rules

• From a single state, you can have multiple arrows leaving with the exact same input symbol. The machine can be in multiple states simultaneously (like quantum superposition).
• You can have zero arrows for a symbol. If the machine reads that symbol, that specific branch of computation simply dies (crashes).

⇒6.2 The Formal Definition

An NFA is also a 5-tuple: $M = (Q, \Sigma, \delta, q_0, F)$.
The only mathematical difference is the transition function $\delta$.

DFA: $\delta: Q \times \Sigma \rightarrow Q$ (Outputs exactly 1 state).
NFA: $\delta: Q \times \Sigma \rightarrow 2^Q$ (Outputs a subset of states, using the Power Set $2^Q$). The output could be empty $\emptyset$, one state, or multiple states.

How does a machine that "guesses" determine if a string is accepted? It doesn't trace a single line; it traces a massive branching tree of all possible parallel realities.

⇒7.1 The Computation Tree

When an NFA encounters multiple transitions for the same symbol, it splits itself into multiple copies, and each copy follows a different path simultaneously.

If a copy encounters a symbol with no defined transition, that copy instantly dies and is removed from the tree.

⇒7.2 The NFA Acceptance Rule

An NFA accepts a string $w$ if and only if AT LEAST ONE branch of the computation tree survives to the end of the string AND lands in a Final State. It does not matter if a million other branches died or landed in non-final states. If even a single path to a final state exists, the NFA magically 'guesses' that correct path and accepts the string.

NFAs are significantly easier for humans to design because you don't have to worry about trap states or deterministic constraints. But can you actually build an NFA out of physical silicon chips? No.

This raises the most critical theorem of Unit 1:

Theorem: Every language accepted by an NFA can also be accepted by a DFA. Therefore, NFAs and DFAs have the exact same mathematical computing power. Nondeterminism adds zero fundamental capability; it is merely a convenience.

⇒8.1 Subset Construction Algorithm

We prove this equivalence using the Subset Construction algorithm, which algorithmically converts any NFA into a perfect, deterministic DFA.

The core idea: If an NFA has $k$ states, it can be in any subset of those states simultaneously. There are exactly $2^k$ possible subsets. The new DFA will treat each of these subsets as a single, massive, deterministic state.

⇒9.1 The Algorithm

Assume we have an NFA with states $Q_{NFA}$. We are building a DFA with states $Q_{DFA}$.

• 1. The start state of the new DFA is the set containing only the start state of the NFA: $\{q_0\}$.
• 2. For this new subset state $\{q_0\}$, look at the input symbol '0'. In the original NFA, where can $q_0$ go on '0'? Let's say it can go to $q_0$ and $q_1$.
  The output is the union of these destinations: $\{q_0, q_1\}$.
• 3. $\{q_0, q_1\}$ is a completely new state in our DFA. We draw a single, deterministic arrow from $\{q_0\}$ to $\{q_0, q_1\}$ on input '0'.
• 4. Now we must evaluate this new state $\{q_0, q_1\}$. For input '1', we check where $q_0$ goes on '1', and where $q_1$ goes on '1', and take the union of all destinations. This might create another new state, or point to an existing one.
• 5. Repeat this process recursively until no new subsets are generated.
• 6. Final States: Any subset state in the new DFA that contains at least one final state from the original NFA becomes a Final State in the DFA.

We can push the boundaries of nondeterminism even further. An $\epsilon$-NFA is an NFA that is allowed to change its state spontaneously, completely for free, without reading any input symbol at all. This is called an $\epsilon$-transition.

⇒10.1 The Epsilon Closure ($\epsilon$-closure)

To analyze an $\epsilon$-NFA, we must define the epsilon closure of a state $q$, denoted as $\epsilon\text{-closure}(q)$.

The $\epsilon$-closure of a state $q$ is the set of all states that can be reached from $q$ by following zero or more $\epsilon$-transitions exclusively.

Rule: A state is ALWAYS in its own $\epsilon$-closure, because you can reach yourself by taking zero transitions. (e.g., $q_0 \in \epsilon\text{-closure}(q_0)$).

If there is an $\epsilon$-arrow from $q_0$ to $q_1$, and an $\epsilon$-arrow from $q_1$ to $q_2$, then $\epsilon\text{-closure}(q_0) = \{q_0, q_1, q_2\}$. If the machine is in $q_0$, it is simultaneously magically in $q_1$ and $q_2$ before reading a single character of input.

Despite allowing spontaneous, zero-input state changes, an $\epsilon$-NFA is still not mathematically more powerful than a standard DFA. We can convert it using an extended version of the Subset Construction algorithm.

⇒11.1 The Extended Transition Function ($\delta^*$)

To process a symbol 'a' in an $\epsilon$-NFA, the machine actually does three things:

• 1. It takes all possible free $\epsilon$-transitions before reading the symbol.
• 2. It actually reads the symbol 'a' and transitions.
• 3. It takes all possible free $\epsilon$-transitions after reading the symbol.

Mathematically: $\delta^*(q, a) = \epsilon\text{-closure}( \delta(\epsilon\text{-closure}(q), a) )$

⇒11.2 The Conversion Algorithm

1. The start state of the new DFA is NOT just $\{q_0\}$. It is the $\epsilon\text{-closure}(q_0)$.
2. For this new starting subset, calculate transitions using the complex $\delta^*$ formula above for every alphabet symbol.
3. Repeat for all newly generated subsets until closure is achieved.
4. Any subset containing an original final state is a final state.

Subset construction often produces a DFA with dozens of unnecessary, redundant states. In hardware, every state requires physical transistors. We must minimize the DFA to use the absolute minimum number of states necessary to recognize the language.

⇒12.1 The Myhill-Nerode Theorem / Equivalence Theorem

Two states $p$ and $q$ are considered mathematically equivalent (and thus can be merged into a single state) if and only if, for EVERY possible string $w \in \Sigma^*$, feeding $w$ into state $p$ and feeding $w$ into state $q$ yields the exact same result (either both end in an accepting state, or both end in a rejecting state).

If there exists even a single string $w$ that makes $p$ accept but $q$ reject, then $p$ and $q$ are distinguishable and absolutely cannot be merged.

This algorithmic process systematically identifies and merges equivalent states.

⇒13.1 Step-by-Step

• 1. Draw a massive staircase table comparing every state against every other state. (e.g., cell $(q_1, q_0)$).
• 2. Base Case: Immediately place an 'X' (distinguishable) in every cell that pairs a Final State with a Non-Final State. A final state can never, ever be equivalent to a non-final state.
• 3. Iteration: Loop through all empty cells $(p, q)$. For every alphabet symbol 'a', check the transitions: where does $p$ go on 'a' (let's call it $p'$), and where does $q$ go on 'a' (let's call it $q'$).
• 4. Check the cell $(p', q')$ in the table. If $(p', q')$ already has an 'X', then $p$ and $q$ are distinguishable. Place an 'X' in cell $(p, q)$.
• 5. Repeat the entire iteration through the table until a full pass occurs without placing a single new 'X'.
• 6. Any cells that remain empty represent mathematically equivalent states. Merge them together in the final diagram.

Unit 1 sets the rules. You must master the 5-tuple definitions and the physical drawing of transition diagrams.

⇒14.1 University Exam Checklist

• Define Alphabet, String, Language, and the Kleene Star ($\Sigma^*$).
• Write the formal 5-tuple mathematical definition of a DFA.
• Design a DFA (draw the transition diagram) for the language of strings over {0,1} that end with '101'.
• Design a DFA for the language of strings over {a,b} where the number of 'a's is even and the number of 'b's is odd.
• Write the formal 5-tuple definition of an NFA. How does its transition function differ from a DFA?
• Explain the concept of NFA acceptance via a computation tree.
• Algorithmically convert a given NFA into a DFA using the Subset Construction method. Show the state mapping table.
• Compute the $\epsilon$-closure for all states in a given $\epsilon$-NFA.
• Convert an $\epsilon$-NFA to a DFA using the extended transition function.
• Minimize a given DFA using the Table-Filling (Myhill-Nerode) algorithm and draw the minimized machine.