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).