A sequence of characters defining a search pattern, grounded in Stephen Kleene's 1951 mathematical formalization of regular languages (his own term was regular events), work motivated by the same McCulloch-Pitts neural-net formalism behind the finite-state machine. Ken Thompson, already a pioneer entity on this atlas, implemented Kleene's notation practically in the QED text editor around 1968 using what became known as Thompson's construction algorithm, later carrying it into the Unix editor ed; the word grep descends directly from ed's own g/re/p command (global search for a regular expression, then print), a verified etymology rather than a repeated folk claim. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Core PrincipleA pattern written in a small algebraic notation (concatenation, alternation, repetition) that denotes a regular language, which Thompson's construction algorithm converts into an equivalent finite-state automaton for actual matching. 1 FAQs
Are the regular expressions programmers use still regular in the mathematical sense?
Backreferences take many modern patterns beyond regular languages, and matching them is NP-complete.
Not always. Many modern tools support patterns with an unbounded number of backreferences, and matching those is still context sensitive, which goes beyond what regular languages can describe. The general problem of matching any number of backreferences is NP-complete, so the execution time of known algorithms grows exponentially with the number of backreference groups used.
Connections
Associated With
Source Wikipedia: Regular expression
Source Wikipedia: Regular expression
In Field
Source Wikipedia: Regular expression
Sources
1. Wikipedia: Regular expression
Wikimedia FoundationHistory
Regular expressions originated in 1951, when mathematician Stephen Cole Kleene described regular languages using his mathematical notation called regular events.
- In Field: Theory of Computation, History section
- Associated With: Finite State Machine, History section
In Group: Mathematical and Formal Notations, Lead
A regular expression (shortened as regex or regexp), sometimes referred to as a rational expression, is a sequence of characters that specifies a match pattern in text.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.