Lab 11: Finite-state machines

Task 0: complete lab evaluations
Task 1: understand FSMs
Task 2: practice using JFLAP
Task 3: design your own FSM
Task 4: submit your work

Task 0: complete lab evaluations

We will begin by taking a few minutes to complete evaluations for the lab component of the course.

These evaluations are only for the teaching fellows. There is a separate evaluation of the undergraduate course assistants that you will complete as part of Problem Set 10, so please don’t comment about the CAs on today’s form.
Your evaluations are anonymous, and we will not receive the results until after all final grades have been submitted.
Comments in the text fields are valued and encouraged. Please try to answer all questions, but if a question is not applicable or you do not wish to answer it, you can simply skip it.

Here is the URL that you should use:

bu.campuslabs.com/courseeval

Enter your BU login name and Kerberos password, and complete the evaluation for your CS 111 lab section (the one with the section number that the teaching fellow will write on the board). Please do not evaluate your lecture section at this time.
When you are done with the survey, please close the separate browser tab.

Thanks in advance for taking the time to provide your feedback about the labs!

Task 1: understand FSMs

Consider the following finite-state machine:

Which state is the start state?
Which state(s) are accepting states?
How many transitions does each state have? Is this required?
Which states(s) are “black hole” states – i.e., states that, once you enter them, you can never leave? Will you always need that type of state in your FSM? When is it useful?
Which of the following inputs are accepted by this FSM, and which are rejected?
- 0
- 10
- 111
- 010
- 101010
- 0100
How would you describe the inputs that are accepted by this FSM?
Would it be possible to simplify this FSM by reducing the number of states? If so, how? If not, why not?

Task 2: practice using JFLAP

On Problem Set 10, you will use tool called JFLAP to build and test several finite state machines.

You should go ahead and download the JFLAP application now.

Then, let’s work together to create the following simple FSM in JFLAP:

Once the FSM is constructed, save it in a file named lab11task2.jff.

Finally, let’s use JFLAP to test our FSM on some sample input strings:

0
10
111
00000

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.

Important

In the tutorial, not every state is given both a transition for 0 and a transition for 1.

In the FSMs that you construct for this problem set, each state must have a single transition for 0 and a single transition for 1.

Task 3: design your own FSM

Run JFLAP, and click on the button for Finite Automaton. Build a deterministic finite-state machine that accepts all bit strings containing the pattern 010, and that rejects all other bit strings. Save your work in a file named lab11task3.jff.

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 three examples of strings that should be accepted:

010
1101001110001
001011

Here are three strings that should be rejected:

01
110110
0001111

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 the FSMs that you submit as part of Problem Set 10.

Task 4: submit your work

You should use Apollo to submit:

your lab11task2.jff file
your lab11task3.jff file

Don’t worry if you didn’t finish all of the tasks. You should just submit whatever work you were able to complete during lab.

Here are the steps:

Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
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.
Find the appropriate lab section on the main page and click “Upload files.”
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.
Click the “Upload” button at the bottom of the page.
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.
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.