A DFA Examples with two states accepts binary strings containing an even number of 1s, switching states every time it reads

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

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

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

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

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

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.