Assignment 13: NFAs, Turing Machines, and Uncomputability!
Due Monday, April 25 by 11:59 PM (except for Part 4 which is due at the beginning of class on Tuesday the 26th)

In this assignment you will be playing with NFA's, Turing Machines, and those AMAZING proofs that some problems are computationally impossible to solve! Please note that Part 4 of this assignment asks you to write careful proofs. You should write these on paper and turn them in at the beginning of class on Tuesday.

1. NFA's meet JFLAP! (15 Points)
   JFLAP allows you to create and run nondeterministic finite automata just as you would deterministic ones. 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.}
     

   You may use only 9 states in your NFA. Save your NFA in a file called part1. (Notice that a DFA for this language would require at least 15 states. You don't need to prove that here, but make sure you understand how this would be proved.)
   
   
2. NFA's Meet Prolog! (20 Points)
   One problem with NFA's is that it can be difficult to tell whether a particular NFA accepts a given input string. Professor Otto Mattah would like to write a computer program that takes as input a description of a NFA and a string and determines all of the possible ways (if any) that would allow the NFA to accept the string. Professor Mattah realizes that while he can do this in any programming language, Prolog is by far the best choice. Your task is to write this program in Prolog. Here are the details:

   The NFA will be encoded in a file of Prolog rules as shown in the example below:

     transition(q0, 0, q0).
     transition(q0, 1, q0).
     transition(q0, 1, q1).
     transition(q1, 0, q2).
     transition(q2, 0, q2).
     transition(q2, 1, q2).
   
     initial(q0).
     final(q2).
     

   The rules of the form transition(x, y, z) encode the information that in state x on input y the NFA may go to state z. Notice that in the example above, there are two transitions from state q0 on input 1. This is nondeterminism! The rule of the form initial(x) indicates that state x is the initial state. There may be only one such rule in a given NFA file. Finally, the rules of the form final(x) indicates that state x is an accepting state. There can be an arbitrary number of rules of this form for a given NFA. Note that the NFA in the example above accepts exactly those strings that contain the pattern "10" in them.

   Your job is to write a Prolog rule called accepted which takes as input two arguments: The first argument is a list of 0's and 1's which represent the input string. The second argument is a list of states in an accepting path for the NFA. For example, for the NFA above, consider the following sample input and output:

     | ?- accepted([0, 1, 0], [q0, q0, q1, q2]).
     yes
     

   Prolog says "yes" because on input string "010" the NFA can accept by starting in state q0, going to state q0 on the first 0, going to state q1 on the 1, and entering state q2 on the last 0. Since state q2 is an accepting state in this example, the NFA accepts.

   Place your code in a file called part2.pl that contains the Prolog code for the accepted rule (and whatever other helper code you need). This file should NOT contain the description of any specific NFA, since we'll be trying it out on a variety of NFA's. Instead, you can find the example NFA above in the file /cs/cs60/assignments/assignment13/nfa.pl. You can copy this file into your directory. Then, when entering Prolog you could load in both your part2.pl file as well as the nfa.pl file. For example, here is some sample input and output:

     | ?- ['nfa.pl'].
     % compiling file /home/hadas/nfa.pl
     % nfa.pl compiled in module user, 0.000 sec 872 bytes
   
     yes
     | ?- ['part2.pl'].
     % compiling file /home/hadas/accepted.pl
     % accepted.pl compiled in module user, 0.000 sec 452 bytes
   
     yes
     | ?- accepted([0, 1, 0], X).
   
     X = [q0,q0,q1,q2] ;
   
     no
     

   If there are many different ways in which the NFA could accept the string, your program must be willing to show them all! (Using ";" repeatedly when running the program.)

   It is advisable to test your solution on a few simple NFAs that you make up yourself. Testing your own software is an important thing to do!

3. Turing Machines! (25 Points)
   Consider the language

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

   That is, the language contains all strings of 0's whose length is a power of 2. We already know (from the last homework assignment) how to prove that this language is NOT regular.

   Nonetheless, this language is accepted by a Turing Machine! Use JFLAP to construct a Turing Machine that accepts this language. 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. One bonus point will be given for each state that you save over nine states. For example, if your solution uses only 3 states (this is possible!), you'll get 6 bonus points!.

   Save your Turing Machine in a file called part3. (JFLAP will automatically add the suffix jff at the end of this filename.)

   • 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.
   
   
4. Millisoft (40 Points)

   This part of the assignment should be submitted on paper at the beginning of class on Tuesday. No CS 60 dollars can be used on this part.

   You have been hired by Millisoft. Your boss, Gill Bates, drops by your spacious cubicle sipping a refreshing and stimulating Jolt Cola ("All the sugar, and twice the caffeine!"). Gill begins by reminding you that a decider is a program that takes an input and eventually halts and accepts (says "yes" to its inputs) or rejects (says "no" to its input). For example, a decider for the prime numbers would take a number (perhaps encoded in binary) as input and would eventually halt saying "yes" (it's prime) or "no" (it's not prime).

   1. "OK, so here's your first task," says Gill. "We're having a little programming competition in the company. The contestants are writing deciders which take as input a string of 0's and determine whether the number of 0's was a power of 2." You smirk, having written such a program in JFLAP just a short time ago yourself! "Here's what I need from you," says Gill. "I need a program which we'll call a Power of Two Decider Tester (POTDT). The POTDT takes as input a program. The POTDT then decides whether P is a legitimate decider for strings whose length is a power of 2. That is, the POTDT eventually halts and says yes if the program it received was a correct submission for this competition and otherwise the POTDT halts and says no. I need this POTDT program written by tomorrow at 6 AM." Prove to Gill that this cannot be done, not by 6 AM and not EVER! You may use diagrams to help explain your proof, but your proof must be clear, precise, and rigorous. Your submission on this and the following problem will be graded on clarity and precision of explanation.
      
   2. "Alright," says Gill. "Drats! In that case, I'd like you to write a program called a Regularity Checker (RC). The Regularity Checker takes as input a program P (e.g. a Turing Machine) and determines whether or not the set of strings accepted by P is a regular language. The RC must always halt with an answer of yes or no!" Prove to Gill that this too is impossible. Again, you may use pictures to help you explain your proof, but your proof must be clear, precise, and rigorous.
      

5. OPTIONAL BONUS PROBLEM (10 Points) Consider two DFA's. Each of these DFA's can (as usual) receive an arbitrary input string from the outside world. Show how an "Auto Grader" can be built which will take as input two DFA's and will determine whether or not the two DFA's have the same functionality. We showed that this isn't possible for Turing Machines, but amazingly, it is possible for DFA's! Submit your proof on paper to Ran at the beginning of class on Tuesday.