--- a/handouts/notation.tex Tue Sep 26 14:07:29 2017 +0100
+++ b/handouts/notation.tex Tue Sep 26 14:08:49 2017 +0100
@@ -8,15 +8,14 @@
\section*{A Crash-Course on Notation}
-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.
+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 apologise 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 other times we need pedantic
+precision for actual programs.
\subsubsection*{Characters and Strings}
@@ -55,7 +54,7 @@
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}.
+characters, while this is the actual 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
@@ -70,14 +69,14 @@
\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
+languages, they are usually written as \dq{\texttt{hello}} where the
double quotes indicate that we are dealing with a string. In
-programming languages, such as Scala, strings have a special
+typed 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
+for lists of characters. This is because strings can be
+efficiently represented in memory, unlike 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]
@@ -85,9 +84,11 @@
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
+\noindent
+However, we do not want to do this kind of explicit coercion in our
+pencil-and-paper, everyday arguments. So 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}] \qquad\text{or simply}\qquad \textit{hello}
@@ -107,7 +108,7 @@
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{bar}}, then their concatenation, written
\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
@@ -115,12 +116,10 @@
write \textit{foo}, \textit{bar}, \textit{foobar} or
\textit{foo $@$ bar}.
-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
+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 some number of $a$s followed by the same number of $b$s. A simple
+property of string concatenation is \emph{associativity}, meaning
\[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\]
@@ -142,15 +141,20 @@
\{1, 2, 3\}
\]
-\noindent The notation $\in$ means \emph{element of}, so $1
-\in \{1, 2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false.
-Sets can potentially have infinitely many elements. For
-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\}$ 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
+\noindent The notation $\in$ means \emph{element of}, so $1 \in \{1,
+2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false. Note that the
+\emph{list} $[1, 2, 3]$ is something different from the \emph{set}
+$\{1, 2, 3\}$: in the former we care about the order and potentially
+several occurrences of a number; while with the latter we do not.
+Also sets can potentially have infinitely many elements, whereas lists
+cannot. For example
+the set of all natural numbers $\{0, 1, 2, \ldots\}$ is infinite. This
+set is often also abbreviated as $\mathbb{N}$. Lists can be very large, but they cannot contain infinitely many elements.
+
+We can define sets by giving all elements, for 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}\}
@@ -163,8 +167,9 @@
\{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\}
\]
-\noindent Notice that set comprehensions could be used
-to define set union, intersection and difference:
+\noindent Can you see why this defines the set $\{0, 1, 2\}$? Notice
+that set comprehensions could be used to define set union,
+intersection and difference:
\begin{eqnarray*}
A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\
@@ -201,13 +206,30 @@
\noindent but using the big union notation is more concise.
-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.
+As an aside: While this stuff about sets 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 to convince you of the fact that some sets are
+more infinite than others. Yes, you read correctly, there can be sets
+that are ``more infinite'' then others. If you think this is obvious:
+say you have the infinite set $\mathbb{N}\backslash\{0\} = \{1, 2, 3, 4, \ldots\}$ which is all
+the natural numbers except $0$, and then compare it to the set
+$\{0, 1, 2, 3, 4, \ldots\}$ which contains the $0$. If you think,
+the second must be more infinite\ldots{} well, then think again. Because the two
+infinite sets
+
+\begin{center}
+ $\{1, 2, 3, 4, \ldots\}$ and
+ $\{0, 1, 2, 3, 4, \ldots\}$
+\end{center}
+
+\noindent
+contain actually the same number of elements. Does this make sense?
+Though this might all look strange this about infinite sets will be a
+topic that is very relevant to the material of this module. It tells
+us what we can compute with a computer (actually algorithm) and what
+we cannot. But during the first 9 lectures we can go by without this
+``weird'' stuff.
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
@@ -254,7 +276,7 @@
set behaves like $0$ for multiplication and the set $\{[]\}$
like $1$ for multiplication ($n * 1 = n$ and $n * 0 = 0$).
-Following the language concatenation, we can define a
+Using the operation of language concatenation, we can define a
\defn{language power} operation as follows:
\begin{eqnarray*}
@@ -267,7 +289,7 @@
set, but the set containing the empty string. So no matter
what the set $A$ is, $A^0$ will always be $\{[]\}$. (There is
another hint about a connection between the $@$-operation and
-multiplication: How is $x^n$ defined recursively and what is
+multiplication: How is $x^n$ defined in mathematics and what is
$x^0$?)
Next we can define the \defn{star operation} for languages:
@@ -282,14 +304,14 @@
gives
\[
-A^0 \cup A^1 \cup A^2 \cup A^3 \cup \ldots
+A\star \dn A^0 \cup A^1 \cup A^2 \cup A^3 \cup \ldots
\]
\noindent
which is equal to
\[
-\{[]\} \,\cup\, A \,\cup\, A @ A \,\cup\, A @ A @ A \,\cup\, \ldots
+A\star \dn \{[]\} \,\cup\, A \,\cup\, A @ A \,\cup\, A @ A @ A \,\cup\, \ldots
\]
\noindent We can see that the empty string is always in $A\star$,
@@ -299,7 +321,7 @@
Recall that an alphabet is often referred to by the letter
$\Sigma$. We can now write for the set of \emph{all} strings
-over this alphabet $\Sigma\star$. In doing so we also include the
+over this alphabet as $\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