Finite state automata, a.k.a.
finite state machines, are used to specify programmed behaviour to sequences of events, or input symbols fed to the automaton.
A finite (state) automaton is a finite directed graph, the nodes of which are interpreted as possible states of affairs; the arrows are possible transitions between these states.
Transitions are labeled with events (often called, symbols).
A finite state automaton is deterministic if its transition table is a total function, i.e., if in every state, on every possible input the automaton has exactly one transition defined.
A nondeterministic finite automaton (nfa), on the other hand, can have states in which for some inputs there is more than one transition, or none at all.
The nondeterministic kind doesn't have more expressive power. Proof: consider an nfa's powerset automaton, whose states are defined by all subsets of states in the nfa, and whose transitions are defined by < X, a Y > for all X,Y with an x in X, y in Y such that in the original nfs, a path of 0 or more transitions leads from x to y. This powerset automaton is deterministic and accepts the same strings.
A set has exponentially many subsets, so this can really blow up the size of the automaton. This cannot be avoided: for many classes of nfas, all equivalent dfas are exponentially larger. So nfa are a more much concise notation.
Nfas can be written down as context-free grammars with restricted sets of rules; the so-called regular grammars. In practice, a more popular, and usually more concise, notation for regular languages is the regular expression.
On deterministic automata, the most interesting operation is minimization, which removes the states that are unreachable from the start state. Given a regular language, its minimal dfa is unique up to isomorphism.