the engine is forbidden from backtracking and so cannot try setting the group to "w" after matching "wi". Possessive quantifiers are easier to implement than greedy and lazy quantifiers, and are typically more efficient at runtime. Patterns for non-regular languages Many features found in virtually all modern regular expression libraries provide an expressive power that exceeds the regular languages. For example, many implementations allow grouping subexpressions with parentheses and recalling the value they match in the same expression (). This means that, among other things, a pattern can match strings of repeated words like "papa" or "WikiWiki", called squares in formal language theory. The pattern for these strings is (.+)\1. The language of squares is not regular, nor is it context-free, due to the pumping lemma. However, pattern matching with an unbounded number of backreferences, as supported by numerous modern tools, is still context sensitive. The general problem of matching any number of backreferences is NP-complete, growing exponentially by the number of backref groups used. However, many tools, libraries, and engines that provide such constructions still use the term regular expression for their patterns. This has led to a nomenclature where the term regular expression has different meanings in formal language theory and pattern matching. For this reason, some people have taken to using the term regex, regexp, or simply pattern to describe the latter. Larry Wall, author of the Perl programming language, writes in an essay about the design of Raku: Assertions Other features not found in describing regular languages include assertions. These include the ubiquitous and , used since at least 1970, as well as some more sophisticated extensions like lookaround that appeared in 1994. Lookarounds define the surrounding of a match and don't spill into the match itself, a feature only relevant for the use case of string searching. Some of them can be simulated in a regular language by treating the surroundings as a part of the language as well. The look-ahead assertions and have been attested since at least 1994, starting with Perl 5. The look-behind assertions and are attested since 1997 in a commit by Ilya Zakharevich to Perl 5.005. Implementations and running times There are at least three different algorithms that decide whether and how a given regex matches a string. The oldest and fastest relies on a result in formal language theory that allows every nondeterministic finite automaton (NFA) to be transformed