Regular expressions describe languages with an algebra built from three operations. Kleene's theorem says they capture precisely the regular languages.
Definition · Regular expression
R is a regular expression if R is:
- a symbol a ∈ Σ, or the empty string ε, or the empty language ∅
- a union R₁ ∪ R₂
- a concatenation R₁ ∘ R₂
- a star R₁* (zero or more repetitions)
Every regular expression can be converted to an NFA, and every DFA can be converted back to a regular expression (via the GNFA state-elimination method). Three formalisms, one class of languages.