Designing a DFA for Binary Strings That Avoid Substring “101”

Verified Sources

Nov 4, 2026

We want a deterministic finite automaton (DFA) over $\Sigma=\{0,1\}$ that accepts exactly the strings that do not contain the substring $101$ . This is a standard “pattern-avoidance” construction: the DFA tracks the longest suffix of the input so far that is also a prefix of the forbidden pattern $101$ (so we know how close we are to completing it).

Intuitively, we only need to remember the partial progress toward forming $101$ :

we have matched nothing yet,
we have matched a trailing 1,
we have matched a trailing 10,
if we ever complete 101, we must reject.

This approach is essentially the same idea as building a DFA using a prefix-function / failure-link style mechanism (as in KMP automata construction), but expressed directly as DFA states.

Below is a complete DFA design, its formal transition table, and a correctness argument.

DFA construction for avoiding substrings (pattern avoidance concept)

Key ideas and terminology

substring
prefix
suffix
accepting state
trap (sink) state

Construct a DFA that avoids the forbidden substring 101

1
Step 1
Let the forbidden substring be $p=101$ and $\Sigma=\{0,1\}$ . We will accept strings that never complete $p$ .
2
Step 2
Create states representing the longest suffix of what you’ve read so far that matches a prefix of $101$ : $S0$ for '', $S1$ for '1', $S2$ for '10'.
3
Step 3
Add $S3$ for having matched '101'. Once in $S3$ , any further input keeps the string containing '101', so $S3$ must be a trap.
4
Step 4
For each state and input symbol, update the longest suffix that is a prefix of '101'. This can be done by reasoning about what suffix could end the newly extended string.
5
Step 5
Accept exactly when you are not in $S3$ . Hence accepting states are $S0,S1,S2$ and the rejecting state is $S3$ .

DFA Definition

States

Let the DFA be $M=(Q,\Sigma,\delta,q_0,F)$ with:

$Q=\{S0,S1,S2,S3\}$
$\Sigma=\{0,1\}$
Start state: $q_0=S0$
Accepting states: $F=\{S0,S1,S2\}$
Rejecting/trap state: $S3$

Transition function $\delta$

The transitions are determined by how the next input bit extends (or resets) the partial match.

Current state	Read `0` → Next	Read `1` → Next	Meaning
$S0$	$S0$	$S1$	No partial match; suffix ''
$S1$	$S2$	$S1$	Suffix '1' matched
$S2$	$S0$	$S3$	Suffix '10' matched; next `1` completes '101'
$S3$	$S3$	$S3$	Forbidden already found (trap)

So, formally:

$\delta(S0,0)=S0,\ \delta(S0,1)=S1$
$\delta(S1,0)=S2,\ \delta(S1,1)=S1$
$\delta(S2,0)=S0,\ \delta(S2,1)=S3$
$\delta(S3,0)=S3,\ \delta(S3,1)=S3$

Correctness sketch (why this accepts exactly the safe strings)

We prove: the DFA accepts iff the input does not contain substring $101$ .

Invariant. After reading any input prefix $w$ , the automaton is in:

$S0$ if the longest suffix of $w$ that is a prefix of $101$ equals ''
$S1$ if that longest suffix equals '1'
$S2$ if that longest suffix equals '10'
$S3$ if $w$ already contains '101' (and then we stay in $S3$ forever)

This invariant holds because transitions were defined by how the next symbol can extend or break the current partial match. In particular:

From $S2$ (meaning we currently have suffix '10'), reading 1 forces completion of '101' → move to $S3$ .
From $S3$ , we loop on both symbols, so once rejected, always rejected.

Therefore:

If the string ever contains '101', the DFA reaches $S3$ at the moment that substring completes and rejects.
If the string never contains '101', the DFA never reaches $S3$ , so it ends in $S0,S1,$ or $S2$ and accepts.

State meanings vs. partial matches

Each state corresponds to the longest suffix that is also a prefix of '101'.

Common checks and edge cases

How the DFA progresses while scanning an input

Read nothing

Start

In $S0$ (no relevant suffix)."

Track '1' as a partial match

After seeing 1

In $S1$ when the suffix is '1'."

Track '10' as a partial match

After seeing 10

In $S2$ when the suffix is '10'."

Forbidden pattern completes

When the next symbol is 1

Move to $S3$ upon reading '1' in state $S2$ ; then reject forever."

DFA for avoiding 101 — quick checks

1 / 4

Question · Term

What does state S1 represent?

Click to reveal

Answer · Definition

S1 represents that the longest suffix seen so far that is a prefix of '101' is exactly '1'.

Knowledge Check

Question 1 of 4

Q1Single choice

In the DFA that avoids the substring '101', what is the purpose of the trap state?

It marks that the input has matched the forbidden pattern already and should never accept

It marks that the input is currently matching the first symbol '1' of the forbidden pattern

It is used only to speed up computation but does not affect acceptance

It represents an invalid input symbol

Explore Related Topics

Construct a DFA for the Regular Expression $r = 0^*1^*2^*$

Linear Bounded Automata (LBA): Definition, Tape Restriction, and an LBA for $\\{a^n b^n c^n\\}$

DFA Design: Strings over $\{a,b\}$ with at least three occurrences of the substring $bbb$ (overlap allowed)

Browse all research articles