# Automaton (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.

## 3 - Usage

• Finite automata model protocols, electronic circuits.
• Context-free grammars are used to describe the syntax of essentially every programming language and are used widely in natural languages.

## 4 - Class of problems

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

## 5 - Documentation

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