Example 1: Designing and Building a DFA

Main ideas and lessons

• Purpose of DFA design: Given a language (described as a set or informally), the goal is to design a DFA that recognizes exactly the same set of strings.
• No universal step-by-step procedure: DFA construction is not fully mechanical. Instead, you reason about what strings should be accepted/rejected, then reflect that reasoning in states and transitions.
• Core strategy:
  1. Understand the language by generating examples (strings in the language and not in it).
  2. Use those patterns to create a DFA with fewer states than brute-force enumeration.
  3. Add a “bad” (sink) state for all rejecting situations that should remain rejecting forever.
  4. Validate the DFA with structural checks and input-output testing.

Specific example language (the one being built)

• Alphabet: (\Sigma = {0,1,2,3})
• Language definition: All strings (x) such that:
  • The first character of (x) equals the length of (x).

Examples of the language’s behavior

• If a string starts with 0, it would need to have length 0, but that would require the empty string, which has no first character. → No strings starting with 0 are accepted.

• If it starts with 1, it must have length 1. → Only “1” is accepted.

• If it starts with 2, it must have length 2. → Accepted: “20”, “21”, “22”, “23”.

• If it starts with 3, it must have length 3. → Accepted: all strings of length 3 that start with 3.

DFA construction methodology used

Step 1: Derive accepted vs rejected strings

• List strings that should be accepted based on the “first symbol = length” rule.
• Identify obvious rejection cases early (e.g., “starts with 0” is impossible to satisfy).

Step 2: Create a rejecting sink state (“bad”)

Define a state bad with these properties:

• Once entered, it cannot be left.
• Reading any further character keeps the DFA in bad.
• bad is not an accept state.

Use bad for:

• Any string that violates the rule immediately (e.g., starts with 0).
• Any string that becomes “too long” or has mismatched length after the critical prefix.

Step 3: Build states for the “first character” cases

• Start state:

  • Not finalized as accepting; it branches based on the first input symbol.

• Case when input starts with 0:

  • On reading 0 immediately go to bad (reject).

• Case when input starts with 1:

  • After reading the first 1, move to a state that:
    • Accepts only if the input ends immediately (because length must be exactly 1).
    • Any additional character sends the DFA to bad.

• Case when input starts with 2:

  • After reading 2, move to a state that:
    • Does not accept yet (length 1 is not sufficient).
    • On reading a second character (0,1,2,3), transition to an accepting configuration only if input ends there.
    • Any third character causes a transition to bad.

• Case when input starts with 3:

  • Build a short chain of states corresponding to consuming exactly the remaining required characters:
    • After 3, the DFA should accept only when the total length reaches 3.
    • If fewer than 3 characters are read, the DFA will fail to reach the accept state.
    • If more than 3 characters are read, it transitions to bad and stays there.

Step 4: Ensure the DFA is formally complete

• Check that there is exactly one start state.
• Confirm the set of accepting states matches the intended lengths:
  • Accepting for strings that end exactly at length conditions for first symbol 1, 2, or 3.
• Transition completeness (DFA requirement):
  • From every state, there must be a defined transition for every character in ({0,1,2,3}).
  • If any outgoing transition is missing, the transition function is undefined.

Step 5: Test with representative input strings

Include:

• The empty string (\epsilon) (special case).
• Strings you expect to accept and reject.
• Both short and long strings.

Simulate DFA runs to verify the final state is accept/reject as expected. Example tests described:

• (\epsilon): reject
• 1: accept
• 10: reject
• 21: accept
• 200: reject (too long)
• 313: accept
• 31: reject (too short)
• Also test long strings starting with 0 to ensure they go to bad and remain rejecting.

Main checks emphasized (validation checklist)

Structural checks

• Exactly one start state
• Accept states placed correctly for:
  • Strings starting with 1 with length 1
  • Strings starting with 2 with length 2
  • Strings starting with 3 with length 3

Transition completeness check

• Every state must have transitions labeled 0,1,2,3
• Common mistakes noted:
  • Forgetting to label an edge correctly
  • Forgetting to add the missing self-loop transition on the bad state

Behavioral checks

• Test a variety of strings, including:
  • (\epsilon)
  • known accept cases
  • known reject cases
  • edge-length and too-long cases
  • long strings reaching the bad state

Speakers / sources featured

• Speaker: An unnamed instructor (narrator guiding through the example)
• Reference source: Sipser, pages 41–44 (as an introduction/reference for designing DFAs)