Assignment 11 "lite": Computational Models in JFLAP [50 Points]
Due Monday, April 18 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.20

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

On the lab Macs, JFLAP is 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 on the Macs in the CS lab) for free. It is available at www.jflap.org. To simplify downloading, you can also get a copy of JFLAP.jar from this local link. If you do go to the JFLAP site, follow the Get JFLAP link on the green left menu. From there, go to the bottom of the page and select "JFLAP software". You'll need to fill out a brief form to let the creators know who's using their software, and then choose the latest "JFLAP.jar."

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

Alternatively, you start JFLAP from a command prompt (unix or windows) by typing java -jar JFLAP.jar. For this to work, java needs to be "in your path," which it may already be, because of the java assignments you wrote! If it's not, feel free to ask. Under windows, the path is set via the "System Contol Panel - Advanced - Environment Variables."

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 5 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 version.)

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 #3, 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!
   

   
   
   The subsequent problems, #4 through #6, may be done in pairs or individually.  If you work with a partner, please work with the same partner for all problems (but you can complete any of them individually still).  In addition, we STRONGLY RECOMMEND that both partners practice writing up the proofs in numbers 5 and 6.  (You only need to submit one version, but it's good practice to at least write up one on your own, even if you come up with the proof idea with a partner).
   

4. [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 part4.jff.
   
   
   
5. [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 part5.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!
   
   
   
6. [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 part6.txt.

   
   

A totally optional and fun extra credit challenge...

• ExCr [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 excr.jff and submit your proof that no fewer states are possible in a file named excr.txt.