Regularium

A Treatise on the Art of Pattern Matching

Being a Collection of Exercises in Regular Expressions

The theory of regular expressions finds its origins in the work of mathematician Stephen Cole Kleene, who in 1956 formalized the concept of "regular events" as part of his study of nerve nets and finite automata. What began as pure mathematics would transform into one of computing's most practical tools.

§ A Brief Chronicle

1943
McCulloch & Pitts publish their seminal paper on neural networks, introducing the concept of finite automata that would later inspire regular expressions.
1956
Stephen Kleene introduces "regular expressions" in his paper "Representation of Events in Nerve Nets and Finite Automata", proving their equivalence to finite automata.
1968
Ken Thompson implements regex in the QED text editor, later bringing it to ed and grep on Unix—the first practical application.
1986
Henry Spencer writes a freely available regex library in C, enabling widespread adoption across programming languages.
1987
Larry Wall creates Perl, whose powerful regex engine would become the de facto standard for "extended" regular expressions.
"Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems." — Jamie Zawinski, 1997

In formal language theory, regular expressions describe regular languages—the simplest class in the Chomsky hierarchy. A language is regular if and only if it can be recognized by a deterministic finite automaton (DFA). This equivalence, proved by Kleene, means every regex can be converted to a state machine, and vice versa.

The three fundamental operations are:

  • Concatenation: ab — "a followed by b"
  • Alternation: a|b — "a or b"
  • Kleene star: a* — "zero or more a's"

In this treatise, you shall master the art of pattern matching through a series of progressively challenging propositions. Each exercise teaches a fundamental concept while revealing the elegant theory beneath.

Finis Coronat Opus

The End Crowns the Work

∎

Final Score: 0

You have completed your study of regular expressions, joining a lineage of pattern-seekers stretching back to Kleene's foundational work. From theoretical curiosity to practical necessity, regex has become an indispensable tool for text processing, validation, parsing, and search.

Remember: while regular expressions are powerful, they have limits. As Chomsky showed, not all languages are regular—some patterns require more expressive formalisms. But for the vast realm of regular languages, you now possess the key.

Appendix: Reference of Symbols

.Any character
*Zero or more
+One or more
?Zero or one
^Start of string
$End of string
[abc]Character class
[^abc]Negated class
\dAny digit
\wWord character
\sWhitespace
(a|b)Alternation
{n}Exactly n times
{n,m}Between n and m