We now know what regular expressions are but what do they mean?
For this purpose, we shall first define an operation on languages
called the Kleene star. Given a language
we define
As an example consider
:
You should notice that we use the same symbol as in
but there is a subtle difference:
is a set of
symbols but
is a set of words.
Alternatively (and more abstractly) one may describe as the
least language (wrt
) which contains
and the empty word
and is closed under concatenation:
We now define the semantics of regular expressions: To each regular
expression over
we assign a language
.
We do this by induction over the definition of the
syntax:
Let us now calculate what the examples of regular expressions from the previous section mean, i.e. what are the langauges they define:
Let's just look at
. We know from 3:
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
From the previous point we know that:
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
||
![]() |
Let us introduce the following notation:
Now using 6 we know that
![]() |
![]() |
|
![]() |
||
![]() |
![]() |
![]() |
|
![]() |
||
![]() |
Let's analyze the parts:
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
Hence, we have