Problem Set 10

due by 11:59 p.m. on Thursday, December 5, 2024

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 the assignment.

Preparing for the Assignment

Creating the necessary folder

Create a subfolder called ps10 within your cs111 folder, and put all of the files for this assignment in that folder.

Installing the necessary software

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

If you haven’t already done so, you should follow the instructions for installing and configuring the necessary software are available here:
Instructions for installing JFlap

If you encounter issues in using JFlap on your computer, you should consult the troubleshooting information that we have provided. You can also use JFLAP on the virtual desktop.

Starter files

Once you have installed JFlap, you should download the following collection of starter files: ps10_jflap.zip

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.

The Problems

Problem 0: Simplifying an existing FSM

8 points; individual-only

Run JFlap by double-clicking on the JFLAP.jar file that you downloaded as part of the installation process.

(Remember that if you encounter issues in using JFlap on your computer, you should consult the [troubleshooting information] (jflap_install.shtml#dealing-with-jflap-issues-on-a-mac) that we have provided. You can also use JFLAP on the virtual desktop.)

Then use File->Open to open the problem0.jff file that was in the zip file that you downloaded above.

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.

If you get stuck while working with JFLAP, there’s an online tutorial that can be found here. Because we’re only working with deterministic FSMs, you should limit yourself to the first 7 sections of the tutorial.

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: No consecutive repeats

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 there are no “consecutive repeats” – i.e., in which consecutive bits are never the same – and that rejects all other bit strings.

This problem requires at least four 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:

10
010101
1010
0

Here are three strings that should be rejected:

11
1010100010
010111

Problem 2: Focusing on the 1s

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 number of 1s is either odd or a multiple of six, and that rejects all other bit strings. The number of 0s does not matter.

This problem requires at least six 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 6!
1100100001011    # six 1s
010101           # three 1s, because three is odd

Here are three strings that should be rejected:

101 
1111 
011011011011

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

14 points; individual-only

We will discuss this problem in lecture on December 2.

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

Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 111.

Submit your problem0.jff, problem1.jff, problem2.jff and problem3.jff files using these steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add all of your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Because your JFlap files have a format that Gradescope can’t read, you won’t be able to view those files on the Code page. Instead, you should click on the Download button for each Scratch file to download it. Once you have done so, open the downloaded file in JFLAP to ensure that the uploaded file is the correct one.

Last updated on December 2, 2024.