|
1 \documentclass{article} |
|
2 \usepackage{charter} |
|
3 \usepackage{hyperref} |
|
4 \usepackage{amssymb} |
|
5 \usepackage{amsmath} |
|
6 \usepackage[T1]{fontenc} |
|
7 |
|
8 \begin{document} |
|
9 |
|
10 \section*{Handout 1} |
|
11 |
|
12 This course is about processing of strings. Lets start with what we mean by \emph{string}. Strings |
|
13 are lists of characters drawn from an \emph{alphabet}. If nothing else is specified, we usually assume |
|
14 the alphabet are letters $a$, $b$, \ldots, $z$ and $A$, $B$, \ldots $Z$. Sometimes we explicitly |
|
15 restrict strings to only contain the letters $a$ and $b$. Then we say the alphabet is the set $\{a, b\}$. |
|
16 |
|
17 There are many ways how we write string. Since they are lists of characters we might write |
|
18 them as {\it "hello"} being enclosed by double quotes. This is a short-hand for the list |
|
19 |
|
20 \[ |
|
21 [\text{\it h, e, l, l, o}] |
|
22 \] |
|
23 |
|
24 \noindent |
|
25 The important point is that we can always decompose strings. For example we often consider the |
|
26 first character of a string, say $h$, and the ``rest'' of a string {\it "ello"}. |
|
27 There are also some subtleties with the empty string, sometimes written as {\it ""} or as the empty list |
|
28 of characters $[\,]$. |
|
29 |
|
30 We often need to talk about sets of strings. For example the set of all strings |
|
31 |
|
32 \[ |
|
33 \{\text{\it "", "a", "b", "c",\ldots,"z", "aa", "ab", "ac", \ldots, "aaa", \ldots}\} |
|
34 \] |
|
35 |
|
36 \noindent |
|
37 Any set of strings, not just the set of all strings, is often called a \emph{language}. The idea behind |
|
38 this choice is that if we enumerate, say, all words/strings from a dictionary, like |
|
39 |
|
40 \[ |
|
41 \{\text{\it "the", "of", "milk", "name", "antidisestablishmentarianism", \ldots}\} |
|
42 \] |
|
43 |
|
44 \noindent |
|
45 then we have essentially described the English language, or more precisely all |
|
46 strings that can be used in a sentence of the English language. French would be a |
|
47 different set of string, and so on. In the context of this course, a language might |
|
48 not necessarily make sense from a natural language perspective. For example |
|
49 the set of all strings from above is a language, as is the empty set (of strings). The |
|
50 empty set of strings is often written as $\varnothing$ or $\{\,\}$. Note that there is a |
|
51 difference between the empty set $\{\,\}$ and the set that contains the empty string $\{\text{""}\}$. |
|
52 |
|
53 \end{document} |
|
54 |
|
55 %%% Local Variables: |
|
56 %%% mode: latex |
|
57 %%% TeX-master: t |
|
58 %%% End: |