Due: Presentations will be done in class the week of April 25. Reports are due by 11:59pm Monday, May 2nd.

Your project will be to read something interesting about automata, grammars, or Turing machines, give a 20-25 minute presentation to the class, and prepare a short report based on your presentation. Topics that students find "interesting", along with any relevant sources, should be presented to the instructor for approval before work is started.

Possible topics include the following.

• Hopcroft's efficient algorithm for minimizing DFAs. (Source given at the end of chapter 2 of our textbook).
• Muller automata, which are automata that process infinite strings.
• Glushkov automata, which are the result of an alternate way of constructing finite automata from regular expressions. (Sources given at Jan Daciuk's FSA and DAWG page).
• Applications of finite automata, including but not limited to the decision procedure for WS1S.
• LALR parsing (see any Compiler Design textbook).

Projects may be done in pairs if there is an appropriate amount of extra effort involved, for example an implementation of an algorithm that is presented.