Assignment 11: Automata!
Due Monday, November 17 by 11:59 PM.

You will be using 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! To use JFLAP you will first need to edit your .cshrc file. In particular, add the line

setenv CLASSPATH /cs/cs60/jflap

Once you've made the above changes to your .cshrc file, 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.

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 labelled 0 and one outgoing transition labelled 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 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.

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.FA.
   
   
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.FA.
   
   
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.FA.
   
   
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 can now conclude that this is the smallest DFA 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. Think about it. Save your DFA in a file called part5.FA.
   
   
6. In JFLAP, construct a nondeterministic finite automata (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. In the old version of JFLAP, a single transition may be labeled with two (or theoretically more) symbols by just putting a comma between the symbols. Evidently, in the new version of JFLAP you cannot do this. In any case, for the sake of counting the number of transitions, if you have two transitions that go between the same pair of states, in theory this could be drawn as one transition with two symbols on it and therefore you may count this as just one transition! Save this NFA in a file called part6.FA.
   
   
7. In JFLAP, construct a nondeterministic finite automata (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.FA
   
   
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. Leave your proof in electronic form in a file called part8.txt. As an example of what such a proof should look like, take a look at the file sample.txt in /cs/cs60/assignments/assignment11/. 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 and 1's whose length is a power of 2}
     

   For example, the strings 0, 01, 0011, 10100000 are all in the language since their lengths are 1, 2, 4, and 8, all of which are powers of 2. 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.
   
   
10. Finally, here's something very surprising: In the sample.PROOF 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.FA. This one is challenging. Think about it!