A DFA (Deterministic Finite Automaton) is a theoretical machine where:
- Each input symbol leads to exactly one next state
- No ε-transitions (empty moves) are allowed
- Every state must have transitions for all input symbols
- It is deterministic and predictable
Formal Definition
A DFA is a 5-tuple:
D = (Q, Σ, δ, q₀, F)
Where:
- Q → set of states
- Σ → input alphabet
- δ → transition function
- q₀ → start state
- F → final/accepting states
Let discuss major examples of DFA
DFA Example 1: DFA for Strings Ending with 01
This is one of the most common DFA examples.
Language:
All binary strings that end with 01.
Idea:
To accept the string, the last two bits must be 0 → 1.
States Description
- q0: Starting state
- q1: Last input was 0
- q2: Last two inputs were 01 (Final state)
Transition Table
| State | 0 | 1 |
| q0 | q1 | q0 |
| q1 | q1 | q2 |
| q2 | q1 | q0 |
Final State: q2
This DFA accepts: 01, 101, 1001, 0001, etc.
DFA Example 2: DFA for Strings Containing Even Number of 1s
Language:
All strings with even number of 1s.
Idea:
Count the number of 1s modulo 2.
States
- q0 → even number of 1s (Final state)
- q1 → odd number of 1s
Transition Table
| State | 0 | 1 |
| q0 | q0 | q1 |
| q1 | q1 | q0 |
Final State: q0
This DFA accepts strings like:
ε, 0, 00, 11, 1010, 1100, 1001, etc.
DFA Example 3: DFA for Strings With No Two Consecutive 1s
Language:
All binary strings where 11 does not appear.
States
- q0 → no 1 seen or last is 0
- q1 → last input was 1
- qd → dead state (11 is found)
Transition Table
| State | 0 | 1 |
| q0 | q0 | q1 |
| q1 | q0 | qd |
| qd | qd | qd |
Final States: q0, q1
This DFA accepts strings like:
0, 1, 10, 101, 1010, 01010, etc.
DFA Example 4: DFA for Strings Over {0,1} Divisible by 3 (Binary to Decimal Mod 3)
This is a very popular DFA in exams.
Idea:
Treat input as a binary number and track remainder mod 3.
States
- q0 → remainder 0
- q1 → remainder 1
- q2 → remainder 2
Transition Rule
For each bit b:
new_state = (old_state * 2 + b) mod 3
Transition Table
| State | 0 | 1 |
| q0 | q0 | q1 |
| q1 | q2 | q0 |
| q2 | q1 | q2 |
Final State: q0
Examples accepted:
0, 11 (3), 110 (6), 1001 (9), 1100 (12), etc.
DFA Example 5: DFA for Strings Starting with 1
Language:
All binary strings that start with 1.
States
- q0 → start state
- q1 → first symbol was 1 (final)
- qd → dead state
Transition Table
| State | 0 | 1 |
| q0 | qd | q1 |
| q1 | q1 | q1 |
| qd | qd | qd |
Final State: q1
Examples accepted:
1, 10, 101, 1000, 111, etc.
Conclusion
Deterministic Finite Automata (DFA) play a major role in theoretical computer science and real-world computing. The examples above cover the most commonly used DFA patterns — including strings ending with specific patterns, counting characters, avoiding patterns, and number divisibility.
This DFA is frequently used in theory-of-computation exams because it is simple, intuitive, and perfectly illustrates how deterministic finite automata track specific patterns within input strings. The DFA has two states: q₀, which represents that the number of 1s read so far is even, and q₁, which represents that the number is odd. The machine starts in q₀, since before reading any input, the count of 1s is zero, which is even. Whenever the DFA reads a 0, it remains in the same state, because zeros do not affect whether the number of 1s is even or odd. However, each time it reads a 1, it flips to the other state, effectively toggling between even and odd. The accepting state is q₀, meaning the input is accepted only if it ends with an even number of 1s. This DFA is popular because it clearly demonstrates state-based memory and parity checking.
