finite automata
(60 minutes to learn)
Summary
Finite automata are a formal model of computation with finite memory. The machine can be in any of a finite number of states, and it has rules for transitioning between states depending on its input. Finite automata can only perform fairly limited computations, such as matching regular expressions.
Context
-this concept has no prerequisites-
Goals
- formally define finite automata
- be able to interpret state diagrams
- be able to design finite automata to solve simple tasks
Core resources (read/watch one of the following)
-Free-
→ Coursera: Automata
An introductory course on automata and the theory of computation.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 1.1, "Finite Automata," pages 31-47
Additional dependencies:
Other notes:
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Chapter 2, "Finite Automata," up to 2.2, "Deterministic finite automata," pages 37-55
Additional dependencies:
See also
-No Additional Notes-