CS 111
Spring 2018

Old version

This is the CS 111 site as it appeared on May 10, 2018.

Problem Set 10

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 Apollo, following the procedures found at the end of the assignment.

Part I

due by 11:59 p.m. on Sunday, April 22, 2018

Task 0: Project milestone

Complete at least Parts I and II of the Final Project, and submit your board.py and state.py files to the Problem Set 10 page on Apollo, following the procedures found at the end of the 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 board.py or state.py file includes incomplete work for the later parts of the project that might prevent us from testing your work for Parts I and II, you should copy the file(s) in question into a different folder (keeping the same name), and remove any code that might interfere with our testing. Test each file before you submit it by running it in IDLE and conducting tests of the code that you wrote for 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

due by 11:59 p.m. on Thursday, April 26, 2018

Task 1: Online survey

This survey will ask you about aspects of the course that are not explicitly covered by the standard in-class course evaluations.

Please go to the Blackboard site for the course (entering your Kerberos username and password as needed), click on Other Content in the navigation bar, and click on end-of-semester survey to access the survey.

Your responses will be anonymous. Thanks in advance for your feedback.

Task 2: Finite State Machines and JFLAP

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

Begin by downloading the following two files:

Next, unzip ps10_jflap.zip into the folder that you are using for this assignment. You should see five separate 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 can be found here. In particular, we encourage you to read over the first 7 sections on that page. 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.

Important

In the FSMs that you construct for this problem set, each state should have exactly one transition for 0 and exactly one transition for 1.

Problem 0: Simplifying an existing FSM

6 points; individual-only

Run JFLAP by double-clicking on the JFLAP_Thin.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:

jflap-problem0.png

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.

Warning

When you want two different characters to act as transitions from one state to another, be sure to draw two different edges and provide each transition character separately. JFLAP will stack the transition characters on top of each other, as you see in the image above. If you use a comma or otherwise try to input both characters at once for a single edge, JFLAP will think you want all of that text to be the transition, instead of the individual characters. (JFLAP supports multi-character transitions, but you won’t want them for this assignment.)

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: At least two 0s and at most one 1

11 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 containing at least two 0s and at most one 1, and that rejects all other bit strings.

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

00
0000100
00000

Here are three strings that should be rejected:

0
0010010
1

Important

You should try convince yourself through logical reasoning that your FSMs correctly handle all possible inputs. The fact that a given FSM correctly handles all of the test cases that we’ve provided does not necessarily means that it works in general. We will be using additional test cases when grading.

Problem 2: Matching first and last bits

11 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: Looking for multiples

11 points; individual-only

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 number of 0s is either a multiple of two, a multiple of three, or a multiple of both two and three, and that rejects all other bit strings. The number of 1s 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:

111              # zero 0s -- and zero is a multiple of both 2 and 3!
0111011111110    # three 0s
11110100000111   # six 0s

Here are three strings that should be rejected:

1011
0010010
1000100001

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

11 points; individual-only

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

In problem4.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

You should use Apollo to submit the following files:

If you worked on the final project or Problem 1 with a partner, make sure that you each submit a copy of your joint work, and that you include comments at the top of the file specifying the name and email of your partner.

Warnings

  • Make sure to use these exact file names, or Apollo will not accept your files. If Apollo reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Apollo upload page.

  • Before submitting your files, make sure that your BU username is visible at the top of the Apollo page. If you don’t see your username, click the Log out button and login again.

  • If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in IDLE after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.

  • If you submit an unrunnable file, Apollo will accept your file, but it will print a warning message. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.

  • If you encounter problems with Apollo, close your browser and try again. If possible, you may also want to wait an hour or two before retrying. If you are unable to submit and it is close to the deadline, email your homework before the deadline to cs111-staff@cs.bu.edu.

Here are the steps:

  1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
  2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
  3. Find the appropriate problem set section on the main page and click Upload files.
  4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
  5. Click the Upload button at the bottom of the page.
  6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
  7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.

Warning

Apollo will automatically close submissions for a given file when its final deadline has passed. We will not accept any file after Apollo has disabled its upload form, so please check your submission carefully following the instructions in Step 7 above.