Assignment 12 Lite: NFAs and Turing Machines!
Due Monday, November 24 by 11:59 PM
HOWEVER, Part 3 should be submitted on paper at the beginning of class on Tuesday.

1. 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.

   Your job is to write a file called part1.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/assignment12/nfa.pl. You can copy this file into your directory. Then, when entering Prolog you could load in both your part1.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
     | ?- ['part1.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!
   
   

2. Turing Machines! [35 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. I 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. (It's actually possible to use substantially fewer than nine states, but it's tricky!) Save your Turing Machine in a file called part2.TM.

   • 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. (It suffices to just use one type of other sybmol, but you are welcome to use more if you wish.)
   • 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.
   
   
3. Millisoft (25 Points) This part of the assignment should be submitted 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. "Here's the deal," says Gill. "Millisoft has a lot of software that we use to develop our outstanding products. All of these programs take an input and answer 'yes' or 'no'. (Such programs are called deciders.) Anyhow, we have a lot of these kinds of programs around and we don't want to store two programs that have exactly the same functionality. We'd like to build a program called the Different Checker which takes as input two programs (each of which is a decider) and says 'yes' if the two programs have different functionality and says 'no' otherwise. Remember, 'different functionality' means that there exists some input on which the two given deciders give different answers."

   Write a clear proof (logically rigorous explanation) of why this is not possible under the assumption that the programs may run on a computer with effectively unlimited memory. You may use pictures to help you in your proof, but you must have clear prose explaining every step and explaining the contradiction that arises. Your submission will be graded on clarity and precision of explanation.

4. OPTIONAL BONUS PROBLEM (15 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 in class on Tuesday.