
diff -r 564f7584eff1 -r 245d302791c7 handouts/notation.tex
--- a/handouts/notation.tex	Wed Jun 01 13:04:06 2016 +0100
+++ b/handouts/notation.tex	Tue Jun 14 11:41:48 2016 +0100
@@ -8,10 +8,15 @@
 
 \section*{A Crash-Course on Notation}
 
-There are innumerable books available about compiler, automata
-and formal languages. Unfortunately, they often use their own
-notational conventions and their own symbols. This handout is
-meant to clarify some of the notation I will use.
+There are innumerable books available about compilers,
+automata theory and formal languages. Unfortunately, they
+often use their own notational conventions and their own
+symbols. This handout is meant to clarify some of the notation
+I will use. I appologise in advance that sometimes I will be a
+bit fuzzy\ldots the problem is that often we want to have
+convenience in our mathematical definitions (to make them
+readable and understandable), but sometimes we need precision
+for actual programs.
 
 \subsubsection*{Characters and Strings}
 
@@ -40,13 +45,17 @@
 $b$, $c$ and so on for characters. Therefore if we need a
 representative string, we might write
 
-\begin{equation}\label{abracadabra}
+\[
 abracadabra
-\end{equation}
+\]
 
 \noindent In this string, we do not really care what the
 characters stand for, except we do care about the fact that
 for example the character $a$ is not equal to $b$ and so on.
+Why do I make this distinction? Because we often need to
+define functions using variables ranging over characters. We
+need to somehow say this is a variable, say $c$, ranging over
+characters, while this is the atual character \pcode{c}.
 
 An \defn{alphabet} is a (non-empty) finite set of characters.
 Often the letter $\Sigma$ is used to refer to an alphabet. For
@@ -62,12 +71,26 @@
 \defn{Strings} are lists of characters. Unfortunately, there
 are many ways how we can write down strings. In programming
 languages, they are usually written as \dq{$hello$} where the
-double quotes indicate that we are dealing with a string. But
-since we regard strings as lists of characters we could also
-write this string as
+double quotes indicate that we are dealing with a string. In
+programming languages, such as Scala, strings have a special
+type---namely \pcode{String} which is different from the type
+for lists of chatacters. This is because strings can be
+efficiently represented in memory, unlike general lists. Since
+\code{String} and the type of lists of characters,
+\code{List[Char]} are not the same, we need to explicitly
+coerce elements between the two types, for example
+
+\begin{lstlisting}[numbers=none]
+scala> "abc".toList
+res01: List[Char] = List(a, b, c)
+\end{lstlisting}
+
+\noindent Since in our (mathematical) definitions we regard
+strings as lists of characters, we will also write
+\dq{$hello$} as
 
 \[
-[\text{\it h, e, l, l, o}] \;\;\text{or simply}\;\; \textit{hello}
+[\text{\it h, e, l, l, o}] \qquad\text{or simply}\qquad \textit{hello}
 \]
 
 \noindent The important point is that we can always decompose
@@ -81,44 +104,32 @@
 represent the empty string.} 
 
 Two strings, say $s_1$ and $s_2$, can be \defn{concatenated},
-which we write as $s_1 @ s_2$. Suppose we are given two
-strings \dq{\textit{foo}} and \dq{\textit{bar}}, then their
-concatenation, writen \dq{\textit{foo}} $@$ \dq{\textit{bar}},
-gives \dq{\textit{foobar}}. Often we will simplify our life
-and just drop the double quotes whenever it is clear we are
-talking about strings, writing as already in
-\eqref{abracadabra} just \textit{foo}, \textit{bar},
-\textit{foobar} or \textit{foo $@$ bar}.
+which we write as $s_1 @ s_2$. If we regard $s_1$ and $s_2$ as
+lists of characters, then $@$ is the list-append function.
+Suppose we are given two strings \dq{\textit{foo}} and
+\dq{\textit{bar}}, then their concatenation, writen
+\dq{\textit{foo}} $@$ \dq{\textit{bar}}, gives
+\dq{\textit{foobar}}. But as said above, we will often
+simplify our life and just drop the double quotes whenever it
+is clear we are talking about strings, So we will often just
+write \textit{foo}, \textit{bar}, \textit{foobar} or
+\textit{foo $@$ bar}.
 
-Some simple properties of string concatenation hold. For
-example the concatenation operation is \emph{associative},
-meaning
+Occasionally we will use the notation $a^n$ for strings, which 
+stands for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is
+a string that has as many $a$s by as many $b$s.
+
+A simple property of string concatenation is 
+\emph{associativity}, meaning
 
 \[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\]  
 
 \noindent are always equal strings. The empty string behaves
-like a unit element, therefore
+like a \emph{unit element}, therefore
 
 \[s \,@\, [] = [] \,@\, s = s\]
 
 
-Occasionally we will use the notation $a^n$ for strings, which 
-stands for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is
-a string that has as many $a$s as $b$s.
-
-Note however that while for us strings are just lists of
-characters, programming languages often differentiate between
-the two concepts. In Scala, for example, there is the type of
-\code{String} and the type of lists of characters,
-\code{List[Char]}. They are not the same and we need to
-explicitly coerce elements between the two types, for example
-
-\begin{lstlisting}[numbers=none]
-scala> "abc".toList
-res01: List[Char] = List(a, b, c)
-\end{lstlisting}
-
-
 \subsubsection*{Sets and Languages}
 
 We will use the familiar operations $\cup$, $\cap$, $\subset$
@@ -137,8 +148,9 @@
 example the set of all natural numbers $\{0, 1, 2, \ldots\}$
 is infinite. This set is often also abbreviated as
 $\mathbb{N}$. We can define sets by giving all elements, for
-example $\{0, 1\}$, but also by \defn{set comprehensions}. For
-example the set of all even natural numbers can be defined as
+example $\{0, 1\}$ for the set containing just $0$ and $1$,
+but also by \defn{set comprehensions}. For example the set of
+all even natural numbers can be defined as
 
 \[
 \{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\}
@@ -189,7 +201,15 @@
 
 \noindent but using the big union notation is more concise.
 
-An important notion in this module are \defn{languages}, which
+While this stuff about sete might all look trivial or even
+needlessly pedantic, \emph{Nature} is never simple. If you
+want to be amazed how complicated sets can get, watch out for
+the last lecture just before Christmas where I want you to
+convince you of the fact that some sets are more infinite than
+others. Actually that will be a fact that is very relevant to
+the material of this module.
+
+Another important notion in this module are \defn{languages}, which
 are sets of strings. One of the main goals for us will be how to
 (formally) specify languages and to find out whether a string
 is in a language or not.\footnote{You might wish to ponder
@@ -251,10 +271,10 @@
 $x^0$?)
 
 Next we can define the \defn{star operation} for languages:
-$A^*$ is the union of all powers of $A$, or short
+$A\star$ is the union of all powers of $A$, or short
 
 \begin{equation}\label{star}
-A^* \dn \bigcup_{0\le n}\; A^n
+A\star \dn \bigcup_{0\le n}\; A^n
 \end{equation}
 
 \noindent This star operation is often also called
@@ -272,16 +292,16 @@
 \{[]\} \,\cup\, A \,\cup\, A @ A \,\cup\, A @ A @ A \,\cup\, \ldots
 \]
 
-\noindent We can see that the empty string is always in $A^*$,
+\noindent We can see that the empty string is always in $A\star$,
 no matter what $A$ is. This is because $[] \in A^0$. To make
 sure you understand these definitions, I leave you to answer
-what $\{[]\}^*$ and $\varnothing^*$ are. 
+what $\{[]\}\star$ and $\varnothing\star$ are?
 
 Recall that an alphabet is often referred to by the letter
-$\Sigma$. We can now write for the set of all strings over
-this alphabet $\Sigma^*$. In doing so we also include the 
-empty string as a possible string over $\Sigma$. So if
-$\Sigma = \{a, b\}$, then $\Sigma^*$ is
+$\Sigma$. We can now write for the set of \emph{all} strings
+over this alphabet $\Sigma\star$. In doing so we also include the
+empty string as a possible string over $\Sigma$. So if $\Sigma
+= \{a, b\}$, then $\Sigma\star$ is
 
 \[
 \{[], a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, \ldots\}




