The class of decision problems solvable by deterministic finite automata (DFAs).
Equals the class solvable by nondeterministic finite automata (NDFAs).
Equals DSPACE(O(1)) [She59], which equals DSPACE(o(log log n)) [HLS65].
Includes, i.e., "Is the parity of the input odd?," but not "Are the majority of bits in the input 1's?" This is sometimes expressed as "finite automata can't count."
Contained in NC1.
See e.g. [Koz97], [Gur89] for basic results on regular languages.
The class of languages accepted by deterministic pushdown automata.
Defined in [GG66], where it was also shown that DCFL is strictly contained in CFL, contained in UCFL, and strictly contains REG. The inclusion in UCFL is also strict.
Same as REG, except that now the inputs are trees (say, binary trees) instead of strings. Each vertex is labeled with a symbol from a fixed alphabet. Evaluation begins at the leaves and proceeds to the root. The state of the finite automaton at each vertex v is a function of (1) the states at v's children (if any), and (2) the symbol at v. The tree is in the language if and only if the automaton is in an 'accept' state at the root.
See [Koz92] for example.