Automaton (State Machine)


Automata theory is the study of abstract computing devices or machines.

The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means self-acting

An automaton consists of:

An automaton is represented through a directed graph where:

As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the current state and the recent symbol as its inputs.

An automaton is a finite representation of a formal language (and therefore computer language) that may be an infinite set.

Automata are often classified by the class of formal languages they can recognize, typically illustrated by the Chomsky hierarchy, which describes the relations between various languages and kinds of formalized logic.


A state machine leaves almost no room for interpretation.



Class of problems

When developing solutions to real problems, we often confront the limitations of what software can do.


  • See Dropbox\automata
  • Book - Hopcroft, Motwani, Ullman, Automata Theory, Languages, and Computation 3rd Edition. pdf - to continue - chapter 2

Powered by ComboStrap