Assignment 10: Computational Models in JFLAP
Finite Automata and Turing Machines! [100 Points]
Due Tuesday, April 22, 2014, 11:59pm

Review of the proof techniques we (will) have discussed this week...

This link contains placeholders for the proof problems in this assignment and an example proof using the Distinguishability Theorem (to prove a minimum-possible number of states) and the Nonregular Language Theorem (to prove that no DFA can accept a certain language).

JFLAP!

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 their operation with any input string you like. You will also be proving that certain tasks are unsolvable by finite automata (read: computers!)

Batch testing

A note just after the first problem describes how to batch-test your JFLAP machines. Be sure to test your DFAs and Turing Machine!. Here is the zip archive of bacth-tests, each a .txt file.

WARNING - Running JFLAP on the lab macs

JFLAP is present on the CS lab Macs - it's located in Go -- Applications -- Additional Applications -- Programming -- JFLAP.jar. However, if you want to double-click it to start it, you need to double-click the Start JFLAP application located in the same directory.

Alternatively, you can start it from the command line (and no need to log in to knuth, either!) by running

cd /Network/Applications/Programming

java -jar JFLAP.java

You can download a copy of JFLAP for your own computer (or onto the Desktop of the PCs in the LAC lab) for free from this JFLAP software website. The smaller one, JFLAP_Thin.jar is all you will need.

A local copy of this file is also avaiable at this JFLAP_Thin.jar link.

JFLAP is written in java; a jar file packages a group of Java classes in one place. Double-clicking that JFLAP.jar file should start the program (if Java is set up).

Lots of files to submit...!

Similar to previous assignments, you will submit a different file for each of the problems on this assignment. Here, however, there will be lots of files -- please do submit them with the names specified! -- this will make it easy on the graders.

Getting started with JFLAP

When you start JFLAP, you will see a menu that looks something like this:



with a Help menu at the top. In fact, the help option directs you to the tutorial available from this link. (The important parts are the "Finite Automata" and "Turing Machine" tutorials that are linked on the left of the tutorial page.) The documentation is not only thorough, it even has various "haiku-help" versions scattered through it... . (Actually the haiku-help has been made hard to find in recent versions.)

Almost all of our problems use the binary alphabet: { 0, 1 }

For each of the problems below, you should assume that the input will consist of zero or more 0's and 1's. Thus, keep in mind that every state in a DFA [Deterministic Finite Automaton] must have one outgoing transition labeled 0 and one outgoing transition labeled 1. Remember also that a DFA must accept every string in the desired language and reject every string not in the language. Finally, the empty string (λ, lambda) corresponds to no input at all. As a concrete example, consider a language L, defined to be the set of all strings with an even number of 0's. The empty string must be in this language since the empty string has zero 0's -- and zero is even! Thus, a DFA for this language must have its initial state be an accepting state -- that way it accepts even if it gets no input! Be sure that your automata accepts the empty string if it is in the specified language -- we'll be checking this!

A Sample Proof

In addition, because you will be applying some of the theorems from class to write your own proofs, two sample proofs from class are available at this link, along with three placeholders for your own proofs... You are welcome to "copy" as much as you like from these sample proofs when writing your own proofs. You'll submit your proofs in an ASCII plain-text file named proofs.txt.

The problems

The first half of these problems, #1 through #5, should be done individually.

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 and submit your DFA in a file called part1.jff.
   
   
   
• Testing!    Be sure to test your machines!
  
  You can step through your machine, state-by-state, with a specific input by going to the Input menu and choosing Step by state. To test more strings at once, from the Input menu, choose Multiple Run. From there, you'll be able to enter any number of strings and test them all.
  
  Batch testing    We will grade your DFAs and TMs by "batch testing them. It's a good idea to do this yourself -- to be sure your machines meet specifications! To run a batch test, grab one of the files from
  
     this directory of JFLAP batch-testing files
  
  and save it to the same directory in which your JFLAP machines live. Or, grab the whole thing from this zip file and unzip it. Then, close your machine and - from the main JFLAP menu - choose Batch Test. From the first dialog window, navigate to the JFLAP machine you want to test and open it. From the second dialog window, navigate to the .txt file you saved from the above directory and open it. It will open that file within a special Multiple Run interface, and you'll be able to see what worked and what did not... . If the rightmost column is all "Accept" and "Reject," it's passed all of the tests. If you see
  Accept(Reject) or Reject(Accept)
  then the first answer is what your machine computed. The second answer was the value expected by the test file.




2. [5 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. The empty string, with zero 0s should be accepted. Save and submit your DFA in a file called part2.jff.
   
   
   
3. [5 Points] The parity-predictor machine.
   
   In JFLAP, construct a DFA for the language:

     {w | The parity of the # of 0's in w and the parity of the # of 1's in w
                 is equal to the parity of the _first bit_ of the input }
     

   So, if the input's first bit is a 0, then the machine accepts strings with both an even number of 0s and an even number of 1s (and rejects others). Alternatively, if the input's first bit is a 1, then the machine accepts strings with both an add number of 0s and an odd number of 1s (and rejects others). The empty string should be rejected.
   
   For example, 0110 should be accepted, because it starts with 0 and both the number of 0s and of 1s are even. The string 1000000011 should also be accepted, because it starts with a 1 and it has an odd number of 0s and 1s, counted individually.
   
   On the other hand, the strings 001 and 11111 should be rejected by this machine (see if you can determine why... - remember that zero is an even number). Save and submit your DFA in a file called part3.jff.
   
   
   
4. [5 points] Create a DFA or NFA (nondeterministic finite automaton) that accepts the language of binary strings such that the first bit is equal to the second-to-last bit of the string.
   
   Notes: a DFA is an NFA, so it's OK if your solution is a DFA. Also, this is slightly different than the initial description of this problem, but any solution to the previous problem will also solve this one, so if you already solved it, you're set!
   
   Details: if the input string has fewer than two characters, it should be rejected. If a string has exactly two characters, it should be accepted. Other strings that should be accepted include 111, 10111010, and 0010000000. Submit your NFA in the file part4.jff.
   
   Overview of NFAs    Remember that you have more flexibility when specifying an NFA. You may omit transitions - and a path that would otherwise take an omitted transition will be rejected. Also, you may have more than one transition on the same character: in this case, the NFA runs all possible paths and if any possible path input leads to an accepting state, the string is accepted. You may have lambda-transitions that do not consume any input characters at all.
   
   NFA example    Here is an NFA that accepts strings whose 3rd-to-last bit is 1:
   
   Several runs from the multiple-run interface are shown, too. In this NFA, there are two paths for each 1 bit in the input string! For NFAs, it's more natural to reason about paths than individual states. The short path from the start state and back to the start state simply consumes input. If it were the only path, the machine would reject all strings. But the second path, which follows each one bit, provides a chance for the string to be accepted. If the 1 is the third-to-last bit, the input will land in the accepting state; if there are too many bits after the 1, that possible path "dies," because there is no outgoing transition to follow from the accepting state. Also, if there are too few bits after the 1, that path will also be rejected. As long as one (or more) valid paths ends in an accepting state, an NFA accepts! Here's an image to summarize this:
   
   
   This example also highlights that NFAs can - sometimes - use fewer states than an equivalent DFA. The next problem will show another such example.
   
   
   
5. [10 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 -- though you need not prove it.) However, for credit for this NFA, it may have at most 9 states. Save your NFA in a file called part5.jff. Again, since 0 is a multiple of 3 (or 5, for that matter), the empty string should be accepted.
   
   Hint: consider creating two transitions on a 0 out of the initial state -- each one can handle one of the two ways this NFA can accept strings. (Using two lambdas will work, too.) Be sure, however, that 8 0s is not accepted by your final machine!
   
   
   

   The subsequent problems, #6 through #10, may be done in pairs or individually.

   
   
   
   
6. [10 Points] In JFLAP, construct a DFA for the language:

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

   For example, the inputs 0, 111, 1110, 10101, 11100, and 100011 would all be accepted because they are the binary representations of the numbers 0, 7, 14, 21, 28, and 35, respectively.
   
   Note! Keep in mind that the DFA reads input from left to right, so that the first digit seen will correspond to the most significant digit and the last digit seen is the least significant digit.
   
   The number may is permitted to begin with leading zeroes (for example, 010101 is OK because it is still 21). For this problem the empty string should be interpreted as the number 0 and, thus, the empty string 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.
   
   Caution: this problem is tricky - consider carefully how reading a 1 or a 0 changes the value of the binary number being built... especially because the number is being built in the "wrong direction," so to speak.
   
   Save and submit your DFA in a file called part6.jff.
   
   
   
7. [10 Points] Prove that any DFA for the language in problem 2 MUST have at least 6 states. This was the DFA from part2.jff, the machine that accepts strings whose number of zeros is a multiple of 2 or a multiple of 3 (or both).
   
   You will need to use the idea of pairwise distinguishable sets of strings as we covered in class. You might use the example proof as both starting guide and template.
   
   Write a clear and precise proof and save/submit it in a file called proofs.txt.
   
   Note, too, that since the part2.jff DFA for this language had 6 states, you have proven that that machine is the most-efficient-possible DFA for this language!
   
   
   
8. [10 Points] Next, you'll prove two 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 palindrome 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. Save and submit your proof in tha same file as above, namely proofs.txt.
   
   As an example of what such a proof should look like, take a look at the second example in the file proofs.txt. Notice that simply giving an infinite set S does not suffice. You must also argue that an arbitrary pair of strings from S are always distinguishable!
   
   
   
9. [10 Points] Another non-regular language   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 - include it in the same proofs.txt file.

   
   
   
   
10. [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. That is to say, 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 fewer than nine states. (Perhaps far fewer -- see the extra credit...)

    Save your Turing Machine in a file called part7.jff.

    • To create a turing machine, select Turing Machine option from the initial JFLAP window. You may want to read the instructions on Turing Machines from the JFLAP on-line tutorial.
      
      
    • 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.
      
      
    • You can assume that the input will be a single, contiguous block of all 0s. Also, you may assume that if there are any 0s on the turing machine's tape, that the read/write head starts at the leftmost zero. Remember that there may be zero 0s!
      
      
    • Remember that Turing Machines can write any symbols they like on the tape. Your Turing Machine may 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. However, 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.
    
    
    
    
11. [5 Points] A surprise...?! In the proofs.txt file 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 substrings 01 and 10.}
      

    
    The substrings may overlap -- thus, this language contains 0110, which 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!).
    
    Perhaps surprisingly, this language is regular! Show that this is true by building a DFA or NFA for this language using JFLAP. Save and submit your solution in a file named part8.jff.
    
    

Three totally optional and fun extra credit challenges...

• ExCr 1 [up to +5 (or even 10) points] State-minimizing Turing Machines Extra credit is available for turing machines that accept problem 9's language with as few as possible states. The minimum possible is three states (and this includes the accepting state!), for which +10 points of extra credit is available. Four states = +5, and five states = +2. The trick here is to use more symbols that help "offload" the effort of storing state! Save and submit this turing machine in a file named excr1.jff.



• ExCr 2 [up to +5 points] The binary-addition DFA!
  
  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 alphabet of only three-character strings:

    000
    001
    010
    011
    100
    101
    110
    111
    

  JFLAP will take multiple-character strings as transitions -- as you do this, it will consume three symbols at a time. Here's a screenshot:
  
  For interpreting these transition strings, however, let's write each of them vertically. So, the eight symbols above are now imagined 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
    

  Next, we 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!
  
  As is usual with arithmetic, whether decimal or binary, the numbers are interpreted so that the most significant digit is at the far left (first input) and the least significant digit is at the far right (most recent input, so far...).
  
  This corresponds to the usual interpretation of a string of 0s and 1s as a binary number. It also 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 accepted by the language of valid additions since the sum of the binary numbers 1010 (first row) and 0010 (second row) is 1100 (third row)s, i.e., 10+2==12 in decimal. Thus, the string 101001110000 should be accepted by the DFA you build here.

  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! Thus, the string 100110 should be rejected by the DFA you build here.

  For this problem, 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! Do not include your proof in the regular file you wrote for the above problems. Instead, include the proof in a note (right-click and choose Add Note) directly in your JFLAP file.

  Save and submit your DFA and proof (in a JFLAP note) into a JFLAP file named excr2.jff.

  
  
  
• ExCr 3 [up to +5 points] Binary multiplication - is not regular!
  
  For an additional +5 points, add a second note to your excr2.jff file that considers the language of "valid multiplications," in the same style as the above language of "valid additions." The "valid multiplications" is the language of three-character strings 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: addition is regular, multiplication is not (at least in this sense...)! No new files to submit -- this will be in your excr2.jff file.