A regular expression is a way of writing down the rules for recognizing a string of bytes or characters as belonging (or not belonging) to a certain "language." In this context, a "language" can be anything from "the set of all digit-sequences" to "the set of all sequences of valid C++ tokens." Essentially, a "language" is just a rule for dividing the world of all strings into two sets--the set of strings matching the rules of the language, and the set of strings that don't match.

Some kinds of languages follow simple enough rules that they can be recognized by a finite state machine, a computer program with no memory at all--just a program counter and a pointer that scans over the input in a single pass. The language of "digit-sequences" is certainly in the category of languages that...