CMPS 260 Spring 2026
March test preview
Among the kinds of problems/questions you should expect are these:
- Given a description of a function computable by a Mealy machine,
present a Mealy machine that computes that function.
- Given a description of a regular language L (either in English
or using set comprehension notation), present a DFA (or
possibly an NFA, if allowed) that accepts L, or possibly
a regular expression r that describes L.
- Given an NFA, apply the Subset Construction algorithm to
produce an equivalent DFA.
- Given a DFA, apply the DFA Minimization algorithm to compute
the Indistinguishability equivalence relation on its state set.
(That is, identify the equivalence classes of that relation.
Each equivalence class is a maximal set of states each of which
is indistinguishable from each of the other states in that set.)
- Given a (small) NFA M, present a regular expression r
such that L(M) = L(r).
- Given a regular expression r, list all strings
—up to some small maximum length—
that are members of L(r).