Finite automata
A finite automaton (plural: automata) is a model of computation. Finite automata and their probabilistic counterpart Markov chains are useful tools when attempting to recognize patterns in data. Their formal definition has a 1-1 correspondence with a type of state diagram.
A finite automaton is a 5-tuple (
is a finite set called the states, is a finite set called the alphabet, is the transition function, is the start sate, and is the set of accept states.
Processing of input
When an automaton receives an input string, it can either accept or reject it. A string is accepted if the automaton is in an accept state once the full input string is processed. Formally this is described as:
String acceptance
Let
, and-
If
State machine representation
A finite automaton has a 1-1 correspondence with a graphical state machine representation.