--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/handouts/notation.tex	Sat Sep 06 15:28:59 2014 +0100
@@ -0,0 +1,274 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+
+
+
+\begin{document}
+
+\section*{A Crash-Course on Notation}
+
+\subsubsection*{Characters and Strings}
+
+In this module we will often use \defn{characters}. While they
+are surely familiar, we will make one subtle distinction. If
+we want to refer to concrete characters, like \code{a},
+\code{b} and so on, we use a typewriter font. So if we want to
+refer to the concrete characters of my email address we shall
+write
+
+\begin{center}
+\pcode{christian.urban@kcl.ac.uk}
+\end{center}
+
+\noindent If we need to explicitly indicate the ``space''
+character, we write \VS{}\hspace{1mm}. For example
+
+\begin{center}
+\tt{}hello\VS\hspace{0.5mm}world
+\end{center}
+
+
+\noindent But often we do not care
+about which characters we use. In such cases we us the italic
+font and write $a$, $b$ and so on. So if we need a
+representative string, we might write
+
+\begin{equation}\label{abracadabra}
+abracadabra
+\end{equation}
+
+\noindent We do not really care what the characters stand for,
+except we do care about is that for example the character $a$
+is not equal to $b$.
+
+An \defn{alphabet} is a finite set of characters. Often the
+letter $\Sigma$ is used to refer to an alphabet. For example
+the ASCII characters \pcode{a} to \pcode{z} form an alphabet.
+The digits $0$ to $9$ are another 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\}$. 
+
+\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 dealing with a string. But
+since, strings are lists of characters we could also write
+this string as
+
+\[
+[\text{\it h, e, l, l, o}]
+\]
+
+\noindent The important point is that we can always decompose
+such strings. For example, we will often consider the first
+character of a string, say $h$, and the ``rest'' of a string
+say \dq{\textit{ello}} when making definitions about strings.
+There are some subtleties with the empty string, sometimes
+written as \dq{} 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 \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}.
+
+Some simple properties of string concatenation hold. For
+example the concatenation operation is \emph{associative},
+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
+
+\[s \,@\, [] = [] \,@\, s = s\]
+
+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$ and $\cap$ for
+sets. For the empty set we will either write $\varnothing$ or
+$\{\,\}$. The set containing, for example, the natural numbers
+$1$, $2$ and $3$ we will write as
+
+\[
+\{1, 2, 3\}
+\]
+
+\noindent The notation $\in$ means \emph{element of}, so $1
+\in \{1, 2, 3\}$ is true and $3 \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, like
+$\{0, 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}\}
+\]
+  
+\noindent Though silly, but the set $\{0, 1, 2\}$ could also be
+defined by the following set comprehension
+
+\[
+\{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\}
+\]
+
+\noindent 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\}\\
+A \cap B & \dn & \{x\;|\; x \in A \wedge x \in B\}\\
+A \backslash B & \dn & \{x\;|\; x \in A \wedge x \not\in B\} 
+\end{eqnarray*}
+
+\noindent For defining sets, we will also often use the notion
+of the ``big union''. An example is as follows:
+
+\begin{equation}\label{bigunion}
+\bigcup_{0\le n}\; \{n^2, n^2 + 1\}
+\end{equation}
+
+\noindent which is the set of all squares and their immediate
+successors, so
+
+\[
+\{0, 1, 2, 4, 5, 9, 10, 16, 17, \ldots\}
+\]
+
+\noindent A big union is a sequence of unions which are 
+indexed typically by a natural number. So the big union in
+\eqref{bigunion} could equally be written as
+
+\[
+\{0, 1\} \cup \{1, 2\} \cup \{4, 5\} \cup \{9, 10\} \cup 
+\ldots
+\]
+
+\noindent but using the big union notation is more concise.
+
+An important notion in this module are \defn{Languages}, which
+are sets of strings. The main goal for us will be how to
+(formally) specify languages and to find out whether a string
+is in a language or not. Note that the language containing the
+empty string $\{\dq{}\}$ is not equal to the empty language
+(or empty set): The former contains one element, namely \dq{}
+(also written $[\,]$), but the latter does not contain any.
+
+
+For languages we define the operation of \defn{language
+concatenation}, written $A @ B$:
+
+\begin{equation}\label{langconc}
+A @ B \dn \{s_1 @ s_2\;|\; s_1\in A \wedge s_2\in B\}
+\end{equation}
+
+\noindent Be careful to understand the difference: the $@$
+in $s_1 @ s_2$ is string concatenation, while $A @ B$ refers 
+to the concatenation of two languages (or sets of strings).
+As an example suppose $A=\{ab, ac\}$ and $B=\{zzz, qq, r\}$,
+then $A \,@\, B$ is
+
+
+\[
+\{abzzz, abqq, abr, aczzz, acqq, acr\}
+\] 
+
+\noindent Recall the properties for string concatenation. For
+language concatenation we have the following properties
+
+\begin{center}
+\begin{tabular}{ll}
+associativity: & $(A @ B) @ C = A @ (B @ C)$\\
+unit element:  & $A \,@\, \{[]\} = \{[]\} \,@\, A = A$\\
+zero element:  & $A \,@\, \varnothing = \varnothing \,@\, A = 
+\varnothing$
+\end{tabular}
+\end{center}
+
+\noindent Note the difference: the empty set behaves like $0$
+for multiplication and the set $\{[]\}$ like $1$ for
+multiplication.
+
+Following the language concatenation, we can define a
+\defn{language power} operation as follows:
+
+\begin{eqnarray*}
+A^0     & \dn & \{[]\}\\
+A^{n+1} & \dn & A \,@\, A^n
+\end{eqnarray*}
+
+\noindent This definition is by induction on natural numbers.
+Note carefully that the zero-case is not defined as the empty
+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 and what is $x^0$?)
+
+Next we can define the \defn{star operation} for languages: 
+$A^*$ is the union of all powers of $A$, or short
+
+\[
+A^* \dn \bigcup_{0\le n}\; A^n
+\]
+
+\noindent
+Unfolding this definition
+
+\[
+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
+\]
+
+\noindent we can see that the empty string is always in $A^*$,
+no matter what $A$ is. This is because $[] \in A^0$. To make
+sure you understand these definition, I leave you to answer
+what $\{[]\}^*$ and $\varnothing^*$ 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
+
+\[
+\{[], a, b, ab, ba, aaa, aab, aba, abb, baa, bab, \ldots\}
+\]
+
+\noindent or in other words all strings containing $a$s and 
+$b$s only.
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: