Assignment 6: Make a Deterministic FSM

Assigned 10th Feb; due 17th Feb

Working in Squeak, start with the newest version of my Monticello package CS510ap-RegularExpressions-apb.?.mcz; make sure that the tests run green. Get it from:

MCHttpRepository
location: 'http://www.squeaksource.com/AdvProg2009'
user: ''
password: ''

You will also need the Closure package, in the same repository, and the Connectors package, obtainable from SqueakMap (from the World menu).

Your task is to

• Implement a DFSM class for Deterministic FSMs
• Write tests that compare the acceptance behavior of equivalent NFSM and DFSMs
• Implement the algorithm to convert an NFSM to a DFSM
• Make the tests run green.

Work on this assignment in pairs. Please find a different partner to pair with; you will learn new stuff from each different person with whom you pair. If you absolutely can't find a different partner, you may reuse an old partner.

If you don't have an automata theory text handy, you might like to refresh yoru memory of the algorithm here, or by reading Mark's Haskell code form today's lecture.

Once again, turn in your work by email to cs410aph @ cs; include some text saying that Barney Rubble and worked with Fred Flintstone, or whatever. Make your work a new package that depends on the CS510ap-RegularExpressions package.