Due: TBA

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.

Individual software projects may also be acceptable but may be recognized for a lower degree of difficulty. Possibilities include

• simulators for various forms of Turing Machines, or
• a small compiler built with lex and yacc (along with a tutorial on their use).