Computer Science 5641
Compiler Design
Homework Assignment 1 (20 points)
Due October 1, 2009

1. Consider a definition of strings as follows:
   • A string starts with a single double-quote character (") or two single back-quote characters (``)
   • A string ends with a single double-quote character (") or two single forward-quote characters (' ')
   • A string may contain letters, digits, spaces, tabs and escaped double-quote, back-quote or forward-quote characters
   • Any quote character is escaped by preceding it with a slash character
   1. Draw a DFA that recognizes this language
   2. Write a regular expression that defines this language
   3. Convert your regular expression into an NFA using the algorithm that was discussed in class
   4. Run the algorithm we discussed in class to convert your NFA to a DFA
2. Some programming languages allow integer constants to be written in other bases (e.g., base 8, 10, 16). Consider a language of integer constants where base 8 numbers start with a 0 and may contain digits from 0 to 7, base 10 integer constants start with any digit other than zero and can include digits from 0 to 9, and base 16 numbers start with an X or x and can include digits 0 through 9 as well as letters A or a through F or f -- 10 (A or a), 11 (B or b), 12 (C or c), 13 (D or d), 14 (E or e), 15 (F or f).
   1. Draw a DFA that recognizes this language
   2. Write a regular expression that defines this language