Exercise 2        Name __________________        Score __/31

1. (10) Write regular expressions for the following:
   1. Strings over the alphabet {a,b,c} where the first a precedes the first b.
   2. Strings over the alphabet {a,b,c} with an even number of of a's.
   3. Binary numbers that are multiples of four.
   4. Strings over the alphabet {a,b,c} that don't contain the contiguous substring baa.
   5. The language of non-negative integer constants in C, where numbers beginning with O are octal constants and other numbers are decimal constants.
2. (1) Why are you not surprised that there is no regular expression defining strings of a's and b's  that are palindromes (the same forward as backward). Hint: Consider the number of finite-automata states required.
3. (4) Explain in informal English what each of these finite-state automata recognizes.
   
4. (4) Convert these regular expressions to NFA.
   1. (if|then|else)
   2. (a((b|a)*c)x)*|x*a
5. (12) Convert these NFAs to DFAs, just do a.