CS 60, Assignment 12

Harvey Mudd College
Computer Science 60
Assignment 12, Due Thursday, December 9, by midnight

Finite-state machines

In this assignment you will be examining the abilities and limitations of computers. We will model a computer by a finite automaton and will examine which languages can be accepted by these machines and which cannot. In addition, you will be building a turing machine to accept a language which no finite-state automaton accepts. All of the machines will be built with the help of a Java-based graphical interface called JFLAP, described in detail below.

Important submission directions!

Begin by creating a directory called a12 in your cs60 directory:

mkdir a12

Make sure that the a12 directory is protected so that only you can read and write to it:

chmod 700 a12

Then, when you are working on the following problems, be sure to work from the a12 directory and to save all of your files in that directory.

Important JFLAP directions!

JFLAP's java code is in /cs/cs60/jflap.new. In order to use it, you will need to edit your .cshrc file. In particular, find the line in your .cshrc file that looks like:

setenv CLASSPATH $JAVA_HOME/lib:/cs/cs60/java/:.

(or something similar to this). At the end of this line add :/cs/cs60/jflap.new so that the line now reads

setenv CLASSPATH $JAVA_HOME/lib:/cs/cs60/java/:/cs/cs60/jflap.new

This will allow java to find JFLAP. Now type source .cshrc and you'll be all set!

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 X-windows. In any case, JFLAP works best with a 3-button mouse but is usable with a 2-button mouse.

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. 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 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.
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 of course have as many final states as you wish.
You can move a state around by clicking on it with the middle mouse button down. You can then drag the state around.
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.

For each of the problems below, you should assume that the input will consist of zero or more 0's and 1's. Remember that the DFA must accept every word in the language and reject every word not in the language. Finally, the empty string corresponds to no input at all. Note 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!

(5/3 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.
(5/3 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.
(5/3 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.
(10 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 binary representation.) (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 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.
(10 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.}
  
```
A straightforward approach to this problem uses at least 15 states. Try to use as few states as possible in your FA. Save your FA in a file called part6.FA
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. 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!) Save your Turing Machine in a file called part7.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. Make sure to read 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 part 7 that use fewer than ten states, up to 20% for a solution using only 3 states.

Reading

Finite state machines (and the languages they accept) are considered in Chapter 12 of the text.

Submission

You will not be using cs60submit in this assignment. Instead, you should save your JFLAP files (with names part1.FA to part6.FA and part7.TM) in the a12 directory of your cs60 directory. We will grade the assignments by running a script that copies your files into a local cs60grad directory when the assignment is due.

Harvey Mudd College Computer Science 60 Assignment 12, Due Thursday, December 9, by midnight