Assignment 12: Automata!
Due Monday, April 19 by 11:59 PM.

To use JFLAP, you will need to have access to the graphics available on turing or one of the terminals in the graphics lab. Because you'll be working with an inherently graphical system, purely text-based interfaces to turing (like putty) won't work for this assignment.

Once you're at a terminal, you can invoke JFLAP by simply typing java JFLAP. A small square menu will appear on your screen. Select the top item Finite State Automaton by clicking on it. (We'll investigate some of the other machines in the next assignment.) Now you'll get a large display in which you can create deterministic or nondeterministic finite automata. The Help menu is useful. Please read through it carefully. It takes less than ten minutes. Notice also that JFLAP has a Save option in the File menu. Make sure to test your machines (DFA's and NFA's) thoroughly in JFLAP before submitting them. Complete documentation on JFLAP is available here. You can even download a copy of JFLAP to your personal computer, in which case you won't have to worry about turing at all... .

For each of the problems below, you should assume that the input will consist of zero or more 0's and 1's. Recall that every state in a DFA must have one outgoing transition labeled 0 and one outgoing transition labeled 1. Remember also that the DFA must accept every string in the 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 a final 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 will be testing this!)

1. In JFLAP, construct a DFA for the language:

     {w | w contains at least three 1's.}
     

   For example, the string 011010 is in the language but the empty string and 01100 are not. Save your DFA in a file called part1. (JFLAP will add its own file extension, so that when you look at your file names, it will be called part1.jff .)
   
   
2. 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 your DFA in a file called part2.
   
   
3. 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. Save your DFA in a file called part3.
   
   
4. Prove that any DFA for the language in the previous problem MUST have at least 6 states. Write a clear and precise proof and save it in a file called part4.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.
   
   
5. 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). The empty string should be interpreted as the number 0 and thus should be accepted. This problem is challenging! Save your DFA in a file called part5.
   
   
6. In JFLAP, construct a nondeterministic finite automaton (NFA) for the language:

     {w | w contains the pattern 00 or 11 or both.}
     

   For example, 1001 should be accepted as should 10110. However, 0101 would not be accepted. Note that JFLAP is just as happy to make NFA's and DFA's. It simply permits you to have multiple outgoing transitions with the same label. Recall that nondeterministic machines do not need to have a transition for each possible input at each state. Your NFA should have at most 7 states and at most 10 transitions. A transition is just an edge from one state to another. A transition with no symbol specified is considered an epsilon move. Note: for the sake of counting the number of transitions, if you have two (or more) transitions that go between the same pair of states, then in theory these could be drawn as one transition with two (or more) symbols on it -- these will count as just one transition! Save this NFA in a file called part6.
   
   
7. 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.) You may use only 9 states in your NFA. Save your NFA in a file called part7
   
   
8. Next, you'll prove that several languages are not regular by using the Nonregular Language Theorem. First, consider the language:

     {w | w consists of n 0's followed immediately by 2n 1's.}
     

   For example, 001111 is in this lanuage (n is 2). However, 010111 is not in the language since this string doesn't have 0's followed immediately by 1's, but rather has 0's followed by 1's followed by 0's followed by 1's. Moreover, 00111 is also not in the language because (although it consists of 0's immediately followed by 1's) the number of 1's is not equal to twice the number of 0's. Prove that that this language is not regular by using the Nonregular Language Theorem. Type your proof into a file named part8.txt. As an example of what such a proof should look like, take a look at the file sampleProof.txt in /cs/cs60/assignments/assignment12/. Notice that simply giving an infinite set S does not suffice. You must also argue that any arbitrary pair of strings from S are always distinguishable!
   
   
9. 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 part9.txt.

   Next week you will build a machine that does accept this language... as this proof shows, that machine will have to be more powerful than a DFA!
   
   

10. Finally, here's something very surprising: In the sampleProof.txt file (in the usual directory, /cs/cs60/assignments/assignment12), 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 the pattern 01 and 10.}
      

    This language contains 0110 (this 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 your solution in the file part10.
    
    
11. OPTIONAL 12 Point Bonus Problem! 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 the most significant digit is at the far left. This 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 stirng 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!

    This bonus problem has two parts. You may turn in one or both parts (for up to 6 bonus points each). Do these on paper and give them to either Zach or Ran in class.

    1. 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. Very nifty!
    2. Now, consider this language's "first cousin": 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 but true!