Métodos computacionales

Automata

The term “automaton” is derived from the Greek word “αὐτόματον” which means “self-acting”. An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.

Finite Automaton

An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).

Formally, a finite automaton can be represented by a 5-tuple \((Q, \Sigma, \delta, q_0, F)\), where:

Finite automaton can be classified into two types:

Additional Terminology

Deterministic Finite Automaton (DFA)

In a DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Automaton.

A DFA is represented by a directed graph called state diagram.