HW 0: Deterministic Finite Automata (DFAs)
due Tuesday, September 6 at 11:59pm
In this assignment, we start to explore what it means to compute. We will look at our first model of computation: Deterministic Finite Automata (DFAs). As you work on the assignment, keep this question in the back of your mind: Are DFAs equivalent to what we typically think of as a computer?
Note: Parts of this assignment cover material from Thursday’s class. They are marked below.
You will use Gradescope to turn in your assignment. Before you get started, make sure that you can access our course page on Gradescope:
https://www.gradescope.com/courses/420670
You should be able to log in with your @hmc email address.
If you log in and do not see “CS 42” under this semester’s courses, please post on Piazza to let us know.
Picobot is a programmable simulator for a robot that is meant to explore all the space in a room (sort of like a Roomba). We can give Picobot a program that describes the bot’s movements, then run the program to confirm that Picobot visits all the space in a given room.
For this part of the assignment, you will learn about Picobot and write a program that can explore an empty room.
Read the description of Picobot, including its environment, state, and rules for controlling its movement.
Using the Picobot simulator, write a program that always visits every spot in the “empty room”, regardless of where the Picobot starts. The “empty room” is the room that loads by default when you visit the Picobot simulator.
Note: The Gradescope assignment has an “autograder”, which will automatically run your Picobot program. Pay attention to the output! If it says there is an error, it is likely a syntax error.
On Gradescope, answer the questions in the HW 0: Reading assignment.
Note: This part of the assignment will be available after Thursday’s class, along with this week’s warmups. Before working on this part of the assignment, you should look over the warmups and consider completing some, as a “bridge” to the assignment.
On Gradescope, answer the questions in the HW 0: Picobot and DFAs assignment.
If you are interested in these topics, here are a few ways to explore it deeper. These items aren’t part of the assignment and aren’t meant to interfere with your other work. They’re just here for fun, and you can refer back to them later, whenever you have some free time and want to think more about the themes of the assignment.
Strategies. Alone or with some friends, come up with some tips for future CS 42 students working on this assignment. What strategies did you find helpful, when writing a Picobot program or turning the description of a language into a drawing of a DFA? How might you tutor someone who was working on the assignment?
Picobot. Write a Picobot program that can cover some of the other maps in the Picobot simulator. For each map in the simulator, is it possible to write a Picobot program that will cover every square of the map, regardless of where the robot starts? Is it possible to write a single Picobot program that will cover any map, starting from an arbitrary location? If you are interested in the theory behind these questions, this paper is a good (though challenging) read.
Resources. If you’re interested in DFAs and the kinds of problems they can(’t) solve, here are a couple of books that go more in depth. These books also talk about other concepts related to DFAs, all from the subdiscipline of Computer Science and Math called Theory of Computation.