Problem Set 10

due by 11:59 p.m. Eastern time on Thursday, December 3, 2020

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please come to office hours, post them on Piazza, or email cs111-staff@cs.bu.edu.

Make sure to submit your work on Gradescope, following the procedures found at the end of Part I and Part II.

Part I: Final Project Milestone

Complete at least Parts I and II of the Final Project, and submit a version of your finalproject.py file that includes at least your work on those parts of the project. Submit it to the Final Project Milestone page on Gradescope, following the procedures found in that assignment.

It’s okay if you have already completed more than Parts I and II. Just make sure that the file that you submit can be used to test your work on Parts I and II.

If your file includes incomplete work for Parts III-V that might prevent us from testing your work for Parts I and II, you should copy the file into a different folder (keeping the same name), and remove any code that might interfere with our testing. Test your file before you submit it by running it in IDLE and making calls to your methods/functions from Parts I and II.

Your final submission of the entire project (Parts I-V) will be made elsewhere. See the Final Project page for more detail.

Part II: Finite State Machines

Getting started

In this part of the assignment, you will practice building finite state machines (FSMs) using a software simulator called JFlap.

You first need to install the Java runtime environment on your own machine. Here are the instructions for doing so:

• for Windows
• for MacOS

Next, download the following two files:

• JFLAP.jar - the JFlap application itself
• ps10_jflap.zip - a zip file containing a starter file for each of the problems.

Next, unzip ps10_jflap.zip into the folder that you are using for this assignment. You should see a number of files with a .jff extension. You will use these files for the problems below.

There is an online tutorial for JFlap; the material that is relevant to this assignment is found in the first 7 sections of the table of contents that can be found here. (Note that the authors of the tutorial use the term finite automaton, which is another name for a finite-state machine. We are only concerned with deterministic FSMs, so you can ignore the sections on nondeterministic finite automata.)

Dealing with JFlap issues on your own machine

If you have trouble getting JFlap to work on your machine, you may need to take one or more of the following steps:

1. Install the Java runtime environment following the instructions provided above.

2. If you are using a Mac and you are unable to download JFlap.jar using Chrome, you should try using Safari instead.

3. If you are using a Mac and are still having trouble after you switch to Safari, you may need to lower your security settings.

4. If you are on a Mac and are unable to run JFLAP, try moving JFlap.jar to your Applications folder.

5. If you are on a Mac and you can’t save one of your .jff files to your Desktop, try saving it to a different folder.

6. If you are using Windows and cannot run the JFLAP.jar file even after installing Java, try taking the following steps;

   1. Open the command prompt (search for cmd in the search bar/start menu and hit Enter when you find it).

   2. Use the cd command to navigate to the folder in which the the .jar file was downloaded. In most cases, you can simply do the following:

      cd Downloads
      

   3. Enter the following command from the downloads folder:

      java -jar JFLAP.jar
      

7. If you are using Windows and the size of the JFlap window is extremely small, you may need to temporarily lower your screen resolution to make JFlap larger.

Working on the virtual desktop

If you can’t get JFlap to work on your own computer, you can use it on the virtual desktop. Once you are in the virtual desktop, you should find a folder named JFLAP that contains the necessary program.

Problem 0: Simplifying an existing FSM

8 points; individual-only

Run JFlap by double-clicking on the JFLAP.jar file that you downloaded above. Then use File->Open to open the problem0.jff file that we have given you.

In problem0.jff, you will see the following FSM:

This deterministic finite-state machine accepts all bit strings whose third bit from the left is a 1, and rejects all other bit strings. In other words, the accepted bit strings must have at least 3 bits, and the third of those bits must be a 1.

The problem of accepting bit strings whose third bit is a 1 can be solved using only five states, but the provided FSM uses six. Simplify the FSM so that it uses five states and still works correctly.

Make sure that your simplified FSM still accepts inputs like the following:

0110
111
001
10101

and that it still rejects inputs like the following:

0100
0001
11
10011

Problem 1: Focusing on the 1s

14 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

Run JFlap, and use File->Open to open the problem1.jff file that we have given you.

In problem1.jff, build a deterministic finite-state machine that accepts all bit strings in which the number of 1s is either odd or a multiple of five or both, and that rejects all other bit strings. The number of 0s does not matter.

This problem requires at least ten states. You may use more states if necessary (there’s no penalty for doing so), but if you have time, try to get as close to the minimum as possible!

Here are three examples of strings that should be accepted:

000              # zero 1s -- and zero is a multiple of 5!
1100100001010    # five 1s
010101           # three 1s, because three is odd

Here are three strings that should be rejected:

101 
111111 
01010101

Problem 2: Comparing the outer bits

14 points; individual-only

Run JFlap, and use File->Open to open the problem2.jff file that we have given you.

In problem2.jff, build a deterministic finite-state machine that accepts all bit strings in which the first and last bits are the same, and that rejects all other bit strings. It should not accept the empty string.

This problem requires at least five states. You may use more states if necessary (there’s no penalty for doing so), but if you have time, try to get as close to the minimum as possible!

Here are three examples of strings that should be accepted:

01010
1
11101

Here are three strings that should be rejected:

01
0010011
11110

Problem 3: Focusing on the third-to-last bit

14 points; individual-only

We will discuss this problem in lecture on November 30.

Run JFlap, and use File->Open to open the problem3.jff file that we have given you.

In problem3.jff, build a deterministic finite-state machine that accepts all bit strings in which the the third-to-last bit is a 1, and that rejects all other bit strings. This problem is a bit tricky, and we’ll discuss it in class, so we encourage you to consult the lecture notes.

This problem requires at least eight states. You may use more states if necessary (there’s no penalty for doing so), but if you have time, try to get as close to the minimum as possible!

Here are four examples of strings that should be accepted:

0101
100
11110101000100
1101

Here are three strings that should be rejected:

10
11111001
011011

Submitting Your Work

Coming soon!

Last updated on December 2, 2020.