Part I: Regular Languages, Regular Expressions, and Finite Automata:

1. Describe, in English, the language accepted by the following DFA:

2. Give a regular expression that describes the same language.

3. Give a regular expression for the language of dollar values, written with an optional leading minus (but not plus) followed by an optional leading dollar sign, with required commas used to group the digits in threes, and an optional final three characters consisting of a decimal point and two digits (for the cents). (I.e., -$12,345.67 and 1,234,567.89 and 12.34 and -12,345 are ok, but 12345.67 and 12,345. and 12,345.6 and 123,45.67 are not.)

   For a small amount of extra credit, design the machine so that the dollar-value part does not accept leading zeroes.

4. Draw a DFA for that language.

5. Draw the DFA that accepts strings of decimal digits that represent numbers divisible by 4. (I.e. it should accept 0, 4, 28, 360, etc., and reject 3, 19, 191, etc.)

6. Extra Credit: Give a regular expression for that language.

Part II: Context-Free Grammars and SLR(1) Parsing:

1. Given the SLR(1) parse table for s-expressions given in the handout, parse the string " ( ( ) id ( id ) ) $ ". Show the parse tree constructed for the string and the complete history of the stack.

   To show the stack history, just cross out the elements on the stack as they are popped, but leave them there so that they can be read. That is, I just want a record of the order things were pushed on the stack.