Due in FOCS Project Tuesday 12 October

This is a two week assignment. You may decide for yourself how to allocate time between FOCS and FOCS project during the weeks of 28 September and 5 October.

The goal of this week's project is to work with regular expressions or finite state machines. You may choose from the suggestions below or propose one of your own. You may also the programming language of your choice.

• Build a finite state machine simulator. That is, build a program that takes a finite state machine description and a string and simulates the machine running on the string to determine whether it is accepted. A description of one such assignment is Fritz Ruehr's assignment from Willamette (see especially Lab 1, Lab 2). For those tackling this problem, there is a ProjectTwoFSASimulator wiki.

• Learn LEX. (Versions exist for several programming languages.) LEX uses regular expressions to generate code; in particular, it's intended to recognize different kinds of tokens for parsing. LEX info at:

  • The LEX and YACC page

  • There are several LEX-for-Java tools, including JLEX:

    • JLEX tutorial and JLEX manual

  • PLY is a LEX-for-Python

• Build a conversational program/pattern matcher. Some examples are

  • Weizenbaum's Eliza, the most famous pre-chat-bot of them all

  • SICP describes a pattern matcher
• Learn about (and use) an FSM-based tool to solve some real problem. For example:

  • Microsoft's ASP.NET tool for Wizard Control

  • open source, too. check out demo.

  • from UML

  • design pattern eg. from Harvard Extension/David Sullivan

  • a PERL FSM for translating document formats

* XSLT is regular expression based, but it'd be a fine thing to look at, too. You'd need to know about xml first, though.

• w3schools on xslt

• xml.com on xslt

• Continue working on your previous project, provided that there are interesting things to do with it. Using regular expressions (e.g., to screen scrape) would be a nice bridge.