CMPS 260 Spring 2026
Preview of Final Exam

Generally speaking, you should expect the final exam to include problems similar to those that appeared in the homework assignments and the midterm exam.

More specifically, you should be prepared to solve problems of the following types:

Regular Languages

• Given an informal, but precise, description of a regular language, devise either a finite automaton (possibly restricted to being deterministic) that accepts the language or a regular expression that denotes the language.
• Given a (possibly nondeterministic) finite automaton, or a regular expression, provide a precise (even if not necessarily formal) description of the language that it accepts/denotes.
• Given a finite automaton M, devise a regular expression r such that M and r represent the same language (i.e., L(M) = L(r)). Or vice versa. (You will not be expected to carry out the standard NFA-to-regular expression algorithm (in Webber's Appendix A) however, as it typically results in a very complicated regular expression.)
• Given a nondeterministic finite automaton (NFA), convert it to an equivalent deterministic finite automaton (DFA) using the standard "subset construction" algorithm.
• Given a description of a property that a language might possess, describe an algorithm that, given as input a DFA M, decides whether or not L(M) possesses that property. (A problem of this kind was Problem 7 in HW #1.)
• Given the description of some language operator, justify the claim that regular languages are closed under that operator.

  For a unary operator, typically this is done by showing that an FA that accepts L can be (algorithmically) modified to become an FA that accepts op(L). For a binary operator, typically this is done by showing that an FA accepting L₁ op L₂ can be built using FA's that accept L₁ and L₂.

  For some operators, a construction based upon regular expressions (or right-linear grammars) could be simpler.

  For example, consider the "Erase all a's" unary operator. When applied to a string x, it erases every occurrence of a within x. For example, EraseAllA(bbacaabacba) = bbcbcb. Applied to a language L, it produces the language consisting of the members of L, each having all its a's erased:

  EraseAllA(L) = { EraseAllA(x) | x ∈ L }.

  Given an NFA M, to produce an NFA M' such that L(M') = EraseAllA(L(M)), it suffices to replace every transition p →^a q by p →^λ q. That is, every transition labeled a is modified so that its label is λ.

• Given a DFA M, identify the equivalence classes of the state-indistinguishability relation and, based upon those, construct the equivalent minimal DFA M'.

Context-free Languages

• Given a CFG G, provide a precise (even if not necessarily formal) description of the language that it generates (L(G)).
• Given an informal, but precise, description of a context-free language (CFL), devise a context-free grammar (CFG) that generates that language, or perhaps a stack machine that accepts it.
• Given an ambiguous CFG, demonstrate that it is ambiguous (by showing two different derivation trees for the same string).
• Given a Chomsky Normal Form CFG G and a (short) string x, apply the CYK algorithm to determine whether x ∈ L(G).
• Given a context-free grammar, be able to determine whether or not it qualifies as an s-grammar, a q-grammar, or an LL(1) grammar and to fill a parsing table to guide the standard left-to-right top-down parsing algorithm.
• Given the description of some language operator, justify the claim that context-free languages are closed under that operator. (Recall the discussion above about regular languages being closed under the EraseAllA() operator.)
• Given a description of a property that a language might possess, describe an algorithm that, given as input a context-free grammar G, decides whether or not L(G) possesses that property. (As an example, in class we discussed how to determine whether L(G) is infinite.)

Turing Machines

• Given the description of a (simple) recursively enumerable (RE) language, devise a Turing machine (TM) that accepts it, or at least describe such a machine in sufficient detail that it is clear that the details could be worked out.
• Given the description of a (simple) computable function, devise a Turing machine (TM) that computes it, or at least describe such a machine in sufficient detail that it is clear that the details could be worked out.
• Given the description of some slight deviation of the standard Turing Machine model (e.g., two tapes rather than one), explain how its computations could be simulated by a standard TM (if the deviation is a relaxation of the standard rules) or vice versa (if the deviation is a restriction of those rules).

Recursive (Decidable) and Recursively Enumerable (Semi-decidable) Languages; Reduction

• Show that a given problem/language is undecidable by describing a reduction to it from a known-to-be undecidable language/problem (e.g. the Halting Problem).
• Given the description of an enumeration procedure for some recursively enumerable (RE/semi-decidable) language, argue that the nature of that procedure can be exploited in such a way as to show that the language is actually recursive/decidable.
• Given a flawed attempt to prove something about recursive or RE languages (e.g., they are closure under union), identify the flaw.
• For a given language operator (e.g., union, intersection, concatenation), argue whether or not languages in a given class (e.g., recursive/decidable, RE/semi-decidable) are closed with respect to that operator. (E.g., Is the intersection of two RE languages necessarily RE?)
• Given a pair of similar languages L₁ and L₂, show that L₁ is polynomial-time reducible to L₂. (This entails describing an algorithm that, given a string w₁, produces (in polynomial time in the length of w₁) a string w₂ such that w₁ ∈ L₁ if and only if w₂ ∈ L₂.)