Course contentsShow
← Computer Science
Lesson 1781 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Designing Simple DFAs

Constructing DFAs for basic patterns like strings ending in '01' or containing an even number of 1s.

Designing Simple DFAs

What you'll learn: You'll learn how to systematically construct DFAs that recognize basic patterns like strings ending in '01' or containing an even number of 1s.

The Core Idea

Designing a DFA means translating a pattern or rule into a state machine. Each state represents "what you've seen so far that matters," and transitions guide you from state to state as you read input symbols. The key is identifying what information you need to track to decide whether to accept or reject.

Example 1: Strings Ending in '01'

To recognize strings ending in '01', track the last one or two characters:

  • State q₀ (start): Haven't seen anything useful yet
  • State q₁: Just saw a '0'
  • State q₂ (accept): Just saw '01'

From q₀: on '0' go to q₁, on '1' stay in q₀
From q₁: on '0' stay in q₁, on '1' go to q₂
From q₂: on '0' go to q₁, on '1' go to q₀

The string "1001" reaches q₂, so it's accepted.

Example 2: Even Number of 1s

Here you only need to track parity (even vs odd):

  • State q_even (start, accept): Seen even number of 1s (including zero)
  • State q_odd: Seen odd number of 1s

From q_even: on '0' stay, on '1' go to q_odd
From q_odd: on '0' stay, on '1' go to q_even

Each '1' flips between states; '0' never changes parity.

Design Strategy

  1. Identify what you need to remember about the input processed so far
  2. Create states for each distinct "memory" situation
  3. Draw transitions based on how each new symbol updates that memory
  4. Mark accept states where the pattern is satisfied

Key Takeaway: Designing DFAs is about identifying the minimal information needed to recognize a pattern, encoding that as states, and defining how input symbols update your "memory."