Assignment 11: Computational Models in JFLAP -- Automata and Turing Machines! [100 Points]
Due Tuesday, November 25th, 2008, 11:59pm

Review of the proof techniques we will discuss 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!)

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 most likely already is, because of the java assignments you wrote! If it's not, feel free to ask. Under windows, the path is set in the "System Contol Panel - Advanced - Environment Variables."

Lots of files to submit...!

In contrast to the prolog assignments, You will submit a different file for each of the problems on this assignment. Some will be JFLAP files, which you should name as the problem specifies to 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... .

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. Note, for example, that if the language L is the set of all strings with an even number of 0's, then the empty string is in this language since it has zero 0's -- and zero is even! Thus, a DFA for this language must have the initial state be an accepting state, so that it accepts even if it gets no input! Be sure that your automata accept the empty string if it is in the specified language -- we'll be checking this!

A Sample Proof

Finally, since you will be applying some of the theorems from class to write your own proofs, a sample proof 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.

The problems

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. 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] JFLAP can convert Regular Expressions to NFAs, NFAs to DFAs, and DFAs to Regular Expressions. However, in the process it can sometimes add more states than are strictly necesary. Determine what regular expression it is that JFLAP has turned into the NFA in the image near the top of this webpage. (You may want to click on it to get a closer view!) Submit this as part4.txt and add a couple of sentences that describes the language generated by the regular expression.

   Though not required, remember that you can use JFLAP to check any regular expression to see if it's the same. I suppose guessing and checking would be one way to solve this problem, though not a very efficient one -- (and you'll have to move states around to make things match, as well). If you do experiment with JFLAP's regular expressions, keep in mind that JFLAP uses + instead of the vertical bar | to indicate "or" alternatives.




5. [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 part5.jff.
   
   
6. [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 part6.jff. Again, since 0 is a multiple of 3 (or 5, for that matter), the empty string should be accepted.
   
   
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 excr.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 - no DFA!
  
  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.