- 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 is one of the most common examples used to illustrate a deterministic finite automaton, or DFA, in computer science. DFAs are theoretical machines that read strings of symbols from an alphabet and determine whether the string belongs to a particular language. In this example, the DFA typically has a small number of states, often including a start state, one or more accepting states, and transitions defined for each symbol in the alphabet. It is widely used in textbooks and lectures because it clearly demonstrates how DFAs work, showing how inputs are processed step by step to either accept or reject a string.
