• The answer to odd numbered exercises from the textbook are given in the back of the book. Don't copy the answers, but rather find the solutions, compare to the answer, and repeat until you get the correct answer.
• Read the ideas at Homework 2 FAQ prior to starting the homework.

• Learn notation and uses of finite state machines
• Learn notation and uses of context-free grammars
• Prep for project 1

• Finite state transducers for simple languages.
• Finite state transducer for the lexer in lab 1
• Finite state machines that recognize abstract languages
• Regular expressions, including some edge cases
• Experiment with generating a language with a regular expression that is recognized with a FSM
• Relationship between CS concepts and FSMs – switch statements, if-then-else, lexers, models of actors, directory listings, search engines
• Experiment with various context free grammars
• Relationship between CS concepts and CFGs
• Simple parse trees
• Ambiguity and backtracking
• Methods for doing a left-most derivation unambiguously
• Removing ambiguity using implementations of precedence

For the international edition, change 13 to 12 on the chapter.

1. (2 points) Section 13.2 problem 1 part a.
2. (2 points) Section 13.2 problem 2 part b.
3. (2 points) Section 13.2 problem 3 part a.
4. (2 points) Section 13.2 problem 4 part b.
5. (3 points) Section 13.2 problem 8.
6. (4 points) Section 13.3 problem 1 parts a, b, and d.
7. (4 points) Section 13.3 problem 2.
8. (4 points) Section 13.3 problem 16.
9. (3 points) Section 13.3 problem 23.
10. (5 points) Draw the finite state automaton that detects single line comments as defined in project 1 (lexical analysis). You may use <EOF> for the end-of-file character and <EOL> for the end-of-line character.
11. (6 points) Section 13.4 problem 3 parts a, b, and c.
12. (2 points) Construct a regular expression that generates the language recognized by the finite state machine in section 13.4 problem 16. (Error in international edition: arrow should point from s₀ to s₁, not vice-versa)
13. (4 points) Go to the gskinner.com regular expression checker and type in the bulleted items below, separated by newlines, in the second box. In the first box, type in a regular expression that will generate each the first four strings and fail to generate the last two. The second box will highlight the ones matched by the regular expression. In your regular expression, use the vertical bar '|' instead of the union symbol from definition 1 in section 13.4. You can use the shorthand [3-7] to indicate any digit between 3 and 7, inclusive. When you get a regular expression that works, write the regular expression as the answer to this problem.
    • 12:36 pm
    • 1:59 am
    • 4:00 pm
    • 2:45 am
    • 13:45 am
    • 9:79 pm