Infinite Script

In computing, a regular expression is a specific pattern that provides concise and flexible means to “match” (specify and recognize) strings of text, such as particular characters, words, or patterns of characters. Common abbreviations for “regular expression” include regex and regexp.

Basic Concepts

A regular expression, often called a pattern, is an expression that specifies a set of strings. To specify such sets of strings, rules are often more concise than lists of a set’s members. For example, the set containing the three strings “Handel”, “Händel”, and “Haendel” can be specified by the pattern H(ä|ae?)ndel (or alternatively, it is said that the pattern matches each of the three strings). In most formalisms, if there exists at least one regex that matches a particular set then there exist an infinite number of such expressions. Most formalisms provide the following operations to construct regular expressions.

Boolean “or”:

A vertical bar separates alternatives. For example, gray|grey can match “gray” or “grey”.

Quantification

A quantifier after a token (such as a character) or group specifies how often that preceding element is allowed to occur. The most common quantifiers are the question mark ?, the asterisk * (derived from the Kleene star), and the plus sign + (Kleene cross).

• ? The question mark indicates there is zero or one of the preceding element. For example, colou?r matches both “color” and “colour”.
• * The asterisk indicates there is zero or more of the preceding element. For example, ab*c matches “ac”, “abc”, “abbc”, “abbbc”, and so on.
• + The plus sign indicates there is one or more of the preceding element. For example, ab+c matches “abc”, “abbc”, “abbbc”, and so on, but not “ac”.

Grouping

Parentheses are used to define the scope and precedence of the operators (among other uses). For example, gray|grey and gr(a|e)y are equivalent patterns which both describe the set of “gray” or “grey”.

Formal language theory

Regular expressions describe regular languages in formal language theory. They have the same expressive power as regular grammars.

Formal Definition

Regular expressions consist of constants and operator symbols that denote sets of strings and operations over these sets, respectively. The following definition is standard, and found as such in most textbooks on formal language theory. Given a finite alphabet Σ, the following constants are defined as regular expressions:

• (empty set) ∅ denoting the set ∅.
• (empty string) ε denoting the set containing only the “empty” string, which has no characters at all.
• (literal character) a in Σ denoting the set containing only the character a.

Given regular expressions R and S, the following operations over them are defined to produce regular expressions:

• (concatenation) RS denoting the set { αβ | α in set described by expression R and β in set described by S }. For example {“ab”, “c”}{“d”, “ef”} = {“abd”, “abef”, “cd”, “cef”}.
• (alternation) R | S denoting the set union of sets described by R and S. For example, if R describes {“ab”, “c”} and S describes {“ab”, “d”, “ef”}, expression R | _S_describes {“ab”, “c”, “d”, “ef”}.
• (Kleene star) R* denoting the smallest superset of set described by R that contains ε and is closed under string concatenation. This is the set of all strings that can be made by concatenating any finite number (including zero) of strings from set described by R. For example, {“0”,“1”}* is the set of all finite binary strings(including the empty string), and {“ab”, “c”}* = {ε, “ab”, “c”, “abab”, “abc”, “cab”, “cc”, “ababab”, “abcab”, … }.

To avoid parentheses it is assumed that the Kleene star has the highest priority, then concatenation and then alternation. If there is no ambiguity then parentheses may be omitted. For example, (ab)c can be written as abc, and a|(b(c*)) can be written as a|bc*. Many textbooks use the symbols ∪, +, or ∨ for alternation instead of the vertical bar.

Examples:

• a|b* denotes {ε, “a”, “b”, “bb”, “bbb”, …}
• (a|b)* denotes the set of all strings with no symbols other than “a” and “b”, including the empty string: {ε, “a”, “b”, “aa”, “ab”, “ba”, “bb”, “aaa”, …}
• ab*(c|ε) denotes the set of strings starting with “a”, then zero or more “b"s and finally optionally a “c”: {“a”, “ac”, “ab”, “abc”, “abb”, “abbc”, …}

Expressive power and compactness

The formal definition of regular expressions is purposely parsimonious and avoids defining the redundant quantifiers ? and +, which can be expressed as follows: a+ = aa*, and a? = (a|ε). Sometimes the complement operator is added, to give a generalized regular expression; here R^c matches all strings over Σ* that do not match R. In principle, the complement operator is redundant, as it can always be circumscribed by using the other operators. However, the process for computing such a representation is complex, and the result may require expressions of a size that is double exponentially larger.

Regular expressions in this sense can express the regular languages, exactly the class of languages accepted by deterministic finite automata. There is, however, a significant difference in compactness. Some classes of regular languages can only be described by deterministic finite automata whose size grows exponentially in the size of the shortest equivalent regular expressions. The standard example here is the languages L_k consisting of all strings over the alphabet {a,b} whose k^th-from-last letter equals a. On one hand, a regular expression describing L₄ is given by (a | b)_^*_a( a | b )( a | b )( a | b ).

On the other hand, it is known that every deterministic finite automaton accepting the language L_k must have at least 2^k states. Luckily, there is a simple mapping from regular expressions to the more general nondeterministic finite automata (NFAs) that does not lead to such a blowup in size; for this reason NFAs are often used as alternative representations of regular languages. NFAs are a simple variation of the type-3 grammars of the Chomsky hierarchy.

Finally, it is worth noting that many real-world “regular expression” engines implement features that cannot be described by the regular expressions in the sense of formal language theory; see below for more on this.

Deciding equivalence of regular expressions

As seen in many of the examples above, there is more than one way to construct a regular expression to achieve the same results.

It is possible to write an algorithm which for two given regular expressions decides whether the described languages are essentially equal, reduces each expression to a minimal deterministic finite state machine, and determines whether they are isomorphic (equivalent).

The redundancy can be eliminated by using Kleene star and set union to find an interesting subset of regular expressions that is still fully expressive, but perhaps their use can be restricted. This is a surprisingly difficult problem. As simple as the regular expressions are, there is no method to systematically rewrite them to some normal form. The lack of axiom in the past led to the star height problem. In 1991, Dexter Kozen axiomatized regular expressions with Kleene algebra.

Regular expressions come in various styles. The table below provides a comprehensive list of metacharacters in PCRE and their behaviors in the context of regular expressions: