Problem Set 10 FAQ

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

Task 1

1. What parts of the final project should we submit as part of Problem Set 10?

   You should submit Parts I and II from the final project.

See the Final Project FAQ for questions related to the project.

General Questions on the FSM Problems

1. I’m having trouble getting JFlap to work on my computer. What should I do?

   You may need to take one or more of the following steps:

   1. Install the Java runtime environment. We gave you instructions for this in Lab 0 at the start of the semester.

   2. If you are using a Mac and you are unable to download JFlap_thin.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 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_thin.jar
         

   5. 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.

   If you are still having problems running the program after taking these steps, you should come to office hours for help. You can also work with JFlap on one of the machines in the undergraduate lab (EMA 302).

2. My FSM looks correct, but it doesn’t accept the right output. What should I do?

   Be sure that none of your transition labels have spaces in them. If this doesn’t fix the issue, try stepping through the FSM for a specific input string and see where its behavior deviates from what you expect.

Problem 4

1. I’m stuck on problem 4. Any suggestions?

   It’s important not to over-complicate this problem. A few people have asked if we can solve this one with less than eight states, and we mentioned in lecture that doing so is impossible. Therefore, we recommend that you start with the eight states described in the lecture notes.

   If we only care about the third-to-last bit, we can assume that we always start with a string of three zeroes (the state labeled s000 in the notes). Then we just need to draw in the transitions, remembering that every state should have a transition for 0 and a transition for 1.

   Suppose we are at s000. This means the last three digits in the string are all zeroes. We need to draw a transition from this state for 0 and for 1. Answering the following questions will help you figure out which states to transition to:

   • If my string ends with 000 and I add a 0 to the end, which state should I go to?

   • If my string ends with 000 and I add a 1 to the end, which state should I go to?

   Repeating this process for all eight states will give you a complete FSM that accepts strings where the third to last bit is 1. Just remember that each state represents the last three letters of your string.