Answer: Finite automata

Question: Which of the following are regular? Write regular expressions for those that are. (You can use a period `.' to represent any character in the alphabet (``(a_1|a_2|a_3|...|a_k)'', if the a_i are the characters in the alphabat).)

1. the set of all strings
2. strings containing both ``smile'' and ``frown'' as substrings
3. strings containing 211 as a subsequence (211 is a subsequence of ``25-100 is a 12-credit course'' because it contains 211 in order)
4. bit sequences representing numbers that are both prime and perfect. (A number n is perfect if the sum of its factors (except n) is n itself.)

Answer: They all are.

1. ``.*''
2. ``(.*smile.*frown.*)|(.*frown.*smile.*)''
3. ``.*2.*1.*1.*''
4. the empty set (no strings); there isn't really a regular expression for this. No prime numbers are perfect; their factors except the number itself add up to only 1, and 1 isn't among the primes.