# 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-