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\}