Programming Assignment Checklist: Theory of Computation Exercises

Goals

Here are the main goals of the assignment.

• Use regular expressions or DFAs.
• Program a Turing machine.

Is this really how doctor's diagnose Huntington's disease. Yes.

What technique should I use for the HD diagnoser? We recommend using regular expressions, although there are other perfectly viable approaches, e.g., using DFAs.

How do I match any whitespace character with Java regular expressions? The predefined character class \s matches any whitespace character. To embed \s in a string, use \\s because \ is a special character.

Where can I find a list of useful String methods? Look in the Booksite section 3.1 Data Types.

Should I use StdIn or In to diagnose Huntington's disease? Use In because you are reading explicitly from a file this time, not from standard input redirected to read from a file. The file name will be a command line argument.

Do I need to use a halt state? No, your program should end in a yes state (labeled Y) or a no state (labeled N). The Turing machine for binary addition uses a halt state (labeled H) since it's purpose is to leave a result on the tape instead of answering a yes/no question.

Does my Turing machine have to clean up after itself and leave an empty tape? No. The only thing that is required is that it end up in the right yes or no state.

Once I've created my Turing machine input file, how do I test it? Use the Turing machine simulator from lecture. To read in your data file, use File -> Load Machine.

How do I launch the Turing machine simulator? Double-click the icon for turing.jar. Or, to launch it from the command line, type java -jar turing.jar.

Input, Output, and Testing

Input.   Here are a number of additional sample input files. You may find it useful to create additional test inputs to check that your programs work in all cases.

Submission

Submission. Submit Huntingtons.java and comparator.tur. We will supply In.java.

readme.txt. Use the following readme file template.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps. First download the theory directory from the ftp site.

1. Huntington's diagnoser.

   • Use Grep.java to find and print all lines in the input that contain CAG. No coding necessary.

   • Use Harvester.java to find and print out all CAG repeats. For now, don't worry about whitespace. No coding necessary.

   • Write a customized program (perhaps based on Harvester.java) that finds the longest CAG repeat, prints the number of its constituent CAG triplets, and prints an appropriate diagnostic message. Don't forget to disregard whitespace.

2. Turing machine.

   • Make sure you understand how the Turing machine described in binaryadder.tur works. Also make sure you understand the data file format.

   • Think about how you would compare two binary numbers. Don't worry about making your computation efficient - the brute force approach taken in binaryadder.tur is perfectly acceptable.