Types of Finite Automata

Deterministic Finite Automata (DFA)

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

• $Q$: Finite set of states
• $\Sigma$: Input alphabet
• $\delta$: Transition function $\delta: Q \times \Sigma \rightarrow Q$
• $q_0$: Start state ($q_0 \in Q$)
• $F$: Set of accept states ($F \subseteq Q$)

Important

In a DFA, for every state and input symbol, there is exactly one next state.

Nondeterministic Finite Automata (NFA)

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

• $Q$: Finite set of states
• $\Sigma$: Input alphabet
• $\delta$: Transition function $\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow \mathcal{P}(Q)$
• $q_0$: Start state ($q_0 \in Q$)
• $\boldsymbol{F}$: Set of accept states ($F \subseteq Q$)

Tips

NFAs can have:

• Multiple transitions for the same symbol from a state
• $\epsilon$-transitions (moves without reading input)

Equivalence of DFA and NFA

Theorem: For every NFA, there exists an equivalent DFA that recognizes the same language.

Subset Construction Method

The standard algorithm to convert an NFA to a DFA:

1. Start with the $\epsilon$-closure of the NFA's start state
2. For each state in the DFA, compute transitions for each input symbol
3. A DFA state is accepting if it contains any NFA accept state
4. Continue until no new states are generated

Regular Expressions to Automata

Thompson's Construction

A systematic method to convert regular expressions to NFAs:

Base case: Handle $\emptyset$, $\epsilon$, and single symbols

Inductive case: Handle union, concatenation, and Kleene star

Base Cases

Regular Expression	NFA Construction
$\emptyset$	Single state, no transitions
$\epsilon$	Single state with $\epsilon$-transition to accept state
$a \in \Sigma$	Two states with transition labeled 'a'

Inductive Cases

1. Union $(r_1 + r_2)$:

   • Create new start and accept states
   • Add $\epsilon$-transitions from new start to $r_1$ and $r_2$ starts
   • Add $\epsilon$-transitions from $r_1$ and $r_2$ accepts to new accept

2. Concatenation $(r_1 \cdot r_2)$:

   • Connect accept state of $r_1$ to start state of $r_2$ with $\epsilon$-transition

3. Kleene Star $(r_1^*)$:

   • Create new start/accept state
   • Add $\epsilon$-transitions:
     • From new start to $r_1$ start
     • From $r_1$ accept to new accept
     • From $r_1$ accept back to $r_1$ start
     • From new start to new accept (empty string case)

Minimization of DFAs

Equivalence Relations

Two states $p$ and $q$ are equivalent if for all strings $w$:

• $\delta^*(p, w) \in F$ if and only if $\delta^*(q, w) \in F$

Myhill-Nerode Theorem

Theorem: A language $L$ is regular if and only if the relation $\equiv_L$ has finite index.

The minimal DFA for $L$ has exactly as many states as there are equivalence classes of $\equiv_L$.

Minimization Algorithm

1. Initial Partition: Separate states into accept and non-accept states
2. Refinement: For each group, split based on transition behavior
3. Repeat: Continue refinement until no more splits are possible
4. Merge: States in the same final group are equivalent and can be merged

Practical Examples

Example 1: DFA for Even Number of 'a's

States: {q0, q1}
Alphabet: {a, b}
Start: q0
Accept: {q0}

Transitions:
δ(q0, a) = q1
δ(q0, b) = q0  
δ(q1, a) = q0
δ(q1, b) = q1

Example 2: NFA for $(a + b)^*aa(a + b)^*$

This NFA recognizes strings containing "aa" as a substring.

Example 3: Full NFA → DFA walkthrough for contains aa

1. Start DFA state {q0}
2. From {q0}: on a → {q1}, on b → {q0}
3. From {q1}: on a → {q2} (accept), on b → {q0}
4. From {q2}: on a/b → {q2} (stay accepting)
5. Minimal already (absorbing accept captures substring seen)

Key Theorems

Kleene's Theorem

Theorem: A language is regular if and only if it is recognized by some finite automaton (DFA or NFA).

Equivalence of Models

All the following are equivalent for a language $L$:

1. $L$ is regular (described by a regular expression)
2. $L$ is recognized by a DFA
3. $L$ is recognized by an NFA
4. $L$ is recognized by an $\epsilon$-NFA
5. The complement of $L$ is regular
6. $L$ has a pumping length satisfying the pumping lemma

Applications

Regular expressions and finite automata are used in:

• Lexical analysis: Compilers use DFAs to tokenize source code
• Text search: Pattern matching in editors and search engines
• Network protocols: State machines in protocol implementation
• Digital circuits: Finite state machines in hardware design

Warning

While NFAs are often easier to construct and understand, DFAs are generally more efficient for actual implementation since they have no nondeterminism.

Generalized Nondeterministic Finite Automata (GNFA)

Definition

A GNFA is a variant of NFA where:

• Transitions are labeled with regular expressions (not just symbols)
• Exactly one start state (no incoming transitions)
• Exactly one accept state (no outgoing transitions)
• All other states have transitions to every other state (except start and accept)

GNFA to Regular Expression Conversion

Algorithm:

1. Convert NFA to GNFA by adding new start and accept states
2. Eliminate states one by one (except start and accept)
3. When eliminating state $q_{rip}$, update transitions:
   • For every pair of states $q_i$ and $q_j$:
   • Replace $R_{ij}$ with $R_{ij} + R_{i,rip} \cdot (R_{rip,rip})^* \cdot R_{rip,j}$
4. Final expression is the transition from start to accept state

This provides a systematic way to convert any finite automaton to a regular expression.

Worked State-Elimination Example (Tiny DFA)

DFA

Recognizes strings over {a,b} ending with a.

States: {q0 (start), q1 (accept)}

Transitions:

• q0 --a--> q1, q0 --b--> q0
• q1 --a--> q1, q1 --b--> q0

Convert to GNFA

Add new start s (ε→q0) and new accept t (ε from q1→t). Label parallel edges with regex using + to combine.

Eliminate q0

Update edges with R_{ij} + R_{i0} (R_{00})^* R_{0j}. Self-loop on q0 is b.

Eliminate q1

Include its self-loop a when updating. Final edge s→t yields a regex equivalent to (a + ba)^* a.

Tips

For “ends with a” languages, a compact regex is (a + ba)^* a.

Testing Properties of Regular Languages

Automata Constructions (Closure by Construction)

Union (NFA)

New start with ε-edges to both NFAs’ starts; accept if either branch accepts.

Union/Intersection (DFA)

Product DFA on Q1×Q2; accept on F1 ∪ F2 or F1 ∩ F2 respectively.

Complement (DFA)

Ensure total DFA (add dead state if needed), then swap accept and non-accept.

Difference

L1 \ L2 = L1 ∩ \overline{L2} using product and complement.

Emptiness Testing

Problem: Given a DFA $M$, is $L(M) = \emptyset$?

Algorithm: Check if any accept state is reachable from the start state

• Time Complexity: $O(|Q| + |\delta|)$ using DFS or BFS

Equivalence Testing

Problem: Given DFAs $M_1$ and $M_2$, is $L(M_1) = L(M_2)$?

Algorithm:

1. Construct DFA for $(L(M_1) \cap \overline{L(M_2)}) \cup (L(M_2) \cap \overline{L(M_1)})$
2. Test if this language is empty
3. If empty, then $L(M_1) = L(M_2)$

Summary

The equivalence between regular expressions and finite automata provides a powerful theoretical foundation for pattern recognition. Regular expressions offer a concise descriptive language, while finite automata provide an efficient computational model. This equivalence enables both theoretical analysis and practical implementation of pattern matching systems.

The systematic conversion algorithms (Thompson's construction for regex→NFA, subset construction for NFA→DFA, and GNFA method for automata→regex) complete the circle of equivalence and provide practical tools for implementation.

Problem-Solving Skills: Construction Templates

Regex → NFA (Thompson)

Recipe for operators:

• Literal a: two states with an a-edge
• Union r + s: new start with ε to each; each accept ε to new accept
• Concat rs: ε from r’s accept to s’s start
• Star r^*: new start=accept, ε to r start, r accept ε back and ε to accept

NFA → DFA (Subset)

Steps:

1. Start with ε-closure of NFA start
2. For each DFA state S and symbol a, go to ε-closure(δ(S,a))
3. Mark accepting if S contains any NFA accept
4. Repeat until closed

DFA Minimization

Partition refinement:

1. Split into Accept vs Non-accept
2. Refine by distinguishing transitions per symbol
3. Merge indistinguishable states

Worked Examples

Build DFA for strings over {0,1} with no substring11

Strategy: Track whether last symbol was 1.

States: q0 (last≠1), q1 (last=1), qd (dead)

Transitions:

• From q0: on 0→q0, on 1→q1
• From q1: on 0→q0, on 1→qd
• From qd: on 0/1→qd

Accept: {q0, q1}

Convert regex(ab + b)^* a to NFA (sketch)

Use Thompson on union inside star, then concat with a.

Equivalence Proof Hints

Showing NFA and DFA recognize same language

Use induction on input length to show subset construction simulates all NFA paths and accepts iff some NFA path accepts.

Quick Patterns via Automata Intuition

• All strings with even number of a: two-state DFA → regex (b^* a b^* a)^* b^*
• Ends with 01: small DFA of tail length 2 → regex (0+1)^* 01

Tips

Designing the smallest DFA first often exposes a simpler equivalent regex.

Changelog

9/7/25, 2:51 AM

View All Changelog

• 87c17-web-deploy(Auto): Update base URL for web-pages branchon 9/7/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)