Regular expression

From Esolang
Jump to: navigation, search

A regular expression is a string which describes a regular language by describing the structure of every string in that language. Each regular language can be recognized by a particular finite-state automaton.

There are several syntaxes and minor variations used to notate regular expression, but they generally consist of the following substructures:

ab          concatenation: match a followed by b
a|b         alternation: match either a or b
(a|b)a      grouping: subvert precendence rules
a*          Kleene closure: match zero or more occurances of a
ε           epsilon (empty): match the null string

Because a regular expression is a string that describes strings, it is a meta-string. Also because of this, it needs either an extended alphabet from the strings it describes, or some concept of quoting.