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).