 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/i/solution

a_{1} \dots a_{k}

is described by the regular expression formed by concatenating its symbols; the empty string is described by

ε

. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by

\emptyset

. Thus

every finite subset of {0, 1}^{*} is regular .

Equivalently, a deterministic finite automaton can remember which prefix of one of the finitely many accepted strings has been read, moving to a rejecting dead state when no such prefix remains possible.

 New to topics? Read the docs here!