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:
Subtle points: in 1. the symbol may be used as a regular expression (as in ) or the empty set ( ). Similarily, in 2. may be a regular expression or a word, in 6. may be used to construct regular expressions or it is an operation on languages. Which alternative we mean becomes only clear from the context, there is no generally agreed mathematical notation 1to make this difference explicit.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