Assignment 10: DFAs and NFAs in JFLAP and Prolog! [100 Points]
Due Monday, November 19th, 2007, 11:59pm

Review of the proof techniques we've discussed so far...

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

Part 1: Automata in JFLAP [60 points]

JFLAP!

Click for a larger image of an 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 them 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. At that web site, follow the "Get JFLAP" link on the green left menu. From there, go to the bottom of the page and select "JFLAP software". After you have filled out the download form, choose the latest "JFLAP.jar" (September, 2006).

JFLAP is written in java and when you download it you will get a file called JFLAP.jar. You start JFLAP from a command prompt (unix or windows) by typing

 java -jar JFLAP.jar

Lots of files to submit...!

In this part, you will submit a different  file for each of the problems on this assignment.  Some of your files will be JFLAP files and others will be .txt files containing explanations or proofs.  Include these files in your hw10.zip file.

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. Choose the "Help" option from the Help menu, and then hit the "back" button or "main index" button to get to the main Help screen.

Take a couple of minutes to read the first "Editors" link, called "Automata" - this includes DFAs, NFAs, and Turing Machines, which you'll be building in this assignment. If you prefer online documentation, check out the tutorial available from this link.. The documentation is not only thorough, it even has a version entirely in haiku (scroll down to read that...)!

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

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_1.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 part1_2.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 part1_3.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. [10 Points] In JFLAP, construct a DFA for the language:

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

   For example, the inputs 101, 1010, and 1111 would all be accepted because they are the binary representations of the numbers 5, 10, and 15, respectively. Remember that the DFA reads input from left to right, so that the first digit seen is the most significant digit and the last digit seen is the least significant digit. The number may begin with leading zeroes (for example, 000101 is OK). For this problem the empty string should be interpreted as the number 0 and thus 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 7 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 part1_4.jff.
   
   
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 part1_5.jff. Again, since 0 is a multiple of 3 (or 5, for that matter), the empty string should be accepted. 
   
   
6. [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 part1_6.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!
   
   
7. [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 part1_7.txt.

Part 2: Automata in Prolog [40 points]

Part 2.1 [30 points]

• At least 3 tests of each of your helper predicates.  If you have successful tests of your helper predicates, we will give you partial credit if you accept does not fully work. If you do not have these tests, you will not get partial credit. 
• At least 3 tests of your accept predicate.

Part 2.2 [10 points]

1. Why does your predicate from part 2.1 NOT work if SymbolSequence is a variable?  (If your predicate already DOES work if SymbolSequence is a variable, good job!  You can skip this question).
   
2. Map out a rough design for a predicate gen_accept(DFA, Sequence) to generate the set of accepting sequences of the DFA,
    one at a time.
   
   If the set of sequences is infinite, it should go on generating forever.  However, if the set of is finite, it should fail after the last sequence is generated. Thus, "setof" and the usual testing framework should be OK for testing, as long as there are finitely many accepting sequences in the language of the DFA.
   
   Include as much detail as possible in your design, including what "helper predicates" you will create, and how these helper predicates will help you solve the overall problem.  Also include any issues you forsee at any point.   It's OK if your design is not totally finished, but you should get as detailed as you can.  Feel free to talk to anyone else in the class about this section.
   
   Optional: If you would like a real challenge, you should consider how to generate all the strings accepted in order of increasing length.  This would allow your predicate to generate, for example, all the strings accepted by a DFA with length < N, even if the language is infinite.

Part 3: Totally optional extra credit 

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

  
  
• ExCr 2 [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 ecmult.txt.