Assignment 12: Automata and Turing Machines! [100 Points]
Due Friday, December 8 by 11:59pm

Click here to read a review of the Distinguishability Theorem, the Nonregular Language Theorem, and how to use them.

This assignment also has a "certifiably cute" bonus problem at the end! It's fun, quite amazing, and worth 10 bonus points too!

In this assignment you will have the opportunity to try out the very nifty JFLAP Automata Simulator developed by Dr. Susan Rodger at Duke University. JFLAP allows you to create automata on the screen and then simulate them with any input string you like! You will also be proving that certain tasks are unsolvable by computers!

You can download a copy of JFLAP for your own computer (or on the Macs in the Beckman CS lab) for free. It is available at www.jflap.org. At that web site, follow the "Get JFLAP" link on the green left menu. From there, go to the bottom of the page and select "JFLAP software". After you have filled out the download form, choose the "JFLAP.jar" download dated Feb 12, 2005.

JFLAP is written in java and when you download it you will get a file called JFLAP.jar. When you invoke this file, it will start JFLAP.

If you use JFLAP on your own computer, you will need to copy the files that you create (the DFA's for the problems below) to turing in order to submit them. You can either use a scp program to securely copy the files from your machine to turing (scp is built into putty and into Mac OS X and is widely available for free download) or you can cut-and-paste the contents of the files on your computer to files with the same name on turing and then submit.

If you downloaded JFLAP to one of the Macs in the CS lab, life is even easier. Since the Macs share files with turing, you can save your files on one of these Macs, and then simply logon to turing and submit them!

When you start JFLAP, you will see a small menu with a File and Help menu at the top. You can use the File pull-down menu to save or load automata that you've constructed. The Help menu is very thorough. It even has a version entirely in haiku (try to find it - it's very amusing).

For each of the problems below, you should assume that the input will consist of zero or more 0's and 1's. Recall that every state in a DFA must have one outgoing transition labeled 0 and one outgoing transition labeled 1. Remember also that the DFA must accept every string in the language and reject every string not in the language. Finally, the empty string (λ, lambda) corresponds to no input at all. Note, for example, that if the language L is the set of all strings with an even number of 0's, then the empty string is in this language since it has zero 0's and zero is even! Thus, a DFA for this language must have the initial state be a final state, so that it accepts even if it gets no input! Be sure that your automata accept the empty string if it is in the specified language.

You will be able to use cs60submit just as usual. Your DFA files will end with .jff and your proofs will end with .txt. cs60submit recognizes both of these suffixes as legitimate files.

Finally, since you will be applying some of the theorems from class to write your own proofs, a sample proof is available at /cs/cs60/assignments/assignment12/sampleProof.txt. You are welcome to "copy" as much as you like from this sample proof when writing your own proofs.

1. [5 Points] In JFLAP, construct a DFA for the language:

     {w | w contains at least two 0's and at most one 1.}
     

   For example, the string 01000 is in the language but 01 and 0110 are not. Save your DFA in a file called part1.
   
   
2. [6 Points] In JFLAP, construct a DFA for the language:

     {w | The number of 0's in w is a multiple of 2 or a multiple of 3 or both.}
     

   For example, the empty string, 0101, and 01000100 are in the language but 01 is not. Your DFA should have at most 6 states. Save your DFA in a file called part2.
   
   
3. [8 Points] Prove that any DFA for the language in the previous problem MUST have at least 6 states. Write a clear and precise proof and save it in a file called part3.txt. Notice that since your DFA for this language had 6 states, you have proven that yours is as succinct a DFA as is possible for this language. (By the way, one way to prove this is to have 15 separate cases. This is fine. The cases are short. However, with a little bit of thought you may be able to have considerably fewer cases in your analysis!)
   
   
4. [12 Points] In JFLAP, construct a DFA for the language:

     {w | w is the BINARY representation of a number which is a multiple of 5.}
     

   For example, the inputs 101, 1010, and 1111 would all be accepted because they are the binary representations of the numbers 5, 10, and 15, respectively. Remember that the DFA reads input from left to right, so that the first digit seen is the most significant digit and the last digit seen is the least significant digit. The number may begin with leading zeroes (for example, 000101 is OK). The empty string should be interpreted as the number 0 and thus should be accepted. This problem is somewhat more challenging than the ones above. You'll need to think about this some before starting to construct your DFA. (Hint: Notice that given a binary number B, adding a 0 to the end of that number results in doubling the number! Make sure that you see why.) Save your DFA in a file called part4.
   
   
5. [12 points] In JFLAP, construct a nondeterministic finite automaton (NFA) for the language:

     {w | The number of 0's in w is a multiple of 3 or a multiple of 5 or both.}
     

   Notice that this machine would require at least 15 states if you were to build a DFA. (Make sure you see why.) You may use only 9 states in your NFA. Save your NFA in a file called part5.
   
   
6. [10 Points] Next, you'll prove that several languages are not regular by using the Nonregular Language Theorem. Recall that we say that a language is "Nonregular" if there cannot exist a DFA for it. First, consider the language:

     {w | w is made of 0's and 1's and is the same forwards as backwards}
     

   For example, 0, 11, 101, and 00100 are all in the language but 01, 100 and 010111 are not in the language. Prove that that this language is not regular by using the Nonregular Language Theorem. Type your proof into a file named part6.txt. As an example of what such a proof should look like, take a look at the file sampleProof.txt in /cs/cs60/assignments/assignment12/. Notice that simply giving an infinite set S does not suffice. You must also argue that any arbitrary pair of strings from S are always distinguishable!
   
   
7. [10 Points] Now consider the language

     {w | w is a string of 0's whose length is a power of 2}
     

   For example, the strings 0, 00, 0000, 00000000 are all in the language since their lengths are 1, 2, 4, and 8, all of which are powers of 2. On the other hand, 000, 00000, any string containing a character other than 0, and the empty string are all not in this language.

   Prove that this language is not regular by using the Nonregular Language Theorem. Your proof must be clear and precise. Leave your proof in electronic form in a file called part7.txt.

8. [25 Points]
   Build a Turing Machine to accept the language from the previous problem:

     L = { w | w contains only 0's and the length of w is a power of 2 }.
     

   Although it is not regular, it is decidable (i.e., there is a Turing machine that accepts it).

   We highly recommend spending some time thinking about this problem and sketching a solution on paper before using JFLAP. If you design the Turing Machine carefully, you can build it using no more than nine states.

   Save your Turing Machine in a file called part8.

   • When you start JFLAP (by typing java JFLAP) you should select Turing Machine from the JFLAP window. Make sure to read the instructions on Turing Machines in the Help menu.
   • Notice that the transitions are of the form Read, Write, Move. If you leave the Read or Write value alone (it will show a lambda initially) it will mean read or write a blank (which is what the tape is made up of, with the exception of the input). The lambda will disappear and the blank will be displayed by a square.
   • Your machine need not have transitions for the input symbol 1. You can assume that the input will be all 0's.
   • Remember that Turing Machines can write any symbols they like on the tape. Your Turing Machine will need to write symbols other than 0. Any symbol on your keyboard is a valid symbol to write. Try not to use too many different types of symbols as this gets confusing.
   • JFLAP allows you to specify multiple states as accepting states and doesn't have an explicit rejecting state. Your machine should have exactly one accepting state. In order to have a rejecting state, simply make a state that doesn't have any transition rules coming out of it. If you end up in this state, JFLAP will reject the input.
   
   
9. [12 Points] Finally, here's something very surprising: In the sampleProof.txt file (in the usual directory, /cs/cs60/assignments/assignment12), we've shown that the language

     {w | w contains an equal number of 0's and 1's in any order.}
     

   is not regular. However, now consider the following closely related language:

     {w | w contains an equal number of occurrences of the the pattern 01 and 10.}
     

   This language contains 0110 (this contains the pattern 01 once and the pattern 10 once) as well as 101 (this contains the pattern 10 once and the pattern 01 once - they overlap, but that's fine!). Amazingly, this language is regular! Show that this is true by building a DFA or NFA for this language using JFLAP. Save your solution in the file part9.
   
   
10. OPTIONAL Bonus Problems on Addition and Multiplication! So far, we have looked at DFAs whose input alphabet comprised only 0's and 1's. It's possible, however, for a DFA to have a different input alphabet. In this problem, we'll consider the following funky alphabet: A symbol in the alphabet is any 3-tuple (also known as a "vector") whose elements are either 0's or 1's. So, here are the eight symbols in our alphabet:

      
      (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1),
      (1, 1, 0), (1, 1, 1)
      

    For convenience, however, let's write each of these input symbols vertically and without parentheses. So, the eight symbols above will be represented as:

      0   0   0   0   1   1   1   1
      0   0   1   1   0   0   1   1
      0,  1,  0,  1,  0,  1,  0,  1
      

    Now, define the language of valid additions to be the collection of all strings made from this alphabet that correspond to correct binary additions when the input is interpreted as the number in the first row added to the number in the second row equals the number in the third row. Note that numbers are interpreted as the most significant digit is at the far left. This means that the DFA sees the most significant digits first!

    For example, consider the string of 4 symbols below:

      1   0   1   0
      0   0   1   0
      1,  1,  0,  0
      

    This 4-symbol string is in the language of valid additions since the sum of the binary numbers 1010 (first row) and 0010 (second row) is 1100 (third row).

    However, the following string is not in the language of valid additions:

      1    1
      0    1
      0,   0
      

    This string is interpreted as the sum of 11 (first row) and 01 (second row) is 00 which is false!

    This bonus problem has two parts. You may turn in one or both parts (for up to 5 bonus points each). Do these on paper and give them to Ran in class on Wednesday.

    1. Construct a DFA for the language of valid additions and then prove (using the Distinguishability Theorem) that your DFA has the fewest possible number of states. Very nifty!
    2. Now, consider this language's "first cousin": The language of valid multiplications. This is the language of strings of 3-tuples such that the product of the first and second rows is equal to the number in the third row. Show that NO DFA can exist for this language. Amazing but true!