DFA Construction, NFA Conversion & Minimization

A Deterministic Finite Automaton (DFA) is a 5-tuple M = (Q, \Sigma, \delta, q_0, F), where:

1. Q: A finite, non-empty set of internal states.

2. \Sigma: A finite alphabet of input symbols.

3. \delta: The transition function mapping Q × \Sigma \to Q (strictly deterministic: exactly one next state for every state-symbol pair).

4. q_0 \in Q: The unique initial start state.

5. F \subseteq Q: The set of accepting (final) states.

Language of a DFA:

L(M) = { w \in \Sigma^ \mid \delta^(q_0, w) \in F }, where \delta^ is the extended transition function defined inductively by \delta^(q, \epsilon) = q and \delta^(q, wa) = \delta(\delta^(q, w), a).

NFA vs DFA Equivalence:

In a Non-deterministic Finite Automaton (NFA), the transition function maps Q × (\Sigma \cup {\epsilon}) \to 2^Q (the powerset of states). Every NFA with n states can be converted into an equivalent DFA via the Subset Construction Algorithm with at most 2^n states.

Two states p, q \in Q in a DFA are equivalent (p \equiv q) if for all strings w \in \Sigma^, \delta^(p, w) \in F \iff \delta^*(q, w) \in F. If there exists even one string w such that one state lands in F and the other lands outside F, the states are distinguishable.

Table-Filling Algorithm Steps:

1. Construct a lower triangular matrix for all state pairs (p, q) with p \ne q.

2. Base Step (0-equivalence): Mark pair (p, q) with an 'X' if one state is in F and the other is in Q \setminus F.

3. Inductive Step (k-equivalence): For each unmarked pair (p, q), examine each symbol a \in \Sigma. If the transition pair (\delta(p, a), \delta(q, a)) is already marked with 'X', mark (p, q) with 'X'.

4. Repeat Step 3 until a full pass makes zero new marks.

5. All remaining unmarked pairs are equivalent and can be merged into single compound states.