Regular expressions define formal languages as sets of strings over a finite alphabet. Let σ denote a selected alphabet. Then ∅ is a regular expression that denotes the empty set and ϵ is a regular expression that denotes the set containing the empty string as its only element. If c element σ, then c is a regular expression that denotes the set whose only element is string c. If p and q are regular expressions denoting sets L(p) and L(q), then 1.(p)|(q) is a regular expression denoting the set L(p) union L(q), where union denotes the union.

formal language | grammar