\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[T1]{fontenc}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
\begin{document}
\section*{Handout 1}
This course is about processing of strings. Lets start with what we mean by \emph{string}. Strings
are lists of characters drawn from an \emph{alphabet}. If nothing else is specified, we usually assume
the alphabet are letters $a$, $b$, \ldots, $z$ and $A$, $B$, \ldots $Z$. Sometimes we explicitly
restrict strings to only contain the letters $a$ and $b$. Then we say the alphabet is the set $\{a, b\}$.
There are many ways how we write string. Since they are lists of characters we might write
them as {\it "hello"} being enclosed by double quotes. This is a short-hand for the list
\[
[\text{\it h, e, l, l, o}]
\]
\noindent
The important point is that we can always decompose strings. For example we often consider the
first character of a string, say $h$, and the ``rest'' of a string {\it "ello"}.
There are also some subtleties with the empty string, sometimes written as {\it ""} or as the empty list
of characters $[\,]$. Two strings, say $s_1$ and $s_2$, can be \emph{concatenated} which is written
as $s_1 @ s_2$. For example if we have the two strings {\it "foo"} and {\it "bar"}, their concatenation
gives {\it "foobar"}.
We often need to talk about sets of strings. For example the set of all strings
\[
\{\text{\it "", "a", "b", "c",\ldots,"z", "aa", "ab", "ac", \ldots, "aaa", \ldots}\}
\]
\noindent
Any set of strings, not just the set of all strings, is often called a \emph{language}. The idea behind
this choice is that if we enumerate, say, all words/strings from a dictionary, like
\[
\{\text{\it "the", "of", "milk", "name", "antidisestablishmentarianism", \ldots}\}
\]
\noindent
then we have essentially described the English language, or more precisely all
strings that can be used in a sentence of the English language. French would be a
different set of string, and so on. In the context of this course, a language might
not necessarily make sense from a natural language perspective. For example
the set of all strings from above is a language, as is the empty set (of strings). The
empty set of strings is often written as $\varnothing$ or $\{\,\}$. Note that there is a
difference between the empty set, or empty language, and the set, or language, that
contains the empty string $\{\text{""}\}$: the former has no elements, the latter has one
element.
As seen there are languages which contain infinitely many strings, like the set of all strings.
The ``natural'' languages English, French and so on contain many but only finitely many
strings (the ones listed in a good dictionary). It might be therefore surprising that the
language consisting of all email addresses is infinite if we assume it is defined by the
regular expression\footnote{See \url{http://goo.gl/5LoVX7}}
\[
([\text{\it{}a-z0-9\_.-}]^+)@([\text{\it a-z0-9.-}]^+).([\text{\it a-z.}]^{\{2,6\}})
\]
\noindent
The reason is that for example before the $@$-sign there can be any string you want if it
is made up from letters, digits, underscore, dot and hyphen---there are infinitely many
of those. Similarly the string after the $@$-sign can be any string. This does not mean
that every string is an email address. For example
\[
\text{\it foo}@\text{\it bar}.\text{\it c}
\]
\noindent
is not, since the top-level-domains must be of length of at least two. Note that there is
the convention that uppercase letters are treated in email-addresses as if they were
lower-case.
\bigskip
Before we expand on the topic of regular expressions, let us review some operations on
sets. We will use capital letters, such as $A$, $B$ and so on, to stand for sets of strings.
The union of two sets is written as usual as $A \cup B$. We also need to define the
\emph{concatenation} of two sets (of strings). This can be defined as
\[
A @ B \dn \{s_1@ s_2 | s_1 \in A \wedge s_2 \in B \}
\]
\noindent
which essentially means take the first string from the set $A$ and concatenate it with every
string in the set $B$, then take the second string from $A$ and so on. We also need to define
the power of a set, written as $A^n$. This is defined inductively as follows
\begin{center}
\begin{tabular}{rcl}
$A^0$ & $\dn$ & $\{[\,]\}$ \\
$A^{n+1}$ & $\dn$ & $A @ A^n$\\
\end{tabular}
\end{center}
\noindent
Finally we need the \emph{star} of a set of strings, written $A^*$. This is defined as the union
of every power of $A^n$ for every $n\ge 0$. The mathematical notation for this operation is
\[
A^* \dn \bigcup_{0\le n} A^n
\]
\noindent
This means the star of a set $A$ contains always the empty string, one copy of every string in $A$, two
copies and so on. In case $A=\{"a\}$ we have
\[
A^* = \{"", "a", "aa", "aaa", \ldots\}
\]
\noindent
Be aware that these operations sometimes have non-intuitive properties, for example
\begin{center}
\begin{tabular}{ccc}
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
$A \cup \varnothing$ & $=$ & $A$\\
$A \cup A$ & $=$ & $A$\\
$A \cup B$ & $=$ & $B \cup A$\\
\end{tabular} &
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
$A @ B$ & $\not =$ & $B @ A$\\
$A @ \varnothing$ & $=$ & $\varnothing @ A = \varnothing$\\
$A @ \{""\}$ & $=$ & $\{""\} @ A = A$\\
\end{tabular} &
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
$\varnothing^*$ & $=$ & $\{""\}$\\
$\{""\}^*$ & $=$ & $\{""\}$\\
$A^1$ & $=$ & $A$\\
\end{tabular}
\end{tabular}
\end{center}
\bigskip
\noindent
\emph{Regular expressions} are meant for conveniently describing languages...at least languages
we are interested in in Computer Science. For example there is no convenient regular expression
for describing the English language short of enumerating all English words/strings like in a dictionary.
But they seem useful for describing all permitted email addresses, as seen above.
Regular expressions are given by the following grammar:
\begin{center}
\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l}
$r$ & $::=$ & $\varnothing$ & null\\
& $\mid$ & $\epsilon$ & empty string / "" / []\\
& $\mid$ & $c$ & character\\
& $\mid$ & $r_1 \cdot r_2$ & sequence\\
& $\mid$ & $r_1 + r_2$ & alternative / choice\\
& $\mid$ & $r^*$ & star (zero or more)\\
\end{tabular}
\end{center}
\noindent
There are some subtleties you should be aware of. The letter $c$ stands for any character from the
alphabet. Second, we will use parentheses to disambiguate
regular expressions. For example we will write $(r_1 + r_2)^*$, which is different from $r_1 + (r_2)^*$.
The former means roughly zero or more times $r_1$ or $r_2$, while the latter means $r_1$ or zero or more times
$r_2$. We should also write $(r_1 + r_2) + r_3$ which is a regular expression different from $r_1 + (r_2 + r_3)$,
but in case of $+$ and $\cdot$ we actually do not care and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2 \cdot r_3$,
respectively. The reasons for this will become clear shortly. In the literature you will often find that the choice
$r_1 + r_2$ is written as $r_1\mid{}r_2$. In case of $\cdot$ we will even often omit it all together. For example
the regular expression for email addresses is meant to be of the form
\[
([\ldots])^+ \cdot @ \cdot ([\ldots])^+ \cdot . \cdot \ldots
\]
\noindent
meaning first comes a name (specified by the regular expression $([\ldots])^+$), then an $@$-sign, then
a domain name (specified by the regular expression $([\ldots])^+$), then a top-level domain. Similarly if
we want to specify the regular expression for the string {\it "hello"} we should write
\[
{\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}
\]
\noindent
but often just write {\it hello}.
Another source of confusion might be that we use the term \emph{regular expressions} for the ones used in ``theory''
and the ones in ``practice''. In this course by default we refer to the regular expressions defined by the grammar above.
In ``practice'' we often use $r^+$ for one or more times, $\backslash{}d$ to stand for a digit, $r^?$ 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 mere convenience
as they can be seen as shorthand for
\begin{center}
\begin{tabular}{rcl}
$r^+$ & $\mapsto$ & $r\cdot r^*$\\
$r^?$ & $\mapsto$ & $\epsilon + r$\\
$\backslash d$ & $\mapsto$ & $0 + 1 + 2 + \ldots + 9$\\
$[\text{\it a - z}]$ & $\mapsto$ & $a + b + \ldots + z$\\
\end{tabular}
\end{center}
\noindent
We will see later that the \emph{not}-regular-expression can also be seen as convenience. This regular
expression is supposed to stand for every string \emph{not} match by a regular expression. We will write
such regular expressions as $~r$. While being ``convenience'' it is often not so clear what the shorthand for
these kind of regular expressions is.
So far we have only considered informally what the \emph{meaning} of a regular expression is.
Formally we associate with every regular expression a set of strings which are matched by this
regular expression. This can be formally defined as
\begin{center}
\begin{tabular}{rcl}
$L(\varnothing)$ & $\dn$ & $\{\,\}$\\
$L(\epsilon)$ & $\dn$ & $\{""\}$\\
$L(c)$ & $\dn$ & $\{"c"\}$\\
$L(r_1+ r_2)$ & $\dn$ & $L(r_1) \cup L(r_2)$\\
$L(r_1 \cdot r_2)$ & $\dn$ & $\{s_1@ s_2 | s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$\\
$L(r^*)$ & $\dn$ & $\bigcup_{n \ge 0} L(r)^n$\\
\end{tabular}
\end{center}
\noindent
This means we can now precisely state what the meaning, for example, of the regular expression
${\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}$ is, namely
$L({\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}) = \{\text{\it"hello"}\}$. Similarly if we have the choice
$a + b$, the meaning is $L(a + b) = \{\text{\it"a"}, \text{\it"b"}\}$, namely the only two strings which can possibly
be matched by this choice.
The point of this definition is that we can now precisely specify when a string is matched by a
regular expression, namely a string, say $s$, is matched by a regular expression, say $r$, if
and only if $s \in L(r)$. In fact we will write a program {\it match} that takes any string $s$ and
any regular expression $r$ as argument and returns \emph{yes}, if $s \in L(r)$ and \emph{no},
if $s \not\in L(r)$. We leave this for the next lecture.
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: