DFA avoiding substring 10110

Idea. Use states q0..q4 to record the length of the longest suffix of the input read so far that is a prefix of 10110. If the whole pattern 10110 is seen, go to a dead (trap) state. All states except the dead state are final.

M = ({q0, q1, q2, q3, q4, d}, {0,1}, δ, q0, {q0, q1, q2, q3, q4})

Meaning: q0 = no progress; q1 = suffix "1"; q2 = "10"; q3 = "101"; q4 = "1011"; d = pattern found.

Transition table

Reasons for the less obvious moves:

• q1 on 1: input ends in "11"; the longest suffix that is a prefix is "1", so q1.
• q2 on 0: "100" has no suffix matching a prefix, so q0.
• q3 on 0: "1010" ends in "10", so q2.
• q4 on 1: "10111" ends in "1", so q1.
• q4 on 0 completes 10110, so d.

    1        0        1        1        0
 q0 ──► q1 ──► q2 ──► q3 ──► q4 ──► d
 (all of q0..q4 are final; d is the trap)

 Back edges:  q0 ↻0     q1 ↻1     q2 -0-> q0
              q3 -0-> q2           q4 -1-> q1
              d ↻0,1

Verification

• Accepted: 1011. q0 →1 q1 →0 q2 →1 q3 →1 q4 (final). Also 101011: q0,q1,q2,q3,q2,q3,q4 (final); 10110 is not a substring.
• Rejected: 0101100. q0 →0 q0 →1 q1 →0 q2 →1 q3 →1 q4 →0 d →0 d, and d is not final (the string contains 10110).