\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: 
