\documentclass{article}+
−
\usepackage{charter}+
−
\usepackage{hyperref}+
−
\usepackage{amssymb}+
−
\usepackage{amsmath}+
−
\usepackage[T1]{fontenc}+
−
+
−
\begin{document}+
−
+
−
\section*{Handout 1}+
−
+
−
This course is about processing of strings. Lets start with what we mean by \emph{string}. Strings+
−
are lists of characters drawn from an \emph{alphabet}. If nothing else is specified, we usually assume +
−
the alphabet are letters $a$, $b$, \ldots, $z$ and $A$, $B$, \ldots $Z$. Sometimes we explicitly+
−
restrict strings to only contain the letters $a$ and $b$. Then we say the alphabet is the set $\{a, b\}$.+
−
+
−
There are many ways how we write string. Since they are lists of characters we might write+
−
them as {\it "hello"} being enclosed by double quotes. This is a short-hand for the list+
−
+
−
\[+
−
[\text{\it h, e, l, l, o}]+
−
\]+
−
+
−
\noindent+
−
The important point is that we can always decompose strings. For example we often consider the+
−
first character of a string, say $h$, and the ``rest''  of a string {\it "ello"}. +
−
There are also some subtleties with the empty string, sometimes written as {\it ""} or as the empty list+
−
of characters $[\,]$. +
−
+
−
We often need to talk about sets of strings. For example the set of all strings+
−
+
−
\[+
−
\{\text{\it "", "a", "b", "c",\ldots,"z", "aa", "ab", "ac", \ldots, "aaa", \ldots}\}+
−
\]+
−
+
−
\noindent+
−
Any set of strings, not just the set of all strings, is often called a \emph{language}. The idea behind+
−
this choice is that if we enumerate, say, all words/strings from a dictionary, like +
−
+
−
\[+
−
\{\text{\it "the", "of", "milk", "name", "antidisestablishmentarianism", \ldots}\}+
−
\]+
−
+
−
\noindent+
−
then we have essentially described the English language, or more precisely all+
−
strings that can be used in a sentence of the English language. French would be a+
−
different set of string, and so on. In the context of this course, a language might +
−
not necessarily make sense from a natural language perspective. For example+
−
the set of all strings from above is a language, as is the empty set (of strings). The+
−
empty set of strings is often written as $\varnothing$ or $\{\,\}$. Note that there is a +
−
difference between the empty set $\{\,\}$ and the set that contains the empty string $\{\text{""}\}$.+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−