CMPS 260 Spring 2026
April 15 test preview

Among the kinds of problems/questions you should expect are these:

• Given a context-free grammar (CFG), provide a precise description of the language that it generates.
• Given a precise description of a context-free language (CFL), present a CFG that generates that language.
• Given an ambiguous CFG, demonstrate that it is ambiguous (by showing either two nonisomorphic derivation trees or two distinct leftmost derivations for the same string).
• Given an ambiguous CFG, modify it to obtain a non-ambiguous CFG that generates the same language.
• Posed with a decision problem about CFLs similar to one discussed in class (e.g., "Given CFG G, is L(G) infinite?"), give a coherent argument that the problem is decidable/solvable.
• Certain kinds of productions in CFGs are problematic, leading to a desire to remove them without changing the language generated by the grammar. Among these are λ-productions, which can be removed by replacing every non-λ-production A → α by the set of productions

  { A → α' | α' is obtained by erasing zero or more occurrences in α of nonterminals originally having λ-productions }

  For example, if A → xByCz is a production and both B and C originally had λ-productions, then keep that production and add these three productions: A → xyCz | xByz | xyz.

  Given a different kind of "undesirable" production, devise a method by which to remove all such productions from a CFG without changing the language that it generates.

• Given an operation on languages, show that this operation preserves regularity. That is, if the operation is applied to a regular language, the resulting language is also regular. A typical strategy is to show how to modify a given DFA that accepts language L to obtain an NFA that accepts op(L), where op is the operation in question.