# 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.*