A regular crossword
Click for a full-size pdf of a
regular expression crossword where each
line must be a string matching a given regular expression
(source). Note that you will
have to learn about the zero-or-once operator ?, character classes [AEIOU]
and their negations [^AEIOU], and backreferences.
(E.g., (.*)\1 matches any string repeated twice, and (.)(.)\2\1 matches any 4-character palindrome.)
Note that backreferences are implemented by most "regular expression" engines (including Java's), but they
are not part of the formal mathematical definition of a regular expression because
some expressions involving backreferences cannot be converted to equivalent DFAs.
This puzzle was originally part of the 2013 MIT Mystery Hunt.