Next: The meaning of regular
Up: Regular expressions
Previous: Regular expressions
What are regular expressions?
We assume as given an alphabet
(e.g.
) and define the
syntax of regular
expressions (over
)
is a regular expression.
is a regular expression.
- For each
,
is a regular expression.
E.g. in the example all small letters are regular expression. We use
boldface to emphasize the difference between the symbol a and the
regular expression a.
- If
and
are regular expressions then
is a regular
expression.
- If
and
are regular expressions then
(i.e. just one
after the other) is a regular expression.
- If
is a regular expression then
is a regular
expression.
- If
is a regular expression then
is a regular
expression.
These are all regular expressions.
Here are some examples for regular expressions:
As in arithmetic they are some conventions how to read regular
expressions:
binds stronger then sequence and
. E.g. we read
as
. We have to
use parentheses to enforce the other reading
.
- Sequencing binds stronger than
. E.g. we read
as
. To
enforce another reading we have to use parentheses as in
.
Next: The meaning of regular
Up: Regular expressions
Previous: Regular expressions
Thorsten Altenkirch
2001-05-08