1. Ø,λ and a ∈ Σ are all regular expressions. These are called primitive regular
expressions.
2 If r 1 and r 2 are regular expressions, so are r 1 + r 2 ,r 1 .r 2 , , and (r 1 ).
3. A string is a regular expression if and only if it can be derived from the
primitive regular expressions by a finite number of applications of the rules
in (2).
Example 3.1
For Σ = {a, b, c}, the string
(a+b+c)* .(c+Ø)
is a regular expression, since it is constructed by application of the above rules.
For example, if we take r1 = c and r2 = Ø, we find that c + Øand (c + Ø) are also
regular expressions. Repeating this, we eventually generate the whole string. On
the other hand, (a + b +) is not a regular expression, since there is no way it can
be constructed from the primitive regular expressions.
Languages Associated with Regular Expressions
Regular expressions can be used to describe some simple languages. If r is a
regular expression, we will let L(r) denote the language associated with r.
Definition 3.2
The language L(r) denoted by any regular expression r is defined by the
following rules.
1. Ø is a regular expression denoting the empty set,
2. λ is a regular expression denoting {λ}.
3. For every a ∈ Σ, a is a regular expression denoting {a}.
If r 1 and r 2 are regular expressions, then