Finite Automaton
A finite automaton is an abstract machine with finitely many internal states which reads an input string one symbol at a time. In its deterministic form, a finite automaton consists of a finite set of states, a finite input alphabet, a transition function, an initial state, and a set of accepting states. It accepts a string if the computation determined by the transition function ends in an accepting state.
Nondeterministic finite automata allow more than one possible next state, but recognize the same class of languages as deterministic finite automata, namely the regular languages (Hopcroft and Ullman 1979).
Wolfram (2002, p. 957) describes finite automata in terms of networks whose nodes are states and whose labeled arcs are transitions.
See also
Automata Theory, Automatic Set, Turing MachineExplore with Wolfram|Alpha
References
Allouche, J.-P. and Shallit, J. Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, 2003.Hopcroft, J. E. and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison Wesley, 1979.Wolfram, S. "Notes: Finite Automata." A New Kind of Science. Champaign, IL: Wolfram Media, p. 957, 2002.Cite this as:
Weisstein, Eric W. "Finite Automaton." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FiniteAutomaton.html