regular expression

views updated

regular expression An expression built from finite formal languages (i.e. finite sets of strings) using the operations of union, concatenation, and Kleene star. For example, the following two regular expressions each denote the set of all strings of alternating as and bs: {a,Λ} {ba}* {Λ,b} {ba}* ∪ {a}{ba}* ∪ {ba}*{b} ∪ {a}{ba}*{b}

where Λ is the empty string. A language is regular if and only if it is representable by a regular expression. Thus the class of regular languages is the smallest one that contains all finite languages and is closed under concatenation, union, and star – the so-called regular operations. These three operations correspond to “sequence”, “choice”, and “iteration” in structured iterative programs.