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:

• states (represented by circles)
• and transitions (represented by arrows).

An automaton is represented through a directed graph where:

• states are node (vertice)
• and transitions are edge

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.

Automata_theory

• Regular expressions are used widely.
• 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.

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

• Undecidable things – no program whatever can do it.
• Intractable things – there are programs, but no fast programs.

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