Assignment 11: Computational Models in JFLAP
Finite Automata and Turing Machines! [100 Points]
Due Monday, November 21, 2011, 11:59pm

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

This link contains a review of the Distinguishability Theorem and the Nonregular Language Theorem, and how to use them.

JFLAP!

Click for a larger image of this example JFLAP NFA...

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!)

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 10 or more of them! Some will be JFLAP files, which you should name as the problem specifies -- this will make it easy on the graders. Others will be plain-text files (.txt) which will hold your proofs. Submit the files via the website as usual, but please do name them according to the problem specification!

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 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, a sample proof using the nonregular language theorem is available at this link. You are welcome to "copy" as much as you like from this sample proof when writing your own proofs. Simply submit each proof in an ASCII plain-text file with a name as designated by the specific problem.

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.
   
   
   
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. [10 Points] Prove that any DFA for the language in the previous problem (part 2) MUST have at least 6 states. You will need to use the idea of pairwise distinguishable sets of strings as we covered in class. Although the proof example at this link uses the nonregular language theorem, i.e., an infinite set of pairwise distinguishable strings, it is still a reasonable starting template and guide to your write-up for this problem.
   
   Write a clear and precise proof and save/submit 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 show 15 separate cases of pairwise distinguishable strings. This is fine, because the cases are short -- however, with a little bit of thought you may be able to have considerably fewer cases in your analysis!
   
   
   
4. [5 points] Create either a DFA or an NFA (nondeterministic finite automaton) that accepts the language of binary strings such that the first two characters are equal to the last two characters of the string. 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 DFA or NFA in the file part4.jff.
   
   Remember that you have more flexibility when specifying an NFA: you may omit transitions - and a string that would otherwise take an omitted transition will be rejected. Also, you may have more than one transition on the same character: if any possible path taken by an input leads to an accepting state, the string is accepted. In the same spirit, you may have lambda-transitions that do not consume any input characters at all. Often you can use fewer states in specifying an NFA than in a DFA for the same language.
   
   
   
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.
   
   
   

   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. For full credit, your solution may not use more than 8 states (it's possible, in fact, to use fewer).
   
   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] 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 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 a file named part7.txt.
   
   As an example of what such a proof should look like, take a look at the file sampleProof.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!
   
   
   
8. [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 part8.txt.

   
   
   
   
9. [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 part9.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.
   
   
   
   
10. [10 Points] A surprise...?! In the sampleProof.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!).
    
    Amazingly, 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 part10.jff.
    
    

Three totally optional and fun extra credit challenges...

• ExCr 1 [up to +5 points] Extra credit is available for turing machines that accept problem 9's language with as few as possible states. The minimum possible in three states (including the accepting state!), for which +5 points of extra credit is available. Four states = +3, five states = +1. For a further challenge (or "fun"?), you might consider how few symbols you can use once you've minimized the number of states... . 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 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 having the most significant digit is at the far left. 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 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!

  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! JFLAP is happy to allow three characters along a single transition, which is what you will need in this case.

  Save and submit your JFLAP DFA in a file named excr2.jff and submit your proof that no fewer states are possible in a file named excr2.txt.

  
  
  
• ExCr 3 [up to +5 points] Binary multiplication - is not regular!
  
  Alternatively (or in addition, if you like!) consider an extension to the final DFA from part 10, above. Rather than the language of "valid additions," consider 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 yet true! Save and submit your proof in a file named excr3.txt.