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.

How should I read in the data to diagnose Huntington's disease? Use the readAll() method in the In data type. The name of the input file is specified as a command line argument, so you must read directly from the file (instead of using standard input).

What technique should I use for the HD diagnoser? Use regular expressions, i.e., Pattern and Matcher.

Where can I see all available String library methods? Here is the String API.

Where can I see the pattern Matcher class and its library methods? Here is the Matcher API.

How do I match any whitespace character with Java regular expressions? One way is to use the predefined character class \s matches any whitespace character. To embed \s in a string, use \\s because \ has a special meaning within a string.
Another way is to use a regular expression to remove all characters that are not in the set we are interested in. The Java page on regular expressions may help with either approach.

What's the difference between the String methods replace(from, to) and replaceAll(from, to)? Both return a new string with all occurrences of from replaced with the string to. The former treats from as a string; the latter treats from as a regular expression. This is a lesson in how not to design an API.

Why doesn't s.replaceAll("a", "x") change the string s? Re-read Section 3.1. Pay special attention to the distinction between mutable and immutable data types.

Frequently Asked Questions: Turing machine

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.

Can I assume that the binary input numbers will both have the same number of bits? No. Do NOT assume that the input numbers are of the same length.

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? Download the Turing machine simulator and launch by clicking the .jnlp file that apperas on your desktop. Alternatively, you can download the file turing.jar from Section 7.5, and launch from the command line by typing 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.

Enrichment

Listen to the Huntington Disease Protein where each amino acid is assigned a note on the musical scale [mp3]. Reference.

Huntington's protein