Deterministic Finite Automata

What is a DFA?

A Deterministic Finite Automaton (DFA) is a theoretical machine (or mathematical model) that reads an input string symbol by symbol and decides whether to accept or reject it based on a set of predefined rules. It’s called “deterministic” because from any state, for any input symbol, there is exactly one next state.

Formal Definition

A DFA is a 5-tuple M = (Q, Σ, δ, q₀, F) where:

  • Q: Finite set of states
  • Σ: Finite input alphabet
  • δ: Transition function δ: Q × Σ → Q
  • q₀: Start state (q₀ ∈ Q)
  • F: Set of accepting/final states (F ⊆ Q)

Simple Analogy

Think of a DFA like a vending machine:

  • States: Different modes (waiting, selecting, dispensing)
  • Alphabet: Buttons and coin inputs
  • Transitions: What happens when you press a button
  • Start state: Initial waiting mode
  • Accept states: Successfully dispensed item
  • Reject states: Error or insufficient funds

The machine is in exactly one state at a time, and each input causes a deterministic transition to the next state.

Components of a DFA

1. States (Q)

Finite set of internal configurations.

Example: Q = {q₀, q₁, q₂}

  • q₀: Start state
  • q₁: Intermediate state
  • q₂: Accept state

2. Alphabet (Σ)

Finite set of input symbols.

Examples:

  • Σ = {0, 1} (binary)
  • Σ = {a, b, c}
  • Σ = {A-Z, 0-9}

3. Transition Function (δ)

Defines how the DFA moves between states.

Format: δ(current_state, input_symbol) = next_state

Example:

δ(q₀, 0) = q₁
δ(q₀, 1) = q₀
δ(q₁, 0) = q₁
δ(q₁, 1) = q₂

4. Start State (q₀)

The state where computation begins.

Notation: Indicated by an arrow → pointing to it

5. Accept States (F)

States that indicate acceptance of the input.

Notation: Drawn with double circles (( ))

Example: F = {q₂}

How a DFA Works

Execution Process:

  1. Start: Begin in state q₀
  2. Read: Read input symbol by symbol from left to right
  3. Transition: Use δ to move to next state
  4. Repeat: Continue until all input is consumed
  5. Accept/Reject:
    • If final state ∈ F → Accept
    • If final state ∉ F → Reject

Example Trace:

DFA for strings ending in ‘1’:

Q = {q₀, q₁}
Σ = {0, 1}
q₀ = start state
F = {q₁}

Transitions:
δ(q₀, 0) = q₀
δ(q₀, 1) = q₁
δ(q₁, 0) = q₀
δ(q₁, 1) = q₁

Input: “0101”

Step 0: q₀ (start)
Step 1: q₀ --0--> q₀
Step 2: q₀ --1--> q₁
Step 3: q₁ --0--> q₀
Step 4: q₀ --1--> q₁ ✓ (accept state)

Result: ACCEPT

Input: “010”

Step 0: q₀ (start)
Step 1: q₀ --0--> q₀
Step 2: q₀ --1--> q₁
Step 3: q₁ --0--> q₀ ✗ (non-accept state)

Result: REJECT

Representing DFAs

1. State Diagram (Graph)

Visual representation with circles and arrows.

Example: Strings ending with ‘01’

     0       1       1
→(q₀)─→(q₁)─→((q₂))
  ↑ ↺      ↺       │
  └───────────0────┘

Legend:

  • → : Start state arrow
  • ( ) : Regular state
  • (( )) : Accept state (double circle)
  • Arrows with labels: Transitions

2. Transition Table

Tabular representation of δ function.

Example: Same DFA as above

StateInput 0Input 1
→q₀q₁q₀
q₁q₁q₂
q₂q₁q₀

Legend:

  • → : Start state
    • : Accept state

3. Formal 5-Tuple

Mathematical notation:

M = (Q, Σ, δ, q₀, F)

Q = {q₀, q₁, q₂}
Σ = {0, 1}
q₀ = start state
F = {q₂}
δ as defined in table above

Examples of DFAs

Example 1: Accept Strings Starting with ‘a’

Language: L = {w | w starts with ‘a’}

DFA:

Σ = {a, b}
Q = {q₀, q₁, q₂}
F = {q₁}

State Diagram:
      a
→(q₀)─→((q₁))
  │      ↺ a,b
  b
  ↓
 (q₂)─↺ a,b

Transition Table:

Stateab
→q₀q₁q₂
q₁q₁q₁
q₂q₂q₂

Example 2: Even Number of 0’s

Language: L = {w | w has even number of 0’s}

DFA:

Σ = {0, 1}
Q = {q_even, q_odd}
F = {q_even}

State Diagram:
         0
→((q_even))⇄(q_odd)
    ↺ 1         ↺ 1

Transition Table:

State01
→q_evenq_oddq_even
q_oddq_evenq_odd

Examples:

  • “11” → q_even (ACCEPT)
  • “01” → q_odd (REJECT)
  • “0101” → q_even (ACCEPT)

Example 3: Strings Containing Substring “ab”

Language: L = {w | w contains “ab” as substring}

DFA:

Σ = {a, b}
Q = {q₀, q₁, q₂}
F = {q₂}

State Diagram:
      a       b
→(q₀)─→(q₁)─→((q₂))
  ↺ b    ↺ a    ↺ a,b

Explanation:

  • q₀: Haven’t seen ‘a’ yet
  • q₁: Seen ‘a’, waiting for ‘b’
  • q₂: Seen “ab”, stay here (found!)

Example 4: Binary Multiples of 3

Language: L = {binary numbers divisible by 3}

DFA:

Σ = {0, 1}
Q = {q₀, q₁, q₂} (remainders 0, 1, 2)
F = {q₀}

Transition Table:
| State | 0 | 1 |
|-------|---|---|
| →*q₀* | *q₀* | q₁ |
| q₁    | q₂ | *q₀* |
| q₂    | q₁ | q₂ |

Logic: Track remainder when dividing by 3

  • Reading ‘0’: remainder × 2 mod 3
  • Reading ‘1’: (remainder × 2 + 1) mod 3

Example 5: Exactly Two a’s

Language: L = {w | w has exactly 2 a’s}

DFA:

Σ = {a, b}
Q = {q₀, q₁, q₂, q₃}
F = {q₂}

State Diagram:
      a       a
→(q₀)─→(q₁)─→((q₂))
  ↺ b    ↺ b    │ ↺ b
                │ a
                ↓
              (q₃) ↺ a,b

Explanation:

  • q₀: 0 a’s seen
  • q₁: 1 a seen
  • q₂: 2 a’s seen (accept)
  • q₃: 3+ a’s seen (reject - dead state)

Example 6: Odd Length Strings

Language: L = {w | |w| is odd}

DFA:

Σ = {0, 1}
Q = {q_even, q_odd}
F = {q_odd}

State Diagram:
           0,1
→(q_even)⇄((q_odd))

Simple: Just toggle between even/odd on each symbol!

Properties of DFAs

1. Determinism

Key Property: From any state, on any input symbol, there is exactly one next state.

For all q ∈ Q and a ∈ Σ:
δ(q, a) is uniquely defined

This means:

  • No ambiguity
  • No choices to make
  • Execution path is unique

2. Completeness

Total Function: δ must be defined for every (state, symbol) pair.

If not naturally complete: Add a dead state (reject state) to handle undefined transitions.

Example:

Original: Missing transitions from q₁

Complete: Add dead state q_dead
δ(q₁, undefined_symbols) = q_dead
δ(q_dead, all_symbols) = q_dead

3. Memory Limitation

Finite States: DFA has fixed, finite number of states.

Cannot remember:

  • Unbounded counts
  • Arbitrary-length patterns
  • Nested structures

Can remember:

  • Fixed patterns
  • Counts modulo fixed number
  • Last few symbols (up to state limit)

4. Linear Time Recognition

Time Complexity: O(n) where n = input length

Each symbol processed in constant time:

  1. Look up current state and input symbol
  2. Move to next state
  3. Repeat

Space Complexity: O(1) - only need to store current state

Language Accepted by DFA

Formal Definition

The language accepted by DFA M = (Q, Σ, δ, q₀, F) is:

L(M) = {w ∈ Σ* | δ*(q₀, w) ∈ F}

Where δ* is the extended transition function for strings

Extended Transition Function (δ*)

Defined recursively:

δ*(q, ε) = q (base case: empty string)
δ*(q, wa) = δ(δ*(q, w), a) (recursive: string + symbol)

Meaning: δ*(q, w) is the state reached from q after reading string w

Example:

δ*(q₀, "01") = δ(δ*(q₀, "0"), 1)
             = δ(δ(q₀, 0), 1)
             = δ(q₁, 1)
             = q₂

Designing DFAs

Strategy 1: Track Required Information

Question: What do I need to remember?

Example: “Strings ending with ‘01’”

  • Need to remember: Last 2 symbols
  • States: Haven’t seen 0, seen 0, seen 01

Strategy 2: Use States as Counters

Example: “Even number of a’s”

  • States: even_count, odd_count
  • Toggle on each ‘a’

Strategy 3: Modular Arithmetic

Example: “Binary numbers divisible by 3”

  • States: remainder 0, 1, 2
  • Update: new_remainder = (old × 2 + bit) mod 3

Strategy 4: Progress Tracking

Example: “Contains substring ‘abc’”

  • States: Not started, seen ‘a’, seen ‘ab’, seen ‘abc’
  • Progress through pattern

Common Patterns:

  1. Prefix: Track first few symbols
  2. Suffix: Track last few symbols
  3. Count Parity: Even/odd counter
  4. Substring: Pattern matching progress
  5. Modulo: Divisibility checking

Minimizing DFAs

Problem: DFA may have unnecessary states.

Goal: Find equivalent DFA with minimum number of states.

Equivalent States

Two states p and q are equivalent if:

For all strings w ∈ Σ*:
δ*(p, w) ∈ F ⟺ δ*(q, w) ∈ F

Meaning: From p and q, all strings lead to same accept/reject decision.

Minimization Algorithm

  1. Partition states into accepting and non-accepting
  2. Refine partitions: Split groups that behave differently
  3. Repeat until no more splits possible
  4. Merge equivalent states

Result: Unique minimal DFA (up to state renaming)

Example:

Before:

5 states: q₀, q₁, q₂, q₃, q₄

After minimization:

3 states: {q₀}, {q₁, q₃}, {q₂, q₄}

DFA Limitations

Cannot Recognize:

  1. {aⁿbⁿ | n ≥ 0} - Equal a’s and b’s

    • Reason: Need to count unboundedly

  2. {w wᴿ | w ∈ Σ*} - Palindromes

    • Reason: Need to remember first half

  3. {aⁿ | n is prime} - Prime lengths

    • Reason: Primality requires computation

  4. Balanced parentheses

    • Reason: Need stack (nesting depth)

These require more powerful models: PDA, Turing Machine

Practical Applications

1. Lexical Analyzers

Identifier: [a-zA-Z][a-zA-Z0-9]*
DFA recognizes valid variable names

2. Protocol Validators

TCP state machine:
CLOSED → SYN_SENT → ESTABLISHED → FIN_WAIT → CLOSED

3. String Matching

Knuth-Morris-Pratt (KMP) algorithm
Uses DFA for pattern matching

4. Hardware Controllers

Traffic lights, elevators, vending machines
Implemented as finite state machines

5. Game AI

NPC behavior:
IDLE → ALERT → CHASE → ATTACK → RETREAT

Important Exam Points

  1. ✓ DFA = (Q, Σ, δ, q₀, F) - five components
  2. ✓ Deterministic: Exactly one transition per (state, symbol)
  3. ✓ Complete: δ defined for all (state, symbol) pairs
  4. ✓ Recognition: O(n) time, O(1) space
  5. ✓ Accept: If final state ∈ F after reading input
  6. ✓ Reject: If final state ∉ F
  7. ✓ Minimization: Unique minimal DFA exists
  8. ✓ Limitations: Cannot count unboundedly or match nested structures
  9. ✓ Equivalent to: NFA, Regular expressions, Regular grammars
  10. ✓ Graphical: States = circles, accepting = double circles, start = arrow

Common Mistakes to Avoid

✗ Mistake 1: Missing transitions (incomplete δ)
✓ Correct: Add dead state for completeness

✗ Mistake 2: Multiple transitions for same (state, symbol)
✓ Correct: That’s NFA, not DFA!

✗ Mistake 3: ε-transitions in DFA
✓ Correct: DFA cannot have ε-transitions

✗ Mistake 4: Forgetting start state arrow
✓ Correct: Always mark start state with →

✗ Mistake 5: Single circle for accept state
✓ Correct: Use double circles (( ))

✗ Mistake 6: DFA can count to any number
✓ Correct: Only finite memory (fixed states)

Practice Questions

Q1: Design DFA for strings with odd number of 1’s.

Answer: 2 states (even/odd), toggle on each 1, accept odd state.

Q2: How many states minimum for “contains substring ‘abc’”?

Answer: 4 states (none, seen ‘a’, seen ‘ab’, seen ‘abc’)

Q3: Can DFA recognize {aⁿbⁿ | n ≥ 0}?

Answer: No, requires counting which needs infinite states.

Q4: What is time complexity of DFA recognition?

Answer: O(n) where n = input string length

Q5: How to make incomplete DFA complete?

Answer: Add a dead/trap state for missing transitions.

Q6: Are two DFAs with different number of states equivalent?

Answer: Yes, if they accept the same language (one may be non-minimal).

Q7: Design DFA for binary numbers divisible by 2.

Answer: 2 states, accept if string ends with ‘0’.

Q8: Can DFA have ε-transitions?

Answer: No, ε-transitions are only in NFAs.

Summary

  • DFA = Deterministic Finite Automaton
  • Five components: Q, Σ, δ, q₀, F
  • Deterministic: Exactly one transition per (state, symbol) pair
  • Complete: Total function - defined for all inputs
  • Linear time: O(n) recognition, O(1) space
  • Representations: State diagram, transition table, 5-tuple
  • Minimization: Unique minimal equivalent DFA exists
  • Limitations: Cannot count unboundedly or recognize nested structures
  • Equivalent to: NFA, Regular expressions (Kleene’s Theorem)
  • Applications: Lexical analysis, protocol validation, pattern matching

DFAs are fundamental computational models that balance simplicity with practical utility, forming the foundation for regular language recognition!