 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2005/calculus-linear-algebra-discrete-mathematics-logic-and-proof-and-models-of-computation/9/b/iii/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}

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

the bounded-run language is regular .

 New to topics? Read the docs here!