CMPS 260 Spring 2025
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 produce the equivalent minimal DFA.
• Given an NFA M, present a regular expression r such that L(M) = L(r). Or vice versa.
• Given a regular expression r, list all strings —up to some small maximum length— that are members of L(r).
• Given two regular expressions r₁ and r₂, identify a string that is a member of L(r₁) − L(r₁). Similarly for L(r₁) ∩ L(r₁) and/or the complement of L(r₁) ∪ L(r₁)
• Given some operation on languages (in the same spirit as, e.g., reversal, tail, and head), give a convincing argument that regular languages are closed under that operation.