Assignment 13 Lite: NFAs and Turing Machines! [65 Points]
Due Sunday, April 30 by 11:59 PM

Please note that this assignment is due on Sunday night rather than Monday night.

In this assignment you will be playing with NFA's and Turing Machines.

1. NFA's meet JFLAP! (15 Points)
   JFLAP allows you to create and run nondeterministic finite automata just as you would deterministic ones. Even "lambda" transitions are permitted (and you may want to use them!). 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. (JFLAP will automatically add the suffix ".jff" when it saves the file.) 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.

   You do not need to worry about "lambda" moves for your NFA's. We will not consider them here.

   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! (30 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 (i.e. it cannot be accepted by any DFA).

   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.