= Solution
This is a <regular language>. A <deterministic finite automaton> needs only to remember the number of consecutive trailing ones, up to three, and whether a forbidden run of four has already occurred. Use states $q_0,q_1,q_2,q_3,q_\times$, start at $q_0$, and accept in $q_0,q_1,q_2,q_3$. Its <transition function of a finite automaton> is:
|| State
|| On $0$
|| On $1$
| $q_0$
| $q_0$
| $q_1$
| $q_1$
| $q_0$
| $q_2$
| $q_2$
| $q_0$
| $q_3$
| $q_3$
| $q_0$
| $q_\times$
| $q_\times$
| $q_\times$
| $q_\times$
Reading a zero resets the trailing count unless rejection has already occurred. A fourth successive one enters the permanent rejecting state $q_\times$. Thus the accepted <strings> are exactly those with no substring $1111$, and
$$
\boxed{\text{the bounded-run language is regular}.}
$$
Back to article page
