8 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2020} |
8 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2020} |
9 |
9 |
10 |
10 |
11 \section*{A Crash-Course on Notation} |
11 \section*{A Crash-Course on Notation} |
12 |
12 |
13 There are an innumerable number of books available on compilers, automata theory |
13 There are innumerable books available on compilers, automata theory |
14 and formal languages. Unfortunately, they often use their own |
14 and formal languages. Unfortunately, they often use their own |
15 notational conventions and their own symbols. This handout is meant to |
15 notational conventions and their own symbols. This handout is meant to |
16 clarify some of the notation I will use. I apologise in advance that |
16 clarify some of the notation I will use. I apologise in advance that |
17 sometimes I will be a bit fuzzy\ldots the problem is that often we |
17 sometimes I will be a bit fuzzy\ldots the problem is that often we |
18 want to have convenience in our mathematical definitions (to make them |
18 want to have convenience in our mathematical definitions (to make them |
114 \dq{\textit{bar}}, then their concatenation, written |
114 \dq{\textit{bar}}, then their concatenation, written |
115 \dq{\textit{foo}} $@$ \dq{\textit{bar}}, gives |
115 \dq{\textit{foo}} $@$ \dq{\textit{bar}}, gives |
116 \dq{\textit{foobar}}. But as said above, we will often |
116 \dq{\textit{foobar}}. But as said above, we will often |
117 simplify our life and just drop the double quotes whenever it |
117 simplify our life and just drop the double quotes whenever it |
118 is clear we are talking about strings. So we will just |
118 is clear we are talking about strings. So we will just |
119 write \textit{foo}, \textit{bar}, \textit{foobar} |
119 write \textit{foo}, \textit{bar}, \textit{foobar}, |
120 \textit{foo $@$ bar} and so on. |
120 \textit{foo $@$ bar} and so on. |
121 |
121 |
122 Occasionally we will use the notation $a^n$ for strings, which stands |
122 Occasionally we will use the notation $a^n$ for strings, which stands |
123 for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is a string that |
123 for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is a string that |
124 has some number of $a$s followed by the same number of $b$s. |
124 has some number of $a$s followed by the same number of $b$s. |
252 $\{0, 1, 2, 3, 4, \ldots\}$ |
252 $\{0, 1, 2, 3, 4, \ldots\}$ |
253 \end{center} |
253 \end{center} |
254 |
254 |
255 \noindent |
255 \noindent |
256 contain actually the same amount of elements. Does this make sense to you? |
256 contain actually the same amount of elements. Does this make sense to you? |
257 If yes, good. If not, then something to learn about. |
257 If yes, good. If not, then something to learn about. |
258 |
258 |
259 Though this might all look strange, infinite sets will be a |
259 Though this might all look strange, infinite sets will be a topic that |
260 topic that is very relevant to the material of this module. It tells |
260 is very relevant to the material of this module. It tells us what we |
261 us what we can compute with a computer (actually an algorithm) and what |
261 can compute with a computer (actually an algorithm) and what we |
262 we cannot. But during the first 9 lectures we can go by without this |
262 cannot. But during the first 9 lectures we can go by without this |
263 ``weird'' stuff. End of aside.\smallskip |
263 ``weird'' stuff. \textbf{Update:} Unfortunately we have now so much |
|
264 material about compilers in the module that I needed to drop this |
|
265 lecture about infinite sets. This is really a pity because notions |
|
266 like infinity (and decidability) play important roles in compilers as |
|
267 soon as one goes beyond the basics. Fortunately you can get pretty much |
|
268 the same |
|
269 material from very slick videos produced by the Youtube channel Veritasium |
|
270 (\textit{How An Infinite Hotel Ran Out Of |
|
271 Room}).\video{https://www.youtube.com/watch?v=OxGsU8oIWjY} End of |
|
272 aside.\smallskip |
264 |
273 |
265 Another important notion in this module are \defn{languages}, which |
274 Another important notion in this module are \defn{languages}, which |
266 are sets of strings. One of the main goals for us will be how to |
275 are sets of strings. One of the main goals for us will be how to |
267 (formally) specify languages and to find out whether a string |
276 (formally) specify languages and to find out whether a string |
268 is in a language or not.\footnote{You might wish to ponder |
277 is in a language or not.\footnote{You might wish to ponder |