Deterministic Finite Automata
We begin our journey into the theory of computation with one of the most elementary models of computation we can consider: the finite automata. As you read from Sipser, make sure to engage with the reading:
- Gain intuition about the model by considering real world examples that can be modeled with finite automata.
- Explore the model by coming up with small, artificial examples using the model’s formal definition.
Through section 1.1 (Finite Automata)
As part of your study of the theory of computation, you should actively engaging with the reading by periodically working on the problems at the end of each chapter on your own. While not required, try work on these quick recommended exercises on your own as a check that you understand the material. I will try to select exercises that best reflect the kinds of activities I expect you to do in preparation for the day’s lab.
As a final note, don’t just look at the answers for the exercise (when they are available). Just like real exercise, the point isn’t to finish exercising; it is, instead, the work, sweat, etc., that you put into exercise where you find the benefit!
- Exercise 1.2 (formal machine descriptions)