\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../langs}+ −
+ −
+ −
+ −
\begin{document}+ −
+ −
\section*{A Crash-Course on Notation}+ −
+ −
There are innumerable books available about automata and+ −
formal languages. Unfortunately, they often use their own+ −
notational conventions and their own symbols. This handout is+ −
meant to clarify some of the notation I will use.+ −
+ −
\subsubsection*{Characters and Strings}+ −
+ −
The most important concept in this module are strings. Strings+ −
are composed of \defn{characters}. While characters are surely+ −
a familiar concept, we will make one subtle distinction in+ −
this module. If we want to refer to concrete characters, like+ −
\code{a}, \code{b}, \code{c} and so on, we use a typewriter font.+ −
Accordingly if we want to refer to the concrete characters of+ −
my email address we shall write+ −
+ −
\begin{center}+ −
\pcode{christian.urban@kcl.ac.uk}+ −
\end{center}+ −
+ −
\noindent If we also need to explicitly indicate the ``space''+ −
character, we write \VS{}\hspace{1mm}. For example+ −
+ −
\begin{center}+ −
\tt{}hello\VS\hspace{0.5mm}world+ −
\end{center}+ −
+ −
+ −
\noindent But often we do not care which particular characters+ −
we use. In such cases we use the italic font and write $a$,+ −
$b$, $c$ and so on for characters. Therefore if we need a+ −
representative string, we might write+ −
+ −
\begin{equation}\label{abracadabra}+ −
abracadabra+ −
\end{equation}+ −
+ −
\noindent In this string, we do not really care what the+ −
characters stand for, except we do care about the fact that+ −
for example the character $a$ is not equal to $b$ and so on.+ −
+ −
An \defn{alphabet} is a (non-empty) finite set of characters.+ −
Often the letter $\Sigma$ is used to refer to an alphabet. For+ −
example the ASCII characters \pcode{a} to \pcode{z} form an+ −
alphabet. The digits $0$ to $9$ are another alphabet. The+ −
Greek letters $\alpha$ to $\omega$ also form an alphabet. If+ −
nothing else is specified, we usually assume the alphabet+ −
consists of just the lower-case letters $a$, $b$, \ldots, $z$.+ −
Sometimes, however, we explicitly want to restrict strings to+ −
contain only the letters $a$ and $b$, for example. In this+ −
case we will state that the alphabet is the set $\{a, b\}$. + −
+ −
\defn{Strings} are lists of characters. Unfortunately, there+ −
are many ways how we can write down strings. In programming+ −
languages, they are usually written as \dq{$hello$} where the+ −
double quotes indicate that we are dealing with a string. But+ −
since we regard strings as lists of characters we could also+ −
write this string as+ −
+ −
\[+ −
[\text{\it h, e, l, l, o}] \;\;\text{or simply}\;\; \textit{hello}+ −
\]+ −
+ −
\noindent The important point is that we can always decompose+ −
such strings. For example, we will often consider the first+ −
character of a string, say $h$, and the ``rest'' of a string+ −
say \dq{\textit{ello}} when making definitions about strings.+ −
There are also some subtleties with the empty string,+ −
sometimes written as \dq{} but also as the empty list of+ −
characters $[\,]$.\footnote{In the literature you can also+ −
often find that $\varepsilon$ or $\lambda$ is used to+ −
represent the empty string.} + −
+ −
Two strings, say $s_1$ and $s_2$, can be \defn{concatenated},+ −
which we write as $s_1 @ s_2$. Suppose we are given two+ −
strings \dq{\textit{foo}} and \dq{\textit{bar}}, then their+ −
concatenation, writen \dq{\textit{foo}} $@$ \dq{\textit{bar}},+ −
gives \dq{\textit{foobar}}. Often we will simplify our life+ −
and just drop the double quotes whenever it is clear we are+ −
talking about strings, writing as already in+ −
\eqref{abracadabra} just \textit{foo}, \textit{bar},+ −
\textit{foobar} or \textit{foo $@$ bar}.+ −
+ −
Some simple properties of string concatenation hold. For+ −
example the concatenation operation is \emph{associative},+ −
meaning+ −
+ −
\[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\] + −
+ −
\noindent are always equal strings. The empty string behaves+ −
like a unit element, therefore+ −
+ −
\[s \,@\, [] = [] \,@\, s = s\]+ −
+ −
+ −
Occasionally we will use the notation $a^n$ for strings, which + −
stands for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is+ −
a string that has as many $a$s as $b$s.+ −
+ −
Note however that while for us strings are just lists of+ −
characters, programming languages often differentiate between+ −
the two concepts. In Scala, for example, there is the type of+ −
\code{String} and the type of lists of characters,+ −
\code{List[Char]}. They are not the same and we need to+ −
explicitly coerce elements between the two types, for example+ −
+ −
\begin{lstlisting}[numbers=none]+ −
scala> "abc".toList+ −
res01: List[Char] = List(a, b, c)+ −
\end{lstlisting}+ −
+ −
+ −
\subsubsection*{Sets and Languages}+ −
+ −
We will use the familiar operations $\cup$, $\cap$, $\subset$+ −
and $\subseteq$ for sets. For the empty set we will either+ −
write $\varnothing$ or $\{\,\}$. The set containing the+ −
natural numbers $1$, $2$ and $3$, for example, we will write+ −
with curly braces as+ −
+ −
\[+ −
\{1, 2, 3\}+ −
\]+ −
+ −
\noindent The notation $\in$ means \emph{element of}, so $1+ −
\in \{1, 2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false.+ −
Sets can potentially have infinitely many elements. For+ −
example the set of all natural numbers $\{0, 1, 2, \ldots\}$+ −
is infinite. This set is often also abbreviated as+ −
$\mathbb{N}$. We can define sets by giving all elements, for+ −
example $\{0, 1\}$, but also by \defn{set comprehensions}. For+ −
example the set of all even natural numbers can be defined as+ −
+ −
\[+ −
\{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\}+ −
\]+ −
+ −
\noindent Though silly, but the set $\{0, 1, 2\}$ could also be+ −
defined by the following set comprehension+ −
+ −
\[+ −
\{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\}+ −
\]+ −
+ −
\noindent Notice that set comprehensions could be used+ −
to define set union, intersection and difference:+ −
+ −
\begin{eqnarray*}+ −
A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\+ −
A \cap B & \dn & \{x\;|\; x \in A \wedge x \in B\}\\+ −
A \backslash B & \dn & \{x\;|\; x \in A \wedge x \not\in B\} + −
\end{eqnarray*}+ −
+ −
\noindent In general set comprehensions are of the form+ −
$\{a\;|\;P\}$ which stands for the set of all elements $a$+ −
(from some set) for which some property $P$ holds.+ −
+ −
For defining sets, we will also often use the notion of the+ −
``big union''. An example is as follows:+ −
+ −
\begin{equation}\label{bigunion}+ −
\bigcup_{0\le n}\; \{n^2, n^2 + 1\}+ −
\end{equation}+ −
+ −
\noindent which is the set of all squares and their immediate+ −
successors, so+ −
+ −
\[+ −
\{0, 1, 2, 4, 5, 9, 10, 16, 17, \ldots\}+ −
\]+ −
+ −
\noindent A big union is a sequence of unions which are + −
indexed typically by a natural number. So the big union in+ −
\eqref{bigunion} could equally be written as+ −
+ −
\[+ −
\{0, 1\} \cup \{1, 2\} \cup \{4, 5\} \cup \{9, 10\} \cup + −
\ldots+ −
\]+ −
+ −
\noindent but using the big union notation is more concise.+ −
+ −
An important notion in this module are \defn{languages}, which+ −
are sets of strings. The main goal for us will be how to+ −
(formally) specify languages and to find out whether a string+ −
is in a language or not.\footnote{You might wish to ponder+ −
whether this is in general a hard or easy problem, where+ −
hardness is meant in terms of Turing decidable, for example.}+ −
Note that the language containing the empty string $\{\dq{}\}$+ −
is not equal to $\varnothing$, the empty language (or empty+ −
set): The former contains one element, namely \dq{} (also+ −
written $[\,]$), but the latter does not contain any+ −
element.+ −
+ −
For languages we define the operation of \defn{language+ −
concatenation}, written like in the string case as $A @ B$:+ −
+ −
\begin{equation}\label{langconc}+ −
A @ B \dn \{s_1 @ s_2\;|\; s_1\in A \wedge s_2\in B\}+ −
\end{equation}+ −
+ −
\noindent Be careful to understand the difference: the $@$+ −
in $s_1 @ s_2$ is string concatenation, while $A @ B$ refers + −
to the concatenation of two languages (or sets of strings).+ −
As an example suppose $A=\{ab, ac\}$ and $B=\{zzz, qq, r\}$,+ −
then $A \,@\, B$ is the language+ −
+ −
\[+ −
\{abzzz, abqq, abr, aczzz, acqq, acr\}+ −
\] + −
+ −
\noindent Recall the properties for string concatenation. For+ −
language concatenation we have the following properties+ −
+ −
\begin{center}+ −
\begin{tabular}{ll}+ −
associativity: & $(A @ B) @ C = A @ (B @ C)$\\+ −
unit element: & $A \,@\, \{[]\} = \{[]\} \,@\, A = A$\\+ −
zero element: & $A \,@\, \varnothing = \varnothing \,@\, A = + −
\varnothing$+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent Note the difference in the last two lines: the empty+ −
set behaves like $0$ for multiplication and the set $\{[]\}$+ −
like $1$ for multiplication ($n * 1 = n$ and $n * 0 = 0$).+ −
+ −
Following the language concatenation, we can define a+ −
\defn{language power} operation as follows:+ −
+ −
\begin{eqnarray*}+ −
A^0 & \dn & \{[]\}\\+ −
A^{n+1} & \dn & A \,@\, A^n+ −
\end{eqnarray*}+ −
+ −
\noindent This definition is by recursion on natural numbers.+ −
Note carefully that the zero-case is not defined as the empty+ −
set, but the set containing the empty string. So no matter+ −
what the set $A$ is, $A^0$ will always be $\{[]\}$. (There is+ −
another hint about a connection between the $@$-operation and+ −
multiplication: How is $x^n$ defined recursively and what is+ −
$x^0$?)+ −
+ −
Next we can define the \defn{star operation} for languages:+ −
$A^*$ is the union of all powers of $A$, or short+ −
+ −
\begin{equation}\label{star}+ −
A^* \dn \bigcup_{0\le n}\; A^n+ −
\end{equation}+ −
+ −
\noindent This star operation is often also called+ −
\emph{Kleene-star}. Unfolding the definition in \eqref{star}+ −
gives+ −
+ −
\[+ −
A^0 \cup A^1 \cup A^2 \cup A^3 \cup \ldots+ −
\]+ −
+ −
\noindent+ −
which is equal to + −
+ −
\[+ −
\{[]\} \,\cup\, A \,\cup\, A @ A \,\cup\, A @ A @ A \,\cup\, \ldots+ −
\]+ −
+ −
\noindent We can see that the empty string is always in $A^*$,+ −
no matter what $A$ is. This is because $[] \in A^0$. To make+ −
sure you understand these definitions, I leave you to answer+ −
what $\{[]\}^*$ and $\varnothing^*$ are. + −
+ −
Recall that an alphabet is often referred to by the letter+ −
$\Sigma$. We can now write for the set of all strings over+ −
this alphabet $\Sigma^*$. In doing so we also include the + −
empty string as a possible string over $\Sigma$. So if+ −
$\Sigma = \{a, b\}$, then $\Sigma^*$ is+ −
+ −
\[+ −
\{[], a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, \ldots\}+ −
\]+ −
+ −
\noindent or in other words all strings containing $a$s and+ −
$b$s only, plus the empty string.+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −