• Main page

2.1 Regular Expressions

A regular expression is a formula of a special kind. Regular expressions provide a notation for regular languages. We can declare them in BNF (Backus-Naur form).

We define the class of regular expressions over an alphabet Σ recursively as follows.

1. Any element of Σ standing by itself is a regular expression;
2. If A is a regular expressions, so is A*;
3. If A and B are regular expressions, so is AB;
4. If A and B are regular expressions, so is A|B.

For example, for any character a, a* is a regular expression.

The idea then is that regular expressions built up in this way from characters in an alphabet Σ will somehow point to regular languages ⊆ Σ* . Now we are going to recall the L() notation, where L(ℳ) is the language recognised by ℳ, and overload it to notate a way of getting languages from regular expressions. We do this by recursion using the clauses above.

1. If a is a character from Σ (and thus by clause 1, a regular expression) then L(a) = {a}.
2. L(A|B) = L(A) ∪ L(B).
3. L(AB) = L(A)L(B). This looks a bit cryptic, but actually makes perfect sense. L(A) and L(B) are languages. If K₁ and K₂ are languages, you already know what K₁K₂ from before, so you know what L(A)L(B) is! L(A*) is the set L(A) ∪ L(AA) ∪ L(AAA) . . . = ⋃_{n∊ ℕ} Aⁿ.   Aⁿ is naturally AAAA . . . A (n times).