a device that can be in any of a finite number of states, like a multi-position switch, and is programmed to change from one of these states to another at regular intervals in response to the inputs it receives
a machine that accepts input and enters states as each new input symbol is read based in the previous state and the input symbol
a machine which transforms any sequence over an alphabet into a sequence over another alphabet
a sequence using a finite number of symbols or letters, generated according to precise rules
a term fa(Symbols,States,Starts,Finals,Transs,Jumps) Symbols is a term r(Sig) (for recognizers) or t(SigD,SigR) for transducers
(FSA, FSM) The simplest computing device. Although it is not nearly powerful enough to perform universal computation, it can recognize regular expressions.
An extremely simple model of computation. In the most basic form, a machine reads an input string once, from left to right. At any step, the machine is in one of a finite number of states. After it reads an input bit, it transitions to a new state, determined by its current state as well as the bit it just read. The machine outputs 'yes' or 'no' based on its state when it reaches the end of the input.
