Submitting your assignment

cs60submit part1.FA

Please make sure your files are named as described in the problems below (part1.FA, part2.FA, ..., part8.TM), so that the submission script will recognize them.

JFLAP!

You will be using the 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 must be running JFLAP from one the terminals in the CS lab or from a machine that supports xwindows (or an xwindows emulator). In any case, JFLAP works best with a 3-button mouse but is usable with a 2-button mouse. (Mac users can emulate a three-button mouse by using the shift and command keys.)

Invoke JFLAP by simply typing java JFLAP. If a "java.lang.NoClassDefFoundError: JFLAP" exception occurs, you need to put /cs/cs60/jflap in your CLASSPATH environment variable in your .cshrc file. If you had your account created this semester, however, everything should work OK.

JFLAP will draw a small rectangular menu on your screen. Select the top item Finite State Automaton by clicking on it. Now you'll get a large display in which you can create deterministic or nondeterministic finite automata. The Help menu is useful. Read through it for tips. It takes less than ten minutes. Here are some quick pointers:

• Create new states by clicking with the middle mouse button inside the JFLAP window.
  
  
• Create a transition (an arrow from one state to another) by clicking on the start state with the left mouse button and releasing the button on the destination state. You'll then see a line between the two states and a little box with an arrow in it. You can then go into that box and type the symbol (0 or 1) for this transition.
  
  
• You can make a transition from a state to itself by simply clicking on the state with the left mouse button and then releasing the left mouse button while still within that state.
  
  
• You can edit a state by clicking on it with the right mouse button. This will then allow you to make the state an initial state, final state, or remove the state. You can only have one initial state and the default is that the first state that you created is the initial state. You can create as many final states as you wish.
  
  
• You can move a state around by clicking on it with the middle mouse button down and then dragging.
  
  
• You can run the machine on an input word by tying the input word in the "Input String" bar. You then select "Run" from the menu bar. You can run the machine in "Step" mode or "Fast" mode. Try both.
• If you have a two-button mouse, hitting both buttons together simulates the middle button on a three-button mouse.
• If you have a one-button mouse (e.g., are running on a Mac with an X emulator), then the option and control keys allow you to simulate the other two mouse buttons.

The problems

1. (2 pts.) In JFLAP, construct a DFA (deterministic finite automaton) 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. Remember that DFAs must contain a transition from every state for each symbol in the alphabet (in our case the possible symbols are 0 and 1). Save your DFA in a file called part1.FA.
   
   
2. (2 pts.) 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. (2 pts.) In JFLAP, construct a DFA for the language:

     { w | w is any string other than 11 and 111. }
     

   For example 0111 is in the language. The only strings not in the language are 11 and 111. Save your DFA in a file called part3.FA.
   
   
4. (9 pts.) In JFLAP, construct a DFA for the language:

     { w | w is the binary representation of a positive integer divisible by 6. }
     

   For example, 0, 0110, and 10010 are in the language, but the empty string, 10, and 0100 are not. Leading zeros don't affect the value of a number, and all numbers are represented with the most-significant bit first (on the left). (Hint: you might want to try to construct a DFA which accepts binary strings that represent integers divisible by 3 first.) Save your FA in a file called part4.FA.
   
   
5. (5 pts.) In JFLAP, construct a finite automaton (NFA or DFA) 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. Try to use as few transitions as possible! Save this NFA in a file called part5.FA.
   
   
6. (5 pts.) In JFLAP, construct a finite automaton (NFA or DFA) for the language:

     { w | The number of 0's in w is a multiple of 3 or a multiple of 5 or both. }
     

   For this problem, your finite automaton should not consider 0 a multiple of 3 or 5 -- that is, you should reject strings that contain no 0's at all. A straightforward approach to this problem uses 15 states. Try to use as few states as possible in your FA. Save your FA in a file called part6.FA
   
   
7. (5 pts.) It turns out that the language

     { w | w contains an equal number of 0's and 1's in any order. }
     

   is not a regular language -- that is, there is no finite-state automaton that accepts this language.

   However, consider the following closely related language:

     { w | w contains an equal number of occurences of 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 part7.FA.
   
   
8. Turing Machines
   
   (20 pts.) Consider the language

     L = { w | w contains only 0's and the length of w is a power of 2 }.
     

   That is, the language contains all strings of 0's whose length is a power of 2.
   
   
   • Although this language is not accepted by a DFA, it is accepted by a Turing Machine! Use JFLAP to construct a Turing Machine that accepts this language. You can assume that the inputs to the turing machine will be strings of 0's and no other character. (But they will not all have length equal to a power of 2!) I 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 surprisingly few states. (It's actually possible to use only three states, but it's tricky -- see the extra credit!) Save your Turing Machine in a file called part8.TM. Here are some important points about constructing Turing Machines in JFLAP:
     
     
     • When you start JFLAP (by typing java JFLAP) you should select 1-tape Turing Machine from the JFLAP window. You may want to check out the instructions in the Help menu.
     • Notice that blank symbols are represented by uppercase B.
     • Your machine need not have transitions for the input symbol 1. You can assume that the input will be all 0's.
     • Remember that Turing Machines can write any symbols they like on the tape. Your Turing Machine will need to write symbols other than 0.
     • JFLAP allows you to specify multiple states as accepting states and doesn't have an explicit rejecting state. 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.

Extra Credit

Extra credit will be given for solutions to the turing machine problem that use six or fewer states, up to 20% for a solution using only 3 states -- which can be done, even using one of those states as the accepting state! However, you will certtainly have to write symbols other than 0 and 1 to the tape... .

If you find a solution with 3 states, you must have a flair for optimizations -- so additional bonus credit (20%) is available for the 3-state turing machine that uses the fewest different symbols in its program. The record minimum number of symbols that CS 60 students (and instructors) have found for this TM so far is 6. (I do not know what the theoretical minimum is for this, but would like to!)

Reading

Finite state machines (and the languages they accept) are considered in Chapter 12 of the text. Additionally, Turing machines and generala state-transition models are covered in Chapter 6.