Regular
expressions in
computer science describe
regular languages.
Regular expressions and languages can be defined
inductively:
Σ is our
alphabet, a ∈ Σ
∅ is a regular expression over Σ and describes the regular language ∅
ε is a regular expression over Σ and describes the regular language {ε} (ε is the
empty word, but ∅ is the
empty set)
a is a regular expression over Σ and describes the regular language {a}
If r1 is a regular expression ,then (r1)* is a regular expression, too ( the
* is the
Kleene star), It describes the regular language R1*
If r1 and r2 are regular languages, then (r1 | r2) (
alternative or
OR) and (r1r2) (
concatenation) are regular expressions, too. They describe thre regular languages R1 U R2 and R1R2.
Nothing else is a regular expression (Important! If you can not lead an expression back to this, it is none).
Example: Σ = {a,b,c}
Regular expressions are for example a,b,c, aa, ba*,...
The corresponding languages are {a} (for a) or {b}{a}* (for ba*, as the Kleene star binds strongest).