On this page
When you search a document for a pattern rather than a fixed word, the tool is probably using a regular expression. That idea goes back to an American logician, Stephen Cole Kleene, and a report he wrote for the RAND Corporation in 1951.
Who invented regular expressions?
Stephen Kleene was born on 5 January 1909 in Hartford, Connecticut, and earned his PhD at Princeton in 1934 under Alonzo Church, according to the MacTutor biography from the University of St Andrews. You can read about his teacher in how Alonzo Church defined computation with the lambda calculus. Kleene spent most of his career at the University of Wisconsin–Madison, and MacTutor records that he spent the summer of 1951 at RAND and discovered an important characterisation of finite automata.
That work became RAND research memorandum RM-704, “Representation of Events in Nerve Nets and Finite Automata”, dated 15 December 1951 (RAND catalogue record; scanned copy of the memo). Its summary opens with a question: “To what kinds of events can a McCulloch-Pitts nerve net respond by firing a certain neuron?” Those nerve nets, simple models of neurons, came from Warren McCulloch and Walter Pitts’s 1943 paper in the Bulletin of Mathematical Biophysics.
What did Kleene’s 1951 memo actually define?
In section 7 of the memo, Kleene names a class of events “regular events”, and adds: “We would welcome any suggestions as to a more descriptive term.” Nobody found a better one: the word “regular” stuck, and standards today call these patterns regular expressions.
He built every regular event from simple pieces with three operations:
Or (written `E∨F`): the event happens if E happens or F happens.
One after another (`EF`): E has just happened, immediately after F.
Star (`E*F`): “zero or more consecutive occurrences of E” preceded by one occurrence of F.
The star is what we now call the Kleene star. Kleene explained why he did not write `E*` on its own: with zero repeats, the event would last no time at all, and, at least for convenience, he required every event to last at least one moment. Modern tools dropped that rule, so a starred item may match nothing.
His objective, in his words, was “to show that all and only regular events can be represented by nerve nets or finite automata”. In plain terms: any pattern built from or, one-after-another and star can be recognised by a machine with a fixed, finite memory, and nothing else can.
How did a logic paper end up in your search tools?
In June 1968, Ken Thompson of Bell Labs published “Regular expression search algorithm” in Communications of the ACM. It describes a compiler that takes a regular expression and produces an IBM 7094 program that signals each time a matching piece of text appears (Crossref record and abstract). Thompson later co-created Unix; read how Ken Thompson built Unix.
Today the POSIX standard, the shared rulebook for Unix-style tools such as grep, still defines Kleene’s star: an expression followed by an asterisk matches what “zero or more consecutive occurrences” of it would match (POSIX regular expressions, section 9.3.6). His “or” survives as the vertical bar: two expressions separated by `|` match a string “that is matched by either” (section 9.4.7 of the same standard).
How do you read a regular expression?
Take the pattern `gr(a|e)y!*` and read it with Kleene’s three operations:
Or: `(a|e)` means a single a or a single e.
One after another: g, then r, then the choice, then y, in that order.
Star: `!*` means zero or more exclamation marks. The star applies only to the item just before it.
So it matches gray, grey and grey!!!, but not groy (o is not an option) or gry (the choice needs one letter).
To write your own, use this five-step check:
Write three strings that should match and three that should not.
Type the parts that never change exactly as they are.
Join the options at each choice point with `|`.
Put a star after anything that may repeat or be missing.
Test against your “should not match” list. A pattern that catches everything you wanted can also catch far more than you meant.
Why does Kleene still matter to students?
Kleene asked a pure question: what can a simple model of neurons recognise? The answer became a tool people use every day without knowing it. In 1990 he received the US National Medal of Science “for his leadership in the theory of recursion and effective computability”, MacTutor notes (St Andrews).
If sets, logic or finite automata feel shaky, the Fermi Concept Library covers concepts in mathematics and computing, each with its own lesson and its place in the map. Then open a text editor, switch its search to regular-expression mode, type `ca*t`, and watch Kleene’s star find ct, cat and caaat.
