This course is about the processing of strings. Lets start with what we mean by \emph{strings}. Strings

(they are also sometimes referred to as \emph{words}) are lists of characters drawn from an \emph{alphabet}. 

If nothing else is specified, we usually assume 

the alphabet consists of just the lower-case letters $a$, $b$, \ldots, $z$. Sometimes, however, we explicitly

restrict strings to contain, for example, only the letters $a$ and $b$. In this case we say the alphabet is the set $\{a, b\}$.

There are many ways how we can write down strings. In programming languages, they are usually 

written as {\it "hello"} where the double quotes indicate that we dealing with a string. 

Essentially, strings are lists of characters which can be written for example as follows

The important point is that we can always decompose strings. For example, we will often consider the

first character of a string, say $h$, and the ``rest''  of a string say {\it "ello"} when making definitions 

about strings. There are some subtleties with the empty string, sometimes written as {\it ""} but also as 

the empty list of characters $[\,]$. Two strings, for example $s_1$ and $s_2$, can be \emph{concatenated}, 

which we write as $s_1 @ s_2$. Suppose we are given two strings {\it "foo"} and {\it "bar"}, then their concatenation

We often need to talk about sets of strings. For example the set of all strings over the alphabet $\{a, \ldots\, z\}$

is

Any set of strings, not just the set-of-all-strings, is often called a \emph{language}. The idea behind

this choice of terminology is that if we enumerate, say, all words/strings from a dictionary, like 

different set of strings, and so on. In the context of this course, a language might 

not necessarily make sense from a natural language point of view. For example

the set of all strings shown above is a language, as is the empty set (of strings). The

difference between the empty set, or empty language, and the set that 

contains only the empty string $\{\text{""}\}$: the former has no elements, whereas 

the latter has one element.

As seen, there are languages which contain infinitely many strings, like the set of all strings.

The ``natural'' languages like English, French and so on contain many but only finitely many 

strings (namely the ones listed in a good dictionary). It might be therefore be surprising that the

language consisting of all email addresses is infinite provided we assume it is defined by the

The reason is that for example before the $@$-sign there can be any string you want assuming it 

is made up from letters, digits, underscores, dots and hyphens---clearly there are infinitely many

of those. Similarly the string after the $@$-sign can be any string. However, this does not mean 

is not, because the top-level-domains must be of length of at least two. (Note that there is

lower-case.)

sets. We will use capital letters $A$, $B$, $\ldots$ to stand for sets of strings. 

operation of \emph{concatenating} two sets of strings. This can be defined as

string in the set $B$, then take the second string from $A$ do the same and so on. You might

like to think about what this definition means in case $A$ or $B$ is the empty set.

We also need to define

the power of a set, written as $A^n$ with $n$ being a natural number. This is defined inductively as follows

of every power of $A^n$ with $n\ge 0$. The mathematical notation for this operation is

This definition implies that the star of a set $A$ contains always the empty string (that is $A^0$), one 

copy of every string in $A$ (that is $A^1$), two copies in $A$ (that is $A^2$) and so on. In case $A=\{"a"\}$ we therefore 

have 

Be aware that these operations sometimes have quite non-intuitive properties, for example

$A^\star$ & $=$ & $\{""\} \cup A\cdot A^*$\\

\emph{Regular expressions} are meant to conveniently describe languages...at least languages

for describing the English language short of enumerating all English words. 

        & $\mid$ & $c$                         & single character\\

Because we overload our notation there are some subtleties you should be aware of. The letter $c$ stands for any character from the

alphabet at hand. Second, we will use parentheses to disambiguate

regular expressions. For example we will write $(r_1 + r_2)^*$, which is different from, say $r_1 + (r_2)^*$.

$r_2$. We should also write $(r_1 + r_2) + r_3$, which is different from the regular expression $r_1 + (r_2 + r_3)$,

but in case of $+$ and $\cdot$ we actually do not care about the order and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2 \cdot r_3$,

$r_1 + r_2$  is written as $r_1\mid{}r_2$. Also following the convention in the literature, we will in case of $\cdot$ even 

often omit it all together. For example the regular expression for email addresses shown above is meant to be of the form

Another source of confusion might arise from the fact that we use the term \emph{regular expressions} for the ones used in ``theory''

and also the ones in ``practice''. In this course we refer by default to the regular expressions defined by the grammar above. 

In ``practice'' we often use $r^+$ to stand for one or more times, $\backslash{}d$ to stand for a digit, $r^?$ to stand for an optional regular

expression, or ranges such as $[\text{\it a - z}]$ to stand for any lower case letter from $a$ to $z$. They are however mere convenience 

expression is supposed to stand for every string \emph{not} matched by a regular expression. We will write

such not-regular-expressions as $\sim{}r$. While being ``convenience'' it is often not so clear what the shorthand for

these kind of not-regular-expressions is. Try to write down the regular expression which can match any

string except {\it "hello"} and {\it "world"}. It is possible in principle, but often it is easier to just include

$\sim{}r$ in the definition or regular expressions. Whenever we do so, we will state it explicitly.

Formally, we associate with every regular expression a set of strings which are matched by this