67 contain only the letters $a$ and $b$, for example. In this |
67 contain only the letters $a$ and $b$, for example. In this |
68 case we will state that the alphabet is the set $\{a, b\}$. |
68 case we will state that the alphabet is the set $\{a, b\}$. |
69 |
69 |
70 \defn{Strings} are lists of characters. Unfortunately, there |
70 \defn{Strings} are lists of characters. Unfortunately, there |
71 are many ways how we can write down strings. In programming |
71 are many ways how we can write down strings. In programming |
72 languages, they are usually written as \dq{$hello$} where the |
72 languages, they are usually written as \dq{\texttt{hello}} where the |
73 double quotes indicate that we are dealing with a string. In |
73 double quotes indicate that we are dealing with a string. In |
74 programming languages, such as Scala, strings have a special |
74 typed programming languages, such as Scala, strings have a special |
75 type---namely \pcode{String} which is different from the type |
75 type---namely \pcode{String} which is different from the type |
76 for lists of chatacters. This is because strings can be |
76 for lists of chatacters. This is because strings can be |
77 efficiently represented in memory, unlike general lists. Since |
77 efficiently represented in memory, unlike general lists. Since |
78 \code{String} and the type of lists of characters, |
78 \code{String} and the type of lists of characters, |
79 \code{List[Char]} are not the same, we need to explicitly |
79 \code{List[Char]} are not the same, we need to explicitly |
112 simplify our life and just drop the double quotes whenever it |
112 simplify our life and just drop the double quotes whenever it |
113 is clear we are talking about strings, So we will often just |
113 is clear we are talking about strings, So we will often just |
114 write \textit{foo}, \textit{bar}, \textit{foobar} or |
114 write \textit{foo}, \textit{bar}, \textit{foobar} or |
115 \textit{foo $@$ bar}. |
115 \textit{foo $@$ bar}. |
116 |
116 |
117 Occasionally we will use the notation $a^n$ for strings, which |
117 Occasionally we will use the notation $a^n$ for strings, which stands |
118 stands for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is |
118 for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is a string that |
119 a string that has as many $a$s by as many $b$s. |
119 has as many $a$s by as many $b$s. A simple property of string |
120 |
120 concatenation is \emph{associativity}, meaning |
121 A simple property of string concatenation is |
|
122 \emph{associativity}, meaning |
|
123 |
121 |
124 \[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\] |
122 \[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\] |
125 |
123 |
126 \noindent are always equal strings. The empty string behaves |
124 \noindent are always equal strings. The empty string behaves |
127 like a \emph{unit element}, therefore |
125 like a \emph{unit element}, therefore |
139 |
137 |
140 \[ |
138 \[ |
141 \{1, 2, 3\} |
139 \{1, 2, 3\} |
142 \] |
140 \] |
143 |
141 |
144 \noindent The notation $\in$ means \emph{element of}, so $1 |
142 \noindent The notation $\in$ means \emph{element of}, so $1 \in \{1, |
145 \in \{1, 2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false. |
143 2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false. Not that the |
146 Sets can potentially have infinitely many elements. For |
144 \emph{list} $[1, 2, 3]$ is something different from the \emph{set} |
147 example the set of all natural numbers $\{0, 1, 2, \ldots\}$ |
145 $\{1, 2, 3\}$: in the former we care about the order and potentially |
148 is infinite. This set is often also abbreviated as |
146 several occurrences of a number; while with the latter we do not. |
149 $\mathbb{N}$. We can define sets by giving all elements, for |
147 Also sets can potentially have infinitely many elements. For example |
150 example $\{0, 1\}$ for the set containing just $0$ and $1$, |
148 the set of all natural numbers $\{0, 1, 2, \ldots\}$ is infinite. This |
151 but also by \defn{set comprehensions}. For example the set of |
149 set is often also abbreviated as $\mathbb{N}$. Lists can be very large, but they cannot contain infinitely many elements. |
152 all even natural numbers can be defined as |
150 |
|
151 We can define sets by giving all elements, for example $\{0, 1\}$ for |
|
152 the set containing just $0$ and $1$, but also by \defn{set |
|
153 comprehensions}. For example the set of all even natural numbers can |
|
154 be defined as |
153 |
155 |
154 \[ |
156 \[ |
155 \{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\} |
157 \{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\} |
156 \] |
158 \] |
157 |
159 |
160 |
162 |
161 \[ |
163 \[ |
162 \{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\} |
164 \{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\} |
163 \] |
165 \] |
164 |
166 |
165 \noindent Notice that set comprehensions could be used |
167 \noindent Can you see why this defines the set $\{0, 1, 2\}$? Notice |
166 to define set union, intersection and difference: |
168 that set comprehensions could be used to define set union, |
|
169 intersection and difference: |
167 |
170 |
168 \begin{eqnarray*} |
171 \begin{eqnarray*} |
169 A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\ |
172 A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\ |
170 A \cap B & \dn & \{x\;|\; x \in A \wedge x \in B\}\\ |
173 A \cap B & \dn & \{x\;|\; x \in A \wedge x \in B\}\\ |
171 A \backslash B & \dn & \{x\;|\; x \in A \wedge x \not\in B\} |
174 A \backslash B & \dn & \{x\;|\; x \in A \wedge x \not\in B\} |
198 \ldots |
201 \ldots |
199 \] |
202 \] |
200 |
203 |
201 \noindent but using the big union notation is more concise. |
204 \noindent but using the big union notation is more concise. |
202 |
205 |
203 While this stuff about sete might all look trivial or even |
206 While this stuff about sets might all look trivial or even needlessly |
204 needlessly pedantic, \emph{Nature} is never simple. If you |
207 pedantic, \emph{Nature} is never simple. If you want to be amazed how |
205 want to be amazed how complicated sets can get, watch out for |
208 complicated sets can get, watch out for the last lecture just before |
206 the last lecture just before Christmas where I want you to |
209 Christmas where I want to convince you of the fact that some sets are |
207 convince you of the fact that some sets are more infinite than |
210 more infinite than others. Yes, you read correctly, there can be sets |
208 others. Actually that will be a fact that is very relevant to |
211 that are ``more infinite'' then others. If you think this is obvious: |
209 the material of this module. |
212 say you have the infinite set $\{1, 2, 3, 4, \ldots\}$ which is all |
|
213 the natural numbers except $0$, and then compare it to the set |
|
214 $\{0, 1, 2, 3, 4, \ldots\}$ which contains the $0$. Yes, the second must be more infinite\ldots{} well, then think again. Because the two |
|
215 infinite sets |
|
216 |
|
217 \begin{center} |
|
218 $\{1, 2, 3, 4, \ldots\}$ and |
|
219 $\{0, 1, 2, 3, 4, \ldots\}$ |
|
220 \end{center} |
|
221 |
|
222 \noindent |
|
223 contain actually the same number of elements. Does this make sense? |
|
224 Though this might all look strange this about infinite sets will be a |
|
225 topic that is very relevant to the material of this module. It tells |
|
226 us what we can compute with a computer (actually algorithm) and what |
|
227 we cannot. |
210 |
228 |
211 Another important notion in this module are \defn{languages}, which |
229 Another important notion in this module are \defn{languages}, which |
212 are sets of strings. One of the main goals for us will be how to |
230 are sets of strings. One of the main goals for us will be how to |
213 (formally) specify languages and to find out whether a string |
231 (formally) specify languages and to find out whether a string |
214 is in a language or not.\footnote{You might wish to ponder |
232 is in a language or not.\footnote{You might wish to ponder |