CMPS 260 Spring 2025
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 exams.

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

• 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 Section 3.2 of Linz) however.)
• Given a nondeterministic finite automaton (NFA), convert it to an equivalent deterministic finite automaton (DFA) using the standard "subset construction" algorithm (what Linz refers to as the nfa-to-dfa procedure in Section 2.3).
• Given the description of some language operator (e.g., as in Problems 5-7 of HW #4), 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.

• Given a DFA M, identify the equivalence classes of the state-indistinguishability relation and, based upon those, construct the equivalent minimal DFA M'.
• 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 PDA (possibly restricted to be a Deterministic PDA)
• Given a CFG G, provide a precise (even if not necessarily formal) description of the language that it generates (L(G)).
• Given an ambiguous CFG, show that it is ambiguous.
• 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 slight deviation of the standard Turing Machine model, 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).
• Given the description of a set that is countable, but perhaps not obviously so, demonstrate that it is by describing a one-to-one correspondence between it and the set of positive integers, or by describing a procedure by which to enumerate its elements.
• Show that a given problem/language is undecidable by describing a reduction to it from a known-to-be undeciable language/problem (e.g. the Halting Problem).
• Given the description of an enumeration procedure for some recursively enumerable (RE) set, argue that the nature of that procedure can be exploited in such a way as to show that the set is actually recursive.
• Given a set-theoretic operator (e.g., union, intersection), argue in favor of, or against, the proposition that the class of recursive/decidable (or perhaps RE) languages is closed under that operation.
• Given a pair of similar decision problems (i.e., 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₂.)