Finite state automata (FSA) are devices that can be in one of a finite number of states, one of which is called the start state and one or more are called final states. Transitions are defined for each state when the FSA reads a symbol from an input language. If a word, or input string of symbols from the input language, is provided to the FSA and if it starts at a start state and arrives at a final state after reading the word, we say the word is accepted by the FSA. Languages of words accepted by FSA are called regular languages.

Transducers are automata that have transitions labeled with two symbols. One of the symbols represents input, the other output. Transducers translate (or transduce) strings. In automata theory they are called Mealy machines. Finite state transducers recognize tuples of strings. A set of tuples of strings that can be recognized by an FST is called a regular relation. So, regular relations are to FSTs what regular languages are to FSA.

Linear bounded automata (LBA) are multi-track Turing machines which have only one tape, and this tape is exactly the same length as the input. The family of languages accepted by LBA is the family of context sensitive languages.

A Moore machine produces an output for each state. An FSA is thus a Moore machine with two outputs, success and failure, corresponding to final and nonfinal states respectively. A Mealy machine produces an output for each transition (state/input pair). A Moore machine can be transformed into an equivalent Mealy machine by associating the output of each state with every transition that leads to that state. The languages accepted are the same (although the Mealy machine doesn't recognize the empty word).

Pushdown automaton (PDA) are finite state automata that can make use of a stack containing data. The state transitions for PDA involve the input symbol as well as the information available on the stack. The set of languages accepted by nondeterministic PDA is equivalent to the set of context free languages.

A Turing machine is an imaginary computing machine invented by Alan Turing to describe what it means to compute something. The “physical description” of a Turing machine is a box with a tape and a tape head. The tape consists of an infinite number of cells stretching in both directions, with the tape head always located over exactly one of these cells. Each cell has one of a finite number of symbols written on it. The machine has a finite set of states, and with every move the machine can change states, change the symbol written on the current cell, and move one space left or right. The machine has a program which specifies each move based on the current state and the symbol under the current cell. The machine stops when it reaches a combination of state and symbol for which no move is defined. A countable set S (or language) is called recursively enumerable if there exists a Turing machine that always halts when given an element of S as input, and that never halts when given an input that does not belong to S.