afl-material: comparison handouts/notation.tex

equal deleted inserted replaced

-:352d15782d35
+:71fc4a7a7039
 \usepackage{../langs}
 \begin{document}
-\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}
+\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018}
 \section*{A Crash-Course on Notation}
 There are innumerable books available about compilers, automata theory
 \end{lstlisting}
 \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
+definitions we regard strings as lists of characters and we will also
-write \dq{$hello$} as
+write \dq{$hello$} as list
 \[
 [\text{\it h, e, l, l, o}] \qquad\text{or simply}\qquad \textit{hello}
 \]
 Suppose we are given two strings \dq{\textit{foo}} and
 \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
-is clear we are talking about strings, So we will often just
+is clear we are talking about strings. So we will often just
 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
 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
+We can define sets by giving all their elements, for example $\{0, 1\}$ for
-the set containing just $0$ and $1$, but also by \defn{set
+the set containing just $0$ and $1$. But often we need to use \defn{set
-comprehensions}. For example the set of all even natural numbers can
+comprehensions} to define sets. For example the set of all \emph{even}
-be defined as
+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
+\noindent Set comprehensions consist of a ``base set'' (in this case
+all the natural numbers) and a predicate (here eveness).
+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}\}
+\{n\;|\;  n \in \mathbb{N} \wedge n^2 < 9\}
 \]
 \noindent Can you see why this defines the set $\{0, 1, 2\}$?  Notice
-that set comprehensions could be used to define set union,
+that set comprehensions are quite powerful constructions. For example they
-intersection and difference:
+could be used to define set union,
+set intersection and set 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\}
 \ldots
 \]
 \noindent but using the big union notation is more concise.
-As an aside: While this stuff about sets might all look trivial or even needlessly
+As an aside: While this stuff about sets might all look trivial or
-pedantic, \emph{Nature} is never simple. If you want to be amazed how
+even needlessly pedantic, \emph{Nature} is never simple. If you want
-complicated sets can get, watch out for the last lecture just before
+to be amazed how complicated sets can get, watch out for the last
-Christmas where I want to convince you of the fact that some sets are
+lecture just before Christmas where I want to convince you of the fact
-more infinite than others. Yes, you read correctly, there can be sets
+that some sets are more infinite than other sets. Yes, you read
-that are ``more infinite'' then others. If you think this is obvious:
+correctly, there can be sets that are ``more infinite'' than
-say you have the infinite set $\mathbb{N}\backslash\{0\} = \{1, 2, 3, 4, \ldots\}$ which is all
+others. If you think this is obvious: say you have the infinite set
-the natural numbers except $0$, and then compare it to the set
+$\mathbb{N}\backslash\{0\} = \{1, 2, 3, 4, \ldots\}$ which is all the
-$\{0, 1, 2, 3, 4, \ldots\}$ which contains the $0$. If you think,
+natural numbers except $0$, and then compare it to the set
-the second must be more infinite\ldots{} well, then think again. Because the two
+$\{0, 1, 2, 3, 4, \ldots\}$ which contains the $0$ and all other
-infinite sets
+numbers. 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?
+contain actually the same amount of elements. Does this make sense?
-Though this might all look strange this about infinite sets will be a
+Though this might all look strange, 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.
+``weird'' stuff. End of aside.\smallskip
 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
 \begin{equation}\label{star}
 A\star \dn \bigcup_{0\le n}\; A^n
 \end{equation}
 \noindent This star operation is often also called
-\emph{Kleene-star}. Unfolding the definition in \eqref{star}
+\emph{Kleene-star}. Unfolding the definition in~\eqref{star}
 gives
 \[
 A\star \dn A^0 \cup A^1 \cup A^2 \cup A^3 \cup \ldots
 \]

changeset 550	71fc4a7a7039
parent 505	5b9cf7fbd51a
child 736	d3e477fe6c66