Formal Languages and Automata
An automaton is an abstract model of a digital computer. As such, every automaton includes some essential features. It has a mechanism for reading input. It will be assumed that the input is a string over a given alphabet, written on an input file, which the automaton can read but not change. The input file is divided into cells, each of which can hold one symbol. The input mechanism can read the input file from left to right, one symbol at a time. The input mechanism can also detect the end of the input string (by sensing an end-of-file condition). The automaton can produce output of some form. It may have a temporary storage device, consisting of an unlimited number of cells, each capable of holding a single symbol from an alphabet (not necessarily the same one as the input alphabet). The automaton can read and change the contents of the storage cells. Finally, the automaton has a control unit, which can be in any one of a finite number of internal states, and which can change state in some defined manner.
Deterministic and Nondeterministic Automata
[...] A deterministic automaton is one in which each move is uniquely determined by the current configuration. If we know the internal state, the input, and the contents of the temporary storage, we can predict the future behavior of the automaton exactly. In a nondeterministic automaton, this is not so. At each point, a nondeterministic automaton may have several possible moves, so we can only predict a set of possible actions. [...]
State Machines
State machines have their roots in mathematics and, therefore, like many things in math, sound really clever but are actually pretty simple when it comes down to it. You will also find state machines and drawings of state machines being called finite state machines (FSMs) and state transition diagrams (STDs).
The basic concept is that a system stays in a stable state until some trigger causes it to transition to another state. This transition might cause some actions to occur during the transition. States are drawn on a diagram as boxes or bubbles and transitions as lines with arrows that go either from one box to another or from one box back to itself. The transition lines are drawn with a two-part label on them. The top part of the label is the condition for the transition to occur (say, a button being pressed), and then there is a horizontal line, and under the line appear any actions that need to take place during the transition (say, turn a LED on).
There are, of course, other ways of drawing state machines, but this is probably the most common.