fosap.tex

\documentclass[11pt, a4paper]{article}
\usepackage[left=3cm, right=3cm]{geometry}

% packages
\usepackage{natbib}
\usepackage[utf8]{inputenc}
\usepackage[german]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{bm}
\usepackage{stmaryrd}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{mathrsfs}
\usepackage{mathdots}
\usepackage{mathtools}
\usepackage{listings}
\usepackage[linesnumbered, ruled, vlined, ngerman]{algorithm2e}
\usepackage{enumitem}
\usepackage{wrapfig}
\usepackage{float}
\usepackage{array}
\usepackage[justification=centering]{caption}
\usepackage{subcaption}
\usetikzlibrary{arrows, automata, graphs, shapes, petri, decorations.pathmorphing}

% meta
\clubpenalty = 10000
\widowpenalty = 10000
\displaywidowpenalty = 10000
\parindent = 0pt

% define environments
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}[definition]{Beispiel}
\newtheorem*{example*}{Beispiel}
\newtheorem*{remark*}{Bemerkung}

\theoremstyle{plain}
\newtheorem{theorem}[definition]{Satz}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{corollary}[definition]{Korollar}

\numberwithin{equation}{section}

\renewcommand{\labelenumi}{(\roman{enumi})}
\makeatletter
\newcommand*{\shifttext}[2]{
	\settowidth{\@tempdima}{#2}
	\makebox[\@tempdima]{\hspace*{#1}#2}
}
\makeatother
\def\Rho{\mathrm{P}}

\newenvironment{problem}[1]{\begin{tabular}{|p{.96\textwidth}|} \hline \textsc{#1}\\}{\\ \hline \end{tabular}}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\qedw}{\hfill$\square$}
\newcommand{\qedb}{\hfill$\blacksquare$}
\newcommand{\shuffle}{\mathrel{\shifttext{5pt}{$\equiv$}\shifttext{-5pt}{$=$}}}
\newcommand{\reaches}[1]{\overset{#1}{\rightarrow}}
\newcommand{\reachess}[2]{\overset{#1}{\underset{#2}{\rightarrow}}}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\bin}{bin}
\DeclareMathOperator{\xor}{xor}
\let\emptyset\varnothing

\lstset{numbers=left, xleftmargin=.2\textwidth, xrightmargin=.2\textwidth, basicstyle=\ttfamily\bfseries}

% Here we go...
\begin{document}

% title page
\pagestyle{empty}
\begin{center}
    Rheinisch-Westf\"alische Technische Hochschule Aachen\\[10em]

    \begin{LARGE}
    		Skript zur Vorlesung\\[1.5em]
		\textbf{Formale Systeme, Automaten, Prozesse}
    \end{LARGE}
	\vfill
    \begin{Large}
    		Letzte Änderung:\\
    		\today\\[2em]
		Autor:\\
		Niklas Rieken\\
	\end{Large}
	\vfill
	\includegraphics[scale=.4]{icons/cc.png}
	\includegraphics[scale=.4]{icons/by.png}
	\includegraphics[scale=.4]{icons/sa.png}\\
	Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung -- Weitergabe unter gleichen Bedingungen 4.0 International Lizenz.
\end{center}


\newpage
% acknowledgements
\vspace*{\fill}
\section*{Hinweise}
Dieses Skript entstand aus der Vorlesung Formale Systeme, Automaten, Prozesse an der RWTH Aachen von Prof. Dr. Wolfgang Thomas und Prof. Dr. Martin Grohe vom Lehrstuhl Informatik~7 in den Sommersemestern 2015 und 2016. Ein paar Notationen und Definitionen sind außerdem adaptiert aus dem Skript zu den Diskreten Strukturen und Lineare Algebra I für Informatiker von Dr. Timo Hanke und Prof. Dr. Gerhard Hiß vom Lehrstuhl~D für Mathematik.
\vspace*{\fill}


\newpage
% table of contents
\tableofcontents


\newpage
\pagestyle{headings}
\section{Mathematisches Vorwissen}\label{sec:pre}
In diesem ersten Kapitel fixieren wir einige mathematischen Notationen und geben elementare Sätze aus der diskreten Mathematik, die im weiteren verlauf der Vorlesung benötigt werden. In der Regel sollten nahezu alle Begriffe und Notationen aus dem ersten Semester bereits bekannt sein. Deshalb ist dieses Kapitel eher nur für Sommersemesteranfänger bestimmt. Die in diesem Abschnitt gesammelten Definitionen und Sätze sind nicht alle relevant, aber dennoch nützlich zu kennen im weiteren Verlauf des Studiums.


\subsection{Mengen}\label{sec:pre_sets}
Der Begriff Menge geht auf Georg Cantor aus dem 19. Jahrhundert zurück und wurde (verglichen mit späteren Definitionen in diesem Skript) informell beschrieben.
\begin{quote}
	Unter einer ``Menge`` verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterschiedenen Objekten $m$ unserer Anschauung oder unseres Denkens (welche die ``Elemente`` von $M$ genannt werden) zu einem Ganzen.
\end{quote}

Wir definieren eine Menge wie folgt
\begin{definition}
	Eine \textit{Menge} $M$ ist etwas, zu dem jedes beliebige Objekt $x$ entweder \textit{Element} der Menge ist ($x \in M$), oder nicht ($x \notin M$).
\end{definition}
Mengen selbst können auch wieder als Objekte aufgefasst werden, also Elemente anderer Mengen sein. Wir vermeiden jedoch Aussagen über ``Mengen, die sich selbst enthalten``, da so schnell Widersprüche entstehen können (vgl. Russel'sche Antinomie). Wir schließen uns der weit verbreiteten \textit{Zermelo-Fraenkel-Mengenlehre} an, dazu geben wir jedoch keine Details (diese findet man zum Beispiel in der Logik 2-Vorlesung im Wahlpflichtbereich). Wir schauen uns nur an, wie wir Mengen im allgemeinen betrachten können. Folgende Definition sind dabei elementar.
\begin{definition}\label{def:subsets}
	Seien $M, N$ zwei Mengen. $N$ ist eine \textit{Teilmenge} von $M$ ($N \subseteq M$) bzw. $M$ eine \textit{Obermenge} von $N$ ($M \supseteq N$), wenn für alle $x \in N$ gilt, dass auch $x \in M$.\\
	Wir sagen $N$ ist eine \textit{echte Teilmenge} von $M$ ($N \subset M$) bzw. $M$ eine \textit{echte Obermenge} von $N$ ($M \supset N$), wenn es zusätzlich ein $y \in M$ gibt mit $y \notin N$.\\
	$M$ und $N$ sind \textit{gleich} ($M = N$), wenn sowohl $M \subseteq N$ als auch $N \subseteq M$ gilt.
\end{definition}
Wir kommen nun zum Mächtigkeitsbegriff der Mengenlehre, der für die Anzahl der Elemente einer Menge beschreibt.
\begin{definition}
	Sei $M$ eine Menge. $M$ heißt \textit{endlich}, wenn $M$ nur endlich viele Elemente besitzt, dann beschreibt $\left| M \right|$ die Anzahl der Elemente von $M$. Andernfalls heißt $M$ \textit{unendlich} und wir schreiben $\left| M \right| = \infty$. Man nennt $\left| M \right|$ die \textit{Mächtigkeit} von $M$.
\end{definition}
Um eine konkrete Menge zu zu benennen gibt es im Wesentlichen vier verschiedene Möglichkeiten:
\begin{enumerate}
	\item \textit{Aufzählen.} Die Elemente der Menge werden aufgelistet und in Mengenklammern ($\{, \}$) eingeschlossen. Reihenfolge und Wiederholungen spielen keine Rolle.
		$$
			\{ 3, 4.5, \pi, \diamondsuit \} = \{ \pi, 4.5, \diamondsuit, \diamondsuit, 3 \} \subseteq \{ \diamondsuit, \pi, 4.5, 3, \clubsuit \}. 
		$$
	\item \textit{Beschreiben.} Mengen können durch Worte beschrieben werden.
		$$
			\text{Menge der natürlichen Zahlen} = \{ 0, 1, 2, 3, \ldots \} \eqqcolon \mathbb{N}.
		$$
		Aber Achtung: Natürliche Sprache neigt zu Uneindeutigkeit!
	\item \textit{Aussondern.} Sei $M$ eine Menge, dann ist
		$$
			\{ x \in M \mid \varphi(x) \}
		$$
		die Menge aller Elemente aus $M$, die die Eigenschaft $\varphi$ erfüllen. Zum Beispiel:
		$$
			\mathbb{P} \coloneqq \{ n \in \mathbb{N} \mid n \text{ hat genau zwei Teiler} \}
		$$
		als Menge aller Primzahlen.
	\item \textit{Abbilden.} Sei $M$ eine Menge und $f$ ein Ausdruck, der für jedes $x \in M$ definiert ist. Dann ist
		$$
			\{ f(x) : x \in M \}
		$$
		die Menge aller Ausdrücke $f(x)$, wobei jedes $x \in M$ in $f$ eingesetzt wird. Zum Beispiel:
		$$
			\{ n^2 : n \in \mathbb{N} \}
		$$
		als Menge aller Quadtratzahlen.
\end{enumerate}
Wir können Abbilden und Aussondern auch kombinieren, zum Beispiel mit:
$$
	\{ n^2 : n \in \mathbb{N} \mid n \text{ ungerade} \}
$$
als Menge aller Quadratzahlen von ungeraden natürlichen Zahlen. Man würde hier jedoch abkürzend schreiben:
$$
	\{ n^2 : n \in \mathbb{N} \text{ ungerade} \}
$$
oder auch
$$
	\{ n^2 : n \in 2\mathbb{N}+1 \}.
$$
Eine wichtige Menge haben wir bisher außen vor gelassen: die \textit{leere Menge}. Wir schreiben $\emptyset \coloneqq \{ \}$. Gelegentlich verwenden wir außerdem folgende Notation, wenn wir nur eine endliche geordnete Menge benötigen: $[\ell] \coloneqq \{ 0, 1, \ldots, \ell-1 \}$. Ein-elementige Mengen (z.B. $[1] = \{ 0 \}$) nennt man auch \textit{Singleton}.
\begin{remark*}
	Im Allgemeinen gibt es keine Elemente in Mengen, die mehrfach vorkommen. Man kann dies explizit zulassen, durch \textit{Multimengen}, z.B.: $\{^\ast 1, 1, 2, \pi, \clubsuit, \pi ^\ast\}$.
\end{remark*}


\subsection{Operationen auf Mengen}\label{sec:pre_setops}
Im folgendem betrachten wir Mengen immer als Teilmenge eines \textit{Universums} (oder auch \textit{Grundemenge}) $\mathcal{U}$. In der Analysis ist das typischerweise die Menge der reellen Zahlen $\mathbb{R}$ (oder die Menge der komplexen Zahlen $\mathbb{C}$), die betrachteten Teilmengen sind oftmals Intervalle in denen zum Beispiel Funktionen auf Stetigkeit hin untersucht werden. Vorweg: Wir betrachten später im Allgemeinen das Universum $\Sigma^\ast$ und Sprachen als Teilmenge von eben diesem. Genaueres folgt im nächsten Kapitel.\\
Um die Operatoren auf den Mengen zu veranschaulichen gibt es die sogenannten \textit{Venn-Diagramme}, bei denen Kreise oder Ellipsen die Mengen visualisieren. In Abbildung~\ref{fig:venn_subset} finden wir zum Beispiel für die Inklusion ($\subseteq$) ein entsprechendes Diagramm.
\begin{figure}
	\centering
	\input{figs/venn_subset}
	\caption{Venn-Diagramm für $A \subseteq B$.}
	\label{fig:venn_subset}
\end{figure}
Wir definieren nun einige Operationen auf Mengen ähnlich wie Addition und Multiplikation usw. auf Zahlen. Zusätzlich zur formalen Definition befindet sich in Abbildung~\ref{fig:venn} auch ein passendes Venn-Diagramm. Die jeweils eingefärbte Fläche kennzeichnet die resultierende Menge. $\mathcal{U}$ sei ein beliebiges aber festes Universum.
\begin{definition}\label{def:setops}
	Seien $A, B$ Mengen. 
	\begin{enumerate}[label=(\alph*)]
		\item Die \textit{Vereinigung} von $A$ und $B$ ist definiert als 
			$$ 
				A \cup B \coloneqq \{ a \in \mathcal{U} \mid a \in A \text{ oder } a \in B \}.
			$$
			Für endliche und unendliche Vereinigungen (z.B. gegeben durch eine Indexmenge $I = \{ 0, 1, \ldots \}$) schreiben wir abkürzend
			$$
				\bigcup_{i \in I} A_i = A_0 \cup A_1 \cup \ldots
			$$
		\item Der \textit{Schnitt} von $A$ und $B$ ist definiert als
			$$
				A \cap B \coloneqq \{ a \in A \mid a \in B \}.
			$$
			Für endlichen und unendlichen Schnitt (z.B. gegeben durch eine Indexmenge $I = \{ 0, 1, \ldots \}$) schreiben wir abkürzend
			$$
				\bigcap_{i \in I} A_i = A_0 \cap A_1 \cap \ldots
			$$
		\item Das \textit{Komplement} von $A$ is definiert als
			$$
				\comp{A} \coloneqq \{ a \in \mathcal{U} \mid a \notin A \}.
			$$
		\item Die \textit{Differenz} (auch: \textit{relatives Komplement}) von $A$ und $B$ ist definiert als
			$$
				A \setminus B \coloneqq A \cap \comp{B}.
			$$
		\item Das \textit{kartesische Produkt} zwischen $A$ und $B$ ist definiert als
			$$
				A \times B \coloneqq \{(a, b) : a \in A, b \in B \}.
			$$
			Für ein endliches Produkt einer Menge $A$ auf sich selbst schreiben wir abkürzend
			$$
				A^k \coloneqq A \times A^{k-1}, \quad\quad A^1 \coloneqq A, \quad\quad A^0 \coloneqq \{ \bullet \},
			$$
			wobei $\bullet$ ein beliebiges Platzhaltersymbol ist, d.h. $A^0$ ist für jedes $A$ ein Singleton.\\
			Die Elemente eines kartesischen Produkts $(x_1, \ldots, x_k)$ heißen $k$-\textit{Tupel}. Für $k = 2, 3, 4, \ldots$ kann man auch \textit{Paar, Tripel, Quadrupel, \ldots} sagen.
		\item Die \textit{Potenzmenge} von $A$ ist definiert als
			$$
				2^A \coloneqq \{ M \subseteq \mathcal{U} \mid M \subseteq A \}.
			$$
	\end{enumerate}
\end{definition}
\begin{figure}
	\centering
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_union}
		\caption{$A \cup B$}
		\label{fig:venn_union}
	\end{subfigure}
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_intersection}
		\caption{$A \cap B$}
		\label{fig:venn_intersection}
	\end{subfigure}\\
	\ \\
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_complement}
		\caption{$\comp{A}$}
		\label{fig:venn_complement}
	\end{subfigure}
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_setminus}
		\caption{$A \setminus B$}
		\label{fig:venn_setminus}
	\end{subfigure}
	\caption{Venn-Diagramme für Mengen-Operationen.}
	\label{fig:venn}
\end{figure}


\subsection{Relationen}\label{sec:pre_relations}
Relationen drücken Beziehungen oder Zusammenhänge zwischen Elementen aus. Im Allgemeinen können dies Beziehungen zwischen beliebig vielen Elementen sein und wir werden verschieden stellige Relationen auch im Laufe der Vorlesung benutzen. In diesem Abschnitt legen wir aber ein besonderes Augenmerk auf 2-stellige Relationen.
\begin{definition}
	Es seien $M_1, \ldots, M_k$ nicht-leere Mengen. Eine Teilmenge $R \subseteq M_1 \times \ldots \times M_k$ heißt \textit{Relation} zwischen $M_1, \ldots, M_k$ (oder auf $M$, falls $M = M_1 = \ldots = M_k$).
\end{definition}
Für 2-stellige Relationen verwenden wir oft Symbole wie $\sim, \prec$ und schreiben dann statt $(a, b) \in\, \sim$ intuitiver $a \sim b$.
\begin{definition}
	Sei $\sim \,\subseteq M \times M$ eine 2-stellige Relation. $\sim$ heißt
	\begin{itemize}
		\item \textit{reflexiv}, falls $x \sim x$ für alle $x \in M$,
		\item \textit{symmetrisch}, falls für alle $x, y \in M$ mit $x \sim y$ auch $y \sim x$ gilt,
		\item \textit{antisymmetrisch}, falls für alle $x, y \in M$ mit $x \sim y$ und $y \sim x$ gilt, dass $x = y$,
		\item \textit{transitiv}, falls für alle $x, y, z \in M$ mit $x \sim y$ und $y \sim z$ gilt, dass $x \sim z$.
	\end{itemize}
\end{definition}
Wir klassifizieren außerdem 2-stellige Relationen, falls sie bestimmte Eigenschaften haben.
\begin{definition}\label{def:relations}
	Sei $\sim \,\subseteq M \times M$ eine 2-stellige Relation. $\sim$ heißt
	\begin{itemize}
		\item \textit{Äquivalenzrelation}, falls sie reflexiv, symmetrisch und transitiv ist,
		\item \textit{(partielle) Ordnung}, falls sie reflexiv, antisymmetrisch und transitiv ist,
		\item \textit{Totalordnung}, falls sie partielle Ordnung ist und für alle $x, y \in M$ entweder $x \sim y$ oder $y \sim x$ gilt. 
	\end{itemize}	 
\end{definition}
\begin{example*}
	\
	\begin{enumerate}
		\item Die Relation $\leq$ ist auf $\mathbb{N}$ eine Totalordnung.
		\item Die Relation $\{(a, b) \in \mathbb{R}^2 \mid a^2 = b^2 \}$ ist eine Äquivalenzrelation auf $\mathbb{R}$.
	\end{enumerate}
\end{example*}

\begin{definition}\label{def:equivalenceclass}
	Sei $\sim$ eine Äquivalenzrelation auf einer Menge $M$. Für $x \in M$ heißt
	$$
		[x] \coloneqq [x]_\sim \coloneqq \{ y \in M \mid x \sim y \}
	$$
	die \textit{Äquivalenzklasse} von $x$. Die Menge aller Äquivalenzklassen von $\sim$ wird notiert mit $M /_\sim \coloneqq \{ [x]_\sim : x \in M \}$.
\end{definition}



\subsection{Gesetze für Mengen}\label{sec:pre_setlaws}
In diesem Abschnitt sammeln wir ein paar Gesetzmäßigkeiten, die für Mengen gelten. Manche davon sind offensichtlich, wir werden aber auch zu ein paar Aussagen die Beweise geben, manche bleiben als Übung.
\begin{remark*}
	Für die Inklusion gilt offensichtlich für jede Menge $M$
	$$
		\emptyset \subseteq M \subseteq M \subseteq \mathcal{U}.
	$$
	Insbesondere ist die Relation $\subseteq$ reflexiv. Sie ist außerdem transitiv und per Definition der Gleichheit von Mengen antisymmetrisch, also eine partielle Ordnung.\par
	Schnitt und Vereinigung sind per Definition offenbar \textit{assoziativ} (d.h. $A \cup (B \cup C) = (A \cup B) \cup C$ und $A \cap (B \cap C) = (A \cap B) \cap C$) und \textit{kommutativ} (d.h. $A \cup B = B \cup A$ und $A \cap B = B \cap A$). Außerdem sind diese beiden Operationen zueinander \textit{distributiv}, was wir im folgenden einmal zeigen wollen. 
\end{remark*}
Das Beweisschema für solche Aufgaben ist stets das selbe und sollte deshalb auch ruhig übernommen werden für Übungsaufgaben. Tricks sind selten notwendig, es ist meist
\begin{center}
	\textit{Definition anwenden -- triviale Umformung -- Definition anwenden -- Profit}.
\end{center}
\begin{remark*}
	Für Mengen $A, B, C$ gilt:
	\begin{enumerate}
		\item $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$,
		\item $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
	\end{enumerate}
	\begin{proof}
		Wir zeigen nur Aussage (i), die zweite Hälfte geht analog. Wir müssen zwei Richtungen beweisen.\\
		``$\subseteq$``: Sei $a \in A \cup (B \cap C)$. D.h. $a \in A$ oder $a \in B \cap C$.
		\begin{itemize}
			\item $a \in A$. Dann ist $a$ auch in $A \cup B$ und $A \cup C$ (da $\cup$ die Mengen nicht verkleinert). Also ist $a$ auch im Schnitt dieser beiden Mengen.
			\item $a \in B \cap C$. Dann ist $a \in B$ und $a \in C$. Also (da wie oben $\cup$ die Menge nicht verkleinert) ist $a \in A \cup B$ und $a \in A \cup C$. Somit ist $a$ auch wieder im Schnitt beider Mengen.
		\end{itemize}
		``$\supseteq$``: Sei $a \in (A \cup B) \cap (A \cup C)$. Dann ist $a \in A \cup B$ und $a \in A \cup C$ ($\ast$). Wir unterscheiden zwei Fälle:
		\begin{itemize}
			\item $a \in A$. Unabhängig von $B, C$ ist dann $a \in A \cup (B \cap C)$.
			\item $a \notin A$. Dann muss $a \in B$ und $a \in C$ gelten, sonst würde ($\ast$) nicht gelten. Somit ist $a \in B \cap C$ und damit auch wieder $a \in A \cup (B \cap C)$. 
		\end{itemize}
		Wir haben also $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ und $A \cup (B \cap C) \supseteq (A \cup B) \cap (A \cup C)$ gezeigt. Somit muss Gleichheit zwischen diesen beiden Mengen vorliegen.
	\end{proof}
\end{remark*}
Weiterhin nützlich sind noch folgende Bemerkungen.
\begin{remark*}[DeMorgan'sche Gesetze]
	Für Mengen $A, B$ gilt:
	\begin{itemize}
		\item $\comp{(A \cup B)} = \comp{A} \cap \comp{B}$,
		\item $\comp{(A \cap B)} = \comp{A} \cup \comp{B}$.
	\end{itemize}
\end{remark*}
\begin{remark*}[Absorptionsgesetz]
	Für Mengen $A, B$ gilt:
	\begin{itemize}
		\item $A \cup (A \cap B) = A$,
		\item $A \cap (A \cup B) = A$.
	\end{itemize}
\end{remark*}
Die Beweise hierfür bleiben als Übung.


\subsection{Funktionen}\label{sec:pre_mappings}
\begin{definition}
	Seien $M, N$ Mengen. Eine \textit{Funktion} (oder \textit{Abbildung)} $f$ von $M$ nach $N$ ist eine Vorschrift (z.B. eine Formel), die jedem $x \in M$ genau ein $f(x) \in N$ zuordnet. Wir schreiben dazu
	$$
		f\colon M \to N, \quad x \mapsto f(x).
	$$
	$M$ heißt der \textit{Definitionsbereich} (auch Domäne) von $f$, $N$ heißt der \textit{Wertebereich} von $f$. $f(x)$ ist das \textit{Bild} von $x$ unter $f$ und $x$ ist ein \textit{Urbild} von $f(x)$ unter $f$. Die Menge aller Funktionen von $M$ nach $N$ wird mit $N^M$ bezeichnet. Falls $M = A^n, N = A$ für ein nicht-leeres $A$ ist, sagen wir auch, dass $f$ eine \textit{$n$-stellige} Funktion über $A$ ist. Desweitere nennen wir eine $0$-stellige Funktion auch \textit{Konstante}.
\end{definition}
\begin{definition}
	Sei $f\colon M \to N$ eine Funktion.
	\begin{itemize}
		\item Für jede Teilmenge $X \subseteq M$ ist $f(X) \coloneqq \{ f(x) : x \in X \}$ das \textit{Bild von $X$ unter $f$}. Falls $X = M$ sprechen wir auch nur vom \textit{Bild} von $f$.
		\item Für jede Teilmenge $Y \subseteq N$ ist $f^{-1}(Y) \coloneqq \{ x \in M \mid f(x) \in Y \}$ das \textit{Urbild von $Y$ unter $f$}.
	\end{itemize}
\end{definition}
\begin{definition}
	Zu einer Menge $M$ ist $\id_M\colon M \to M, x \mapsto x$ die \textit{Identität}.
\end{definition}
\begin{definition}
	Eine Funktion $f\colon M \to N$ heißt
	\begin{itemize}
		\item \textit{surjektiv}, falls für alle $y \in N$ ein $x \in M$ mit $f(x) = y$ existiert,
		\item \textit{injektiv}, falls für alle $x, x^\prime \in M$ mit $x \neq x^\prime$ gilt, dass $f(x) \neq f(x^\prime)$,
		\item \textit{bijektiv}, falls $f$ surjektiv und injektiv ist.
	\end{itemize}
\end{definition}
\begin{example*}
	Die Addition zweier natürlicher Zahlen kann als Funktion aufgefasst werden:
	$$
		+\colon \mathbb{N}^2 \to \mathbb{N}, \quad (m, n) \mapsto m+n.
	$$
	$+$ ist surjektiv (jedes $y \in \mathbb{N}$ wird z.B. durch $(y, 0) \in \mathbb{N}^2$ getroffen), aber nicht injektiv ($1 \in \mathbb{N}$ wird sowohl von $(1, 0)$ als auch $(0, 1)$ getroffen).
\end{example*}
Für Funktionen $f\colon [k] \to M$ für beliebige $k \in \mathbb{N}$ in beliebige $M$ können wir auch abkürzend die Tupelschreibweise $(y_0, \ldots, y_{k-1})$ verwenden. Dann ist $y_i = f(i)$ für alle $i \in [k]$.\par
Wir fügen nun noch ein paar nützliche Definitionen an um dieses Skript in sich abgeschlossen zu halten.
\begin{definition}
	Sei $f\colon M \to N$ eine Funktion und $A \subseteq M$. Dann ist $f\vert_A\colon A \to N$ die \textit{Einschränkung von $f$ auf $A$} mit $f\vert_A(x) = f(x)$ für alle $x \in A$.
\end{definition}
\begin{definition}
	Wir schreiben für zwei Funktionen $f, g\colon M \to N$, dass sie \textit{identisch} sind ($f \equiv g$), wenn für alle $x \in M$ gilt, dass $f(x) = g(x)$.
\end{definition}
\begin{definition}
	Die \textit{Komposition} zweier Funktionen $f\colon M \to M^\prime, g\colon M^\prime \to N$ ist bezeichnet mit $g \circ f\colon M \to N, x \mapsto g(f(x))$.
\end{definition}
\begin{definition}
	Seien $f\colon M \to N, g\colon N \to M$ Funktionen. Dann heißt $g$ eine \textit{linksseitige (rechtseitige) Umkehrfunktion} von $f$, wenn $g \circ f \equiv id_M$ ($f \circ g \equiv id_N$). Wenn $g$ sowohl links- als auch rechtsseitige Umkehrfunktion ist sprechen wir schlicht von einer \textit{Umkehrfunktion} von $f$ und bezeichnen diese mit $f^{-1}$.
\end{definition}
\begin{remark*}
	Die Schreibweise $f^{-1}$ benutzen wir sowohl für das Urbild als auch für Umkehrabbildungen, was jedoch zwei verschiedene Begriffe sind!
\end{remark*}


\subsection{Strukturen}\label{sec:pre_structures}
Wir haben Mengen, Relationen und Abbildungen jeweils eigenständig kennengelernt. Tatsächlich benutzen wir sie allerdings nur zusammen. Beispielsweise sind die natürlichen Zahlen für sich allein nicht sehr interessant, wenn man auf ihnen nicht addieren könnte. Umgekehrt sind auch Funktionsvorschriften wertlos, wenn sie nicht auf Elemente einer Menge angewendet werden kann. Wir fassen alles nun unter dem Begriff einer \textit{Struktur} zusammen.
\begin{definition}
	Sei $\tau = \{ R_1, \ldots, R_m, f_1, \ldots, f_n \}$ eine Menge von Relationssymbolen und Funktionssymbolen, eine sogenannte \textit{Signatur}. Eine \textit{$\tau$-Struktur} ist ein Paar $\mathfrak{A} = (A, \mathfrak{a})$, wobei $A$ eine nicht-leere Menge ist, die \textit{Universum} (oder \textit{Träger}) heißt und $\mathfrak{a}$ ist eine Funktion, die jedem $k$-stelligem Relationssymbol $R \in \tau$ eine $k$-stellige Relation und jedem $k$-stelligem Funktionssymbol $f \in \tau$ eine $k$-stellige Funktion zuordnet.
\end{definition}
Statt $\mathfrak{a}(R), \mathfrak{a}(f)$ schreibt man auch häufig $R^\mathfrak{A}, f^\mathfrak{A}$. In der mathematischen Logik ist es wichtig eine Unterscheidung zwischen Relations- und Funktionssymbolen und ihren Interpretationen durch konkrete Relationen $R^\mathfrak{A}$ bzw. Funktionen $f^\mathfrak{A}$ zu machen. Deshalb sollten Schreibweisen wie $\mathfrak{N} = (\mathbb{N}, +)$ nur als Abkürzungen verstanden werden für $\mathfrak{N} = (\mathbb{N}, +^\mathfrak{N})$ mit $+^\mathfrak{N}\colon \mathbb{N}^2 \to \mathbb{N}, (m, n) \mapsto +^\mathfrak{N}(m, n) = m + n$, wobei wir mit $m + n$ den gewohnten $n$-ten Nachfolger von $m$ bezeichnen. Der Autor hofft, dass es klar ist worauf er hinaus wollte.\par
Wir können Strukturen wieder klassifizieren nach sogenannten \textit{Axiomen}, die sie erfüllen.
\begin{definition}
	Eine Struktur vom Typ $(A, \bullet)$ heißt \textit{Magma}. Ein Magma $(A, \bullet)$ heißt \textit{abelsch} (oder \textit{kommutativ)}, falls für alle $a, b \in A$ gilt: $a \bullet b = b \bullet a$. Es heißt \textit{assoziativ} (oder \textit{Halbgruppe}) falls für alle $a, b, c \in A$ gilt: $(a \bullet b) \bullet c = a \bullet (b \bullet c)$.
\end{definition}
\begin{definition}
	Sei $\mathfrak{A} = (A, \bullet)$ eine Struktur mit $\bullet\colon A \times A \to A$. Wir sagen $\mathfrak{A}$ ist ein \textit{Monoid}, wenn folgende Axiome gelten:
	\begin{enumerate}
		\item \textit{Assoziativität}, für alle $a, b, c \in A$ gilt $(x \bullet y) \bullet z = x \bullet (y \bullet z)$.
		\item \textit{neutrales Element}, es gibt ein $e \in A$, sodass für alle $a \in A$ gilt $a \bullet e = e \bullet a = a$.
	\end{enumerate}
	Gilt zusätzlich
	\begin{enumerate}\setcounter{enumi}{3}
		\item \textit{Kommutativität}, für alle $a, b \in A$ gilt $a \bullet b = b \bullet a$.
	\end{enumerate}
	so heißt das Monoid \textit{abelsch}.
\end{definition}
\begin{example}
	Sei $A$ eine beliebige nicht-leere Menge und $\mathbb{B} = \{ 0, 1 \}$.
	\begin{enumerate}
		\item $(\mathbb{N}, +)$ ist abelsches Monoid mit neutralem Element $0$,
		\item $(\mathbb{R}, \cdot)$ ist abelsches Monoid mit neutralem Element $1$,
		\item $(A^A, \circ)$ ist Monoid mit neutralem Element $\id_A$,
		\item $(\mathbb{B}, \wedge)$ ist abelsches Monoid mit neutralem Element $1$.
	\end{enumerate}
\end{example}
Es ist bei Monoiden auch üblich, dass das neutrale Element mit in die Struktur geschrieben wird also, z.B. $(\mathbb{R}, \cdot, 1)$.
\begin{definition}
	Sei $\mathfrak{A} = (A, \bullet)$ ein Monoid. Eine Teilmenge $E \subseteq A$ heißt \textit{Erzeugendensystem} von $\mathfrak{A}$ falls jedes $a \in A$ als $a = e_0 \bullet \ldots \bullet e_{n-1}$ mit $e_i \in E$ für alle $i \in [n]$ dargestellt werden kann. $E$ heißt \textit{frei}, falls diese Darstellung eindeutig ist. In diesem Fall nennen wir $\mathfrak{A}$ auch das von $E$ \textit{frei erzeugte Monoid} (oder unter Missbrauch der Notation auch \textit{freies Monoid}).
\end{definition}
\begin{remark*}
	Das neutrale Element wird stets durch eine \textit{leere} Anwendung dargestellt. Beispielsweise ist für $(\mathbb{N}, +)$ die Menge $\{1\}$ ein (freies) Erzeugendensystem, denn jede natürliche Zahl $n$ lässt sich als Summe von $n$ $1$en darstellen $n = \sum_{i=1}^n 1$, für $n = 0$ erhalten wir eben genau die leere Summe ohne Summanden.
\end{remark*}
\begin{definition}
	Sei $(A, \bullet, e)$ Monoid und $a \in A$.
	\begin{itemize}
		\item Gibt es ein $b \in A$ mit $a \bullet b = e$ so heißt $a$ \textit{rechtsinvertierbar}.
		\item Gibt es ein $b \in A$ mit $b \bullet a = e$ so heißt $a$ \textit{linksinvertierbar}.
		\item Ist $a$ rechts- und linksinvertierbar, dann heißt $a$ eine \textit{Einheit}.
		\item Gibt es ein $b \in A$ mit $b \bullet a = a \bullet b = e$ so heißt $a$ \textit{invertierbar} und $b$ \textit{invers} zu $a$. 
	\end{itemize}
	Die \textit{Menge aller Einheiten} von $A$ bezeichnen wir mit $A^\times$.
\end{definition}
Wir bezeichnen die Inversen zu Einheiten $a$ in der Regel mit $a^{-1}$ oder $-a$. 
\begin{definition}
	Sei $\mathfrak{A} = (A, \bullet, e)$ ein Monoid. Falls in $\mathfrak{A}$ zusätzlich
	\begin{enumerate}\setcounter{enumi}{2}
		\item \textit{Invertierbarkeit}, für alle $a \in A$ existiert $b \in A$ mit $a \bullet b = b \bullet a = e$, 
	\end{enumerate}
	dann ist $\mathfrak{A}$ eine \textit{Gruppe} (bzw. \textit{abelsche Gruppe}).
\end{definition}
\begin{lemma}
	Ist $(A, \bullet, e)$ Monoid, so ist $(A^\times, \bullet, e)$ Gruppe (Einheitengruppe).
	\begin{proof}
		Per Definition ist jedes Element in $A^\times$ eine Einheit. Außerdem ist $e$ stets eine Einheit, da es invers zu sich selbst ist. Es bleibt zu zeigen, dass $A^\times$ auch abgeschlossen ist unter der Operation $\bullet$. Sei dazu $a, b \in A^\times$ und $a^{-1}, b^{-1}$ die jeweiligen Inversen $(\ast)$. Wir zeigen das $a \bullet b$ Einheit ist mit Inversem $b^{-1} \bullet a^{-1}$:
		\[
			(a \bullet b) \bullet (b^{-1} \bullet a^{-1}) \overset{\text{(i)}}{=} a \bullet (b \bullet b^{-1}) \bullet a^{-1} \overset{(\ast)}{=} a \bullet e \bullet a^{-1} \overset{\text{(ii)}}{=} a \bullet a^{-1} \overset{(\ast)}{=} e. \qedhere
		\]
	\end{proof}
\end{lemma}
\begin{example}
	Sei $\mathbb{B} = \{ 0, 1 \}$. Das Symbol $\nleftrightarrow$ steht für das Boolsche exklusive Oder ($\xor$).
	\begin{enumerate}
		\item $(\mathbb{B}, \nleftrightarrow)$ ist abelsche Gruppe,
		\item $(\mathbb{R} \setminus \{ 0 \}, \cdot)$ ist abelsche Gruppe,
		\item $(\mathbb{Z}, -)$ ist Gruppe.
	\end{enumerate}
\end{example}
\begin{definition}
	Sei $\mathfrak{A} = (A, \bullet)$ eine Gruppe und $B \subseteq A$ nicht-leer. $\mathfrak{B} = (B, \bullet)$ ist eine \textit{Untergruppe} von $\mathfrak{A}$, wenn für alle $a, b \in B$ auch $a \bullet b^{-1} \in B$ gilt.
\end{definition}
Natürlich ist es auch möglich eine solche Klassifizierung von Strukturen mit mehr als einer Funktion vorzunehmen.
\begin{definition}
	Eine Struktur $(A, \oplus, \odot)$ heißt \textit{Ring}, falls gilt
	\begin{enumerate}
		\item $(A, \oplus)$ ist abelsche Gruppe,
		\item $(A, \odot)$ ist Halbgruppe,
		\item \textit{Distributivität}, für alle $a, b, c \in A$ gilt $a \odot (b \oplus c) = a \odot b \oplus a \odot c$ und $(a \oplus b) \odot c = a \odot c \oplus b \odot c$.
	\end{enumerate}
	Das neutrale Element von $(A, \oplus)$ heißt \textit{Nullelement} des Rings. Der Ring heißt \textit{kommutativ}, falls er bzgl. $\odot$ kommutativ ist, ansonsten \textit{nicht-kommutativ}. Ist $(A, \odot)$ Monoid, so heißt der Ring \textit{unitär}. Das neutrale Element von $(A, \odot)$ heißt dann \textit{Einselement}. Ist $(A, \oplus)$ nur eine abelsche Halbgruppe, so heißt $(A, \oplus, \odot)$ \textit{Halbring}. Ist $( A, \oplus)$ Halbgruppe, aber $(A, \odot)$ Gruppe, so heißt $(A, \oplus, \odot)$ \textit{Halbkörper}.
\end{definition}
\begin{definition}
	Eine Struktur $(A, \oplus, \odot)$ heißt \textit{Körper}, wenn gilt
	\begin{enumerate}
		\item $(A, \oplus)$ ist abelsche Gruppe,
		\item $(A \setminus \{0\}, \odot)$ ist abelsche Gruppe (mit $0$ neutralem Element bzgl. $\oplus$),
		\item Distributivität ist erfüllt.
	\end{enumerate}
	Ist $(A \setminus \{0\}, \odot)$ nur Gruppe (ohne Kommutativität), so ist $(A, \oplus, \odot)$ \textit{Schiefkörper}.
\end{definition}
\begin{remark*}
	Jeder Körper ist ein kommutativer Ring und auch ein Schiefkörper. Jeder Schiefkörper ist ein Ring.
\end{remark*}


\subsection{Graphen}\label{sec:pre_graphs}
Eine weitere wichtige Klasse von Strukturen sind Graphen. Dise werden häufig genutzt um Operatoren wie Funktionen und Relationen zu visualisieren, allerdings untersucht man Graphen auch selbst als mathematische Objekte.
\begin{definition}
	Ein \textit{Graph} ist eine Struktur $G = (V, E)$ mit \textit{Knotenmenge} $V$ und \textit{Kantenmenge} (oder Multimenge) $E \subseteq V \times V$.
\end{definition}
\begin{definition}
	Sei $G = (V, E)$ ein Graph, $v, w \in V$ und $e = (v, w) \in E$.
	\begin{itemize}
		\item $v, w$ heißen \textit{adjazent} (oder \textit{benachbart}) durch $e$.
		\item $e$ heißt \textit{Schleife} (oder \textit{Loop}), falls $v = w$.
		\item Zwei Kanten $e, e^\prime$ heißen \textit{parallel}, falls $e = e^\prime$.
		\item Ein Graph heißt \textit{einfach}, falls er keine parallelen Kanten enthält.
		\item Ein Graph heißt \textit{ungerichtet}, falls $(v, w) \in E$ impliziert, dass $(w, v) \in E$, ansonsten \textit{gerichtet}. 
	\end{itemize}
\end{definition}
\begin{definition}
	Sei $G = (V, E)$ ein Graph und $v \in V$. Der \textit{Knotengrad} von $v$ ist definiert durch
	$$
		\deg(v) = \left| \{ e \in E \,\vert\, e = (v, w), w \neq v \} \right|.
	$$
\end{definition}
\begin{definition}
	Ein Graph $G = (V, E)$ heißt $k$-\textit{regulär}, falls für alle $v \in V$ gilt $\deg(v) = k$.
	$G$ heißt \textit{vollständig}, falls für alle Knotenpaare $v \neq w \in V$ gilt: $(v, w) \in E$. Mit $K_n$ bezeichnen wir den vollständigen Graphen mit $n$ Knoten.
	$G$ heißt \textit{bipartit}, falls sich $V$ als disjunkte Vereinigung aus $U, W$ darstellen lässt, sodass für alle $(u, v) \in E$ entweder $u \in U, v \in W$ oder $u \in W, v \in U$ gilt. Er heißt \textit{vollständig bipartit}, wenn zudem gilt, dass $E = \{ (u, w) \mid u \in U, w \in W \}$. Wir schreiben $K_{p,q}$ mit $p = \left| U \right|$ und $q = \left| W \right|$ für den vollständig bipartiten Graphen mit Knotenmenge $V = U \cup W, U \cap W = \emptyset$.
\end{definition}
\begin{remark*}
	Den Graphen $S_n = K_{1,n-1}$ nennt man auch \textit{Stern}.
\end{remark*}
\begin{definition}
	Sei $G = (V, E)$ ein Graph. Ein \textit{Teilgraph} von $G$ ist ein Graph $G^\prime = (V^\prime, E^\prime)$, wenn gilt $V^\prime \subseteq V$ und $E^\prime \subseteq E$. Ein \textit{induzierter Teilgraph} von $G$ ist ein ein Graph $G^\prime = (V^\prime, E^\prime)$, wenn gilt $V^\prime \subseteq V$ und $E^\prime = E \cap V^\prime \times V^\prime$. Wir schreiben für den durch $V^\prime$ induzierten Teilgraphen von $G$ auch $G[V^\prime]$.
\end{definition}
%TODO Pfade, Kreise, Cliquen, Zusammenhang


\subsection{Beweismethoden}\label{sec:pre_proofs}
%TODO Deduktion, Induktion, Widerspruchsbeweis, Kontraposition
\begin{theorem}\label{thm:primes}
	Es gibt unendlich viele Primzahlen.
	\begin{proof}
		TODO %TODO
	\end{proof}
\end{theorem}



\newpage
\section{Alphabete, Wörter, Sprachen}\label{sec:awl}
Das erste Kapitel hat uns mit den nötigen mathematischen Grundlagen versorgt, die wir als Modellierungswerkzeuge in der theoretischen Informatik verwenden wollen. Wir definieren dazu später abstrakte Rechenmodelle, sogenannte Automaten, um das Verhalten von konkreten Rechenmodellen (z.B. Computern) formal zu erfassen. Zunächst sehen wir uns an, wie wir ganz allgemein diese konkreten Rechenmodelle funktionieren und wie sich diese Funktionsweisen möglichst knapp und allgemein (d.h. abstrakt, ``vereinfacht auf das wesentliche``) darstellen lassen. Nach diesem Kapitel haben wir das Hauptthema der Vorlesung, die \textit{abstrakte Automatentheorie}, vorbereitet.

\subsection{Grundlegende Definitionen}\label{sec:awl_def}
Wir fassen Aktionen eines Computers (oder eines Getränkeautomaten, \ldots) in unserer Abstrakion als \textit{Symbole} (Buchstaben) auf, im Rahmen dieser Vorlesung sind das immer nur endlich viele, d.h. das \textit{Alphabet} ist endlich. Aktionsfolgen (z.B. vom Einwurf einer Münze bis zur Ausgabe des Getränkes) entsprechen somit einem \textit{Wort}. Die Menge aller gültigen Aktionsfolgen (solche, die für das betrachtete System ``sinnvoll`` sind) bezeichnen wir dann als \textit{Sprache des Automaten}.
\begin{definition}
	Ein \textit{Alphabet} ist eine nicht-leere endliche Menge, deren Elemente als \textit{Symbole} bezeichnet sind.
\end{definition}
Alphabete werden durch griechische Großbuchstaben $\Sigma, \Gamma$ oder Variationen wie $\Sigma_1, \Gamma^\prime$ bezeichnet. Symbole werden durch kleine lateinische Buchstaben $a, b, c, \ldots$ oder arabische Ziffern $0, 1, \ldots$ bezeichnet.
\begin{example}
	\
	\begin{enumerate}
		\item Das \textit{Boole'sche Alphabet} $\{ 0, 1 \}$.
		\item Das \textit{Morsealphabet} $\{ \cdot, -, \,\,\, \}$.
		\item Das \textit{ASCII-Alphabet} für zum Beispiel Textdateien.
	\end{enumerate}
\end{example}

\begin{definition}
	Ein \textit{Wort} über einem Alphabet $\Sigma$ ist eine Abbildung
	$$
		w\colon [n] \to \Sigma.
	$$
	Für $n = 0$ ist $w\colon \emptyset \to \Sigma$ das \textit{leere Wort}, was wir als $\varepsilon$ bezeichnen.\\
	Die \textit{Länge} des Wortes $w$ ist bezeichnet mit $\left| w \right| = n$.\\
	$\left| w \right|_a \coloneqq \left| \{ i \in [n] \mid w(i) = a \} \right|$ ist die \textit{Häufigkeit des Symbols} $a$ im Wort $w$.
\end{definition}
Wie in Abschnitt~\ref{sec:pre_mappings} lässt sich $w$ auch als Tupel $(a_0, \ldots, a_{n-1})$ schreiben. Wir gehen hier sogar noch einen Schritt weiter und benutzen $a_0 a_1 \ldots a_{n-1}$ als Abkürzung für die langen Schreibweisen. Für Wörter verwenden wir in der Regel $u, v, w$ und Varianten als Bezeichner. In der Literatur sind auch kleine griechische Buchstaben $\alpha, \beta, \ldots$ gebräuchlich.
\begin{definition}
	Sei $\Sigma$ ein Alphabet. Dann ist $\Sigma^n \coloneqq \Sigma^{[n]}$ die \textit{Menge aller Wörter mit Länge} $n$ über $\Sigma$.
	Die \textit{Menge aller Wörter} ist definiert als
	$$
		\Sigma^\ast \coloneqq \bigcup_{n \in \mathbb{N}} \Sigma^n
	$$
	und $\Sigma^+ \coloneqq \Sigma^\ast \setminus \{ \varepsilon \}$.
\end{definition}
Wie in Abschnitt~\ref{sec:pre_setops} angekündigt wird für ein fixiertes $\Sigma$ die Menge $\Sigma^\ast$ unser Universum sein.
\begin{definition}
	Eine \textit{(formale) Sprache} über einem Alphabet $\Sigma$ ist eine Teilmenge von $\Sigma^\ast$.
\end{definition}
Sprachen bezeichnen wir in der Regel mit $L, K, \ldots$ und Varianten.
\begin{example}
	\
	\begin{itemize}
		\item Die leere Sprache $\emptyset$.
		\item Die Sprache, die nur das leere Wort enthält $\{ \varepsilon \}$.
		\item Die Sprache aller Binärdarstellungen von Primzahlen $\{ \bin(n) : n \in \mathbb{P} \}$.
		\item Die Menge aller grammatikalisch korrekten deutschen Sätze.
	\end{itemize}
\end{example}


\subsection{Operationen und Relationen auf Wörtern und Sprachen}\label{sec:awl_wordops}
Durch diese vorgegangen Definitionen haben wir das Fundament für die theoretische Informatik bereits definiert. Da dies nur mithilfe von Funktionen und Mengen  passiert ist lassen sich Beweismethoden und Ergebnisse aus der Mathematik einfach übertragen. Wir definieren nun noch ein paar Operationen auf Wörtern und erweitern diese Definitionen auf Sprachen.
\begin{definition}
	Seien $u, v \in \Sigma^\ast$ mit $m = \left| u \right|, n = \left| v \right|$. Die \textit{Konkatenation} (Verkettung) ist definiert als
	\begin{align*}
		(u \cdot v)&\colon [m{+}n] \to \Sigma \text{ mit}\\
		(u \cdot v)(i) &= \left\lbrace \begin{array}{ll}u(i), & i < m\\ v(i-m), & i \geq m. \end{array} \right.
	\end{align*}
	Außerdem ist $u^0 \coloneqq \varepsilon$ und $u^n \coloneqq u \cdot u^{n-1}$.
\end{definition}
Aus Bequemlichkeitsgründen wird der Punkt auch weggelassen. Für Sprachen erhalten wir noch die Definitionen.
\begin{definition}
	Seien $L, K \subseteq \Sigma^\ast$ Sprachen.
	\begin{enumerate}
		\item \textit{Konkatenation.} $L \cdot K \coloneqq \{ uv : u \in L, v \in K \}$ und $L^0 \coloneqq \{ \varepsilon \}, L^n \coloneqq L \cdot L^{n-1}$.
		\item \textit{Inklusion.} Wie in Definition~\ref{def:subsets}.
		\item \textit{Vereinigung, Schnitt, Komplement, Differenz.} Wie in Definiton~\ref{def:setops}.
		\item \textit{Kleene'scher Abschluss.} (auch \textit{Iteration}, \textit{Kleene-Stern})
			$$
				L^\ast \coloneqq \bigcup_{n \in \mathbb{N}} L^n.
			$$
	\end{enumerate}
\end{definition}
\begin{definition}
	Seien $u, v$ Wörter. Dann ist $u$
	\begin{itemize}
		\item \textit{Präfix} von $v$ (geschrieben: $u \sqsubseteq v$), falls es ein Wort $w$ gibt mit $v = uw$,
		\item \textit{Infix} von $v$, falls es Wörter $w, w^\prime$ gibt mit $v = wuw^\prime$,
		\item \textit{Suffix} von $v$, falls es ein Wort $w$ gibt mit $v = wu$.
	\end{itemize}
\end{definition}
\begin{example}
	Sei $v = aaba$.
	\begin{itemize}
		\item Die Präfixe von $v$ sind $\varepsilon, a, aa, aab, aaba$.
		\item Die Suffixe von $v$ sind $\varepsilon, a, ba, aba, aaba$.
		\item Die Infixe von $v$ sind alle Präfixe und Suffixe, sowie $ab, b$.
	\end{itemize}
\end{example}


\subsection{Gesetze für Wörter und Sprachen}\label{sec:awl_wordlaws}
In diesem Abschnitt wollen wir einige Gesetzmäßigkeiten, die bei der Anwendung von Operationen auf Wörtern und Sprachen gelten, herausarbeiten. Einige Eigenschaften übertragen sich sofort aus denen für Mengen aus Abschnitt~\ref{sec:pre_setlaws}. Bei anderen ist etwas mehr zu zeigen und bei wieder anderen gibt es vielleicht auch zunächst unintuitive Unterschiede.
\begin{remark*}
	Für das leere Wort $\varepsilon$ gilt:
	\begin{enumerate}
		\item Es ist für jedes Wort sowohl Präfix, Infix als auch Suffix.
		\item Es ist das \textit{neutrale Element} der Konkatenation, d.h. für alle $w \in \Sigma^\ast$ gilt $\varepsilon w = w = w \varepsilon$.
		\item Daran anknüpfend gilt für jede Sprache $L$, dass $ \{ \varepsilon \} L = L = L  \{ \varepsilon \}$.
		\item Für jede Menge $A$ (inklusive dem Fall $A = \emptyset$) ist $A^0 = \{ \varepsilon \}$.
		\item $\varepsilon$ ist eindeutig, d.h. es gibt kein zweites Wort mit diesen Eigenschaften.
		\item Weil es häufig durcheinander gebracht wird: $\{ \varepsilon \} \neq \emptyset$.
	\end{enumerate}
\end{remark*}

\begin{remark*}
	Für Vereinigung, Schnitt, Differenz, \ldots von Sprachen gelten die selben Regeln (Assoziativ-, Kommutativ-, Distributivgesetze, deMorgan, Absorption, \ldots) wie für Mengen.
\end{remark*}

\begin{remark*}
	Für jede Sprache $L$ gilt, dass $\emptyset L = L \emptyset = \emptyset$.
	\begin{proof}
		Wir zeigen, dass $L \emptyset$ leer ist. Der andere Fall geht analog. Angenommen es existiert ein $w \in L \emptyset$. Dann lässt sich $w$ zerlegen in $w = uv$ mit $u \in L, v \in \emptyset$. Da ein solches $v$ nicht existieren kann (leere Menge), kann auch die gesamte Zerlegung und somit auch $w$ nicht existieren. Also ist $L \emptyset$ leer.
	\end{proof}
\end{remark*}



\newpage
\section{Endliche Automaten und Reguläre Sprachen}\label{sec:regular}
Wir haben formale Sprachen eingeführt als Modellierung für Prozessabläufe auf z.B. Computern. Diese Ansicht werden wir zunächst aber beiseite legen und erst in Kapitel~\ref{sec:process} wieder aufgreifen. In der Zwischenzeit untersuchen wir Sprachen auf verschiedene Eigenschaften und klassifizieren unter anderem nach der sogenannten \textit{Chomsky-Hierarchie}. Wir prüfen, wie sich Sprachen von formalen Systemen (Automaten, abstrakte Rechenmodelle) erkennen lassen. Diese Systeme wirken manchmal etwas künstlich, sind aber sehr sinnvoll, da sie sich mit den uns zu Verfügungen Werkzeugen aus der Mathematik gut handhaben lassen. Die daraus entstehenden Resultate haben außerdem auch einen nicht zu vernachlässigenden ästhetischen Wert für die theoretische Informatik. Zugegeben, der Praxisbezug offenbart sich bei einigen Sätzen nicht sofort und ist vielleicht auch gar nicht überalll vorhanden. Dennoch sollte der Wert dieser Ergebnisse auch nicht unterschätzt werden, denn wir liefern hier auch die Grundlagen zur Untersuchung, was sich prinzipiell mit Computern überhaupt berechnen lässt und die Erkenntnis, dass es Probleme in der Informatik gibt, die von einem Computer mehr Funktionalität beansprucht als andere Probleme (und vielleicht sogar mehr als ein Computer prinzipiell haben kann), sollte Motivation genug sein, sich mit theoretischer Informatik auseinanderzusetzen.

\subsection{Deterministische Endliche Automaten}\label{sec:regular_dfa}
Wir beginnen mit der Art Automaten, die ``die einfachste`` Klasse formaler Sprachen erkennen kann.
\begin{definition}
	Ein \textit{deterministischer endlicher Automat (DFA)} (von engl.: deterministic finite automaton) ist ein 5-Tupel
	$$
		(Q, \Sigma, \delta, q_0, F),
	$$
	mit
	\begin{itemize}
		\item $Q$ eine nicht-leere, endliche Menge von \textit{Zuständen},
		\item $\Sigma$ ein nicht-leeres, endliches \textit{Eingabealphabet},
		\item $\delta\colon Q \times \Sigma \to Q$ die \textit{Transitionsfunktion},
		\item $q_0 \in Q$ der \textit{Startzustand},
		\item $F \subseteq Q$ die Menge der \textit{akzeptierenden Zustände} (oder \textit{Endzustände}).
	\end{itemize}
\end{definition}
DFAs lassen sich auch problemlos als Strukturen wie in Abschnitt~\ref{sec:pre_structures} auffassen. Aus Gründen der Lesbarkeit verzichten wir jedoch darauf. Wir bezeichnen DFAs stets mit $\mathcal{A}, \mathcal{B}, \ldots$, Zustände mit $p, q, r, s$ und Variationen.\\
Es lassen sich auch durchaus noch einfacherere Rechenmodelle definieren (z.B. durch Restriktionen gegenüber der Größe der Zustandsmenge), dies ist jedoch vorerst nicht sinnvoll. Auf die bereits angesprochene Chomsky-Hierarchie werden wir noch genauer eingehen, aber auch dort sind die Sprachen, die durch DFAs erkannt werden können, als die einfachste Klasse bezeichnet.\\
Möchte man einen DFA konkret angeben, so ist die Darstellung als Transitionsgraph sinnvoller, als die Angabe des 5-Tupels.
\begin{definition}
	Sei $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ ein DFA. Der \textit{Transitionsgraph} von $\mathcal{A}$ ein beschrifteter Graph $G_\mathcal{A} = ((Q, E), \lambda, q_0, F)$ mit
	$$
		E = \{ (p, q) \mid \text{es ex. } a \in \Sigma \text{ mit } \delta(p, a) = q \}
	$$
	und
	$$
		\lambda\colon E \to 2^\Sigma, \quad (p, q) \mapsto \{ a \mid \delta(p, a) = q \}.
	$$
\end{definition}
Aus Gründen der Bequemlichkeit, lassen wir die Mengenklammern bei der Beschriftung der Transitionen weg. Der Startzustand $q_0$ bekommt einfach eine eingehende Kante ohne Beschriftung und ohne Startknoten. Die Endzustände werden zusätzlich eingekreist. Ein Beispieltransitionsgraph ist in Abbildung~\ref{fig:dfa_ex1}.
\begin{figure}
	\centering
	\input{figs/dfa_ex1}
	\caption{DFA für die Sprache aus Beispiel~\ref{exp:ex1}.}
	\label{fig:dfa_ex1}
\end{figure}
Wir werden die Begriffe Automat und Transitionsgraph gelegentlich synonym verwenden, da sich sowohl im Graphen als auch in der ursprünglichen Automatenstruktur alle Informationen befinden. Wir greifen dann auf den Begriff zurück, der für das aktuelle Thema die bequemere Anschauung hat.\\
Wir schauen uns nun das Verhalten eines DFA auf einem Wort an.
\begin{definition}
	Sei $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ ein DFA.
	Ein \textit{Lauf} von $\mathcal{A}$ auf einem Wort $w = a_0 \ldots a_{n-1}$ für ein $n \in \mathbb{N}$ ist eine endliche Folge
	$$
		(r_0, a_0, r_1, a_1, \ldots, a_{n-1}, r_n),
	$$
	wobei $r_0, \ldots, r_n \in Q$ und $a_0, \ldots, a_{n-1} \in \Sigma$, sodass
	\begin{enumerate}
		\item $r_0 = q_0$,
		\item $\delta(r_i, a_i) = r_{i+1}$ für $i \in [n]$.
	\end{enumerate}
	Wir sagen ein Lauf ist \textit{akzeptierend}, wenn zusätzlich $r_n \in F$ gilt.
\end{definition}
Wir bezeichnen Läufe in der Regel mit $\varrho$ bzw. Variationen. Einen Lauf $(r_0, a_0, r_1, a_1, \ldots, a_{n-1}, r_n)$ kürzen wir gelegentlich durch $(r_0, r_1, \ldots, r_n)$ ab, wenn die Symbole nicht relevant für unsere Betrachtungen sind.
\begin{remark*}
	Zu jedem Wort $w \in \Sigma^\ast$ existiert genau ein Lauf von $\mathcal{A}$ auf $w$.
\end{remark*}
\begin{definition}
\
	\begin{enumerate}
		\item Ein DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ \textit{akzeptiert} ein Wort $w \in \Sigma^\ast$, wenn der Lauf von $\mathcal{A}$ akzeptierend ist. Andernfalls \textit{verwirft} $\mathcal{A}$ das Wort $w$.
		\item Die von einem DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ \textit{erkannte Sprache} ist
			$$
				L(\mathcal{A}) \coloneqq \{ w \in \Sigma^\ast \mid \mathcal{A} \text{ akzeptiert } w \}.
			$$
		\item Eine Sprache $L$ heißt \textit{DFA-erkennbar}, wenn es einen DFA $\mathcal{A}$ gibt, sodass $L = L(\mathcal{A})$.
	\end{enumerate}
\end{definition}
\begin{example}\label{exp:ex1}
	Betrachte erneut den Automaten $\mathcal{A}$ in Abbildung~\ref{fig:dfa_ex1}.
	\begin{itemize}
		\item Sei $w_1 = abaaba$. Der Lauf von $\mathcal{A}$ auf $w_1$ ist
			$$
				\varrho_1 = (q_0, q_1, q_2, q_1, q_1, q_2, q_1).
			$$
			D.h. $\mathcal{A}$ akzeptiert $w_1$.
		\item Sei $w_2 = baa$. Der Lauf von $\mathcal{A}$ auf $w_2$ ist
			$$
				\varrho_2 = (q_0, q_3, q_3, q_3).
			$$
			D.h. $\mathcal{A}$ verwirft $w_2$.
		\item $\mathcal{A}$ erkennt die Sprache 
			$$
				L = \{ w \in \{a, b\}^\ast \mid w \text{ beginnt und endet mit } a \}.
			$$
	\end{itemize}
	Die letzte Aussage sagt etwas über das Verhalten des Automaten auf allen, d.h. unendlich vielen, Wörtern aus. Man kann also nicht für jedes Wort einzeln zeigen, dass sich der Automat korrekt verhält. Stattdessen beweisen wir die Aussage per Induktion.
	\begin{proof}
		Wir zeigen die folgende Aussage:
		\begin{center}
			$\mathcal{A}$ akzeptiert das Wort $w$ {g.d.w.} $w$ beginnt und endet mit $a$.				\end{center}
		Beweis per vollständige Induktion über Wortlänge $n \in \mathbb{N}$. Ist $r = (r_0, \ldots, r_n)$ der Lauf auf dem Wort $w = a_0 \ldots a_{n-1}$, so ist
		$$
			r_n = \left\lbrace 
					\begin{array}{ll}
						q_0, & w = \varepsilon\\
						q_1, & a_0 = a_{n-1} = a\\
						q_2, & a_0 = a \text{ und } a_{n-1} = b\\
						q_3, & a_0 = b.
					\end{array}
				\right.
		$$
		Wir wollen also zeigen, dass ein Lauf von $\mathcal{A}$ auf einem Wort dann und nur dann in $q_1$, dem einzigen akzeptierendem Zustand, endet, wenn $w$ mit $a$ beginnt und endet.\\
		Induktionsverankerung: $n = 0$. Dann ist $w = \varepsilon$ und der Lauf von $\mathcal{A}$ auf $w$ ist $r = (q_0)$, also auch $r_n = r_0 = q_0$.\checkmark\\
		Induktionshypothese (IH): Für $w = a_0 \ldots a_{n-1}$ sei $r = (r_0, \ldots, r_n)$ der Lauf auf $\mathcal{A}$ mit $r_n$ wie in der Behauptung.\\
		Induktionsschritt: Betrachte nun das Wort $w = a_0 \ldots a_n$.
		\begin{itemize}
			\item $a_0 \ldots a_{n-1} = \varepsilon$. Dann ist nach IH $r_n = q_0$ und somit
				$$
					r_{n+1} = \delta(r_n, a_n) = \left\lbrace
							\begin{array}{ll}
								q_1, & a_n = a\\
								q_3, & a_n = b.
							\end{array}
						\right.
				$$
			\item $a_0 = a_{n-1} = a$. Dann ist nach IH $r_n = q_1$ und somit
				$$
					r_{n+1} = \delta(r_n, a_n) = \left\lbrace
							\begin{array}{ll}
								q_1, & a_n = a\\
								q_2, & a_n = b.
							\end{array}
						\right.
				$$
			\item $a_0 = a$ und $a_{n-1} = b$. Dann ist nach IH $r_n = q_2$ und somit
				$$
					r_{n+1} = \delta(r_n, a_n) = \left\lbrace
							\begin{array}{ll}
								q_1, & a_n = a\\
								q_2, & a_n = b.
							\end{array}
						\right.
				$$
			\item $a_0 = b$. Dann ist nach IH $r_n = q_3$ und somit
				$$
					r_{n+1} = \delta(r_n, a_n) = q_3
				$$
				unabhängig von $a_n$.
		\end{itemize}
		Insgesamt gilt also: 
		\begin{align*}
			% if you think this is ugly, I agree.
			w \text{ beginnt und endet mit } a. &\text{ g.d.w. } \text{Ist } r = (r_0, \ldots, r_n) \text{ der Lauf von }\\ &\quad\quad\quad\,\, \mathcal{A} \text{ auf } w \text{ so gilt } r_n = q_1 \in F.\\
			&\text{ g.d.w. } \mathcal{A} \text{ akzeptiert } w.\\
			&\text{ g.d.w. } L(\mathcal{A}) = L.
		\end{align*}
	\end{proof}
\end{example}
So ausführlich wie hier werden wir später nicht mehr beweisen, dass ein gegebener Automat ``das richtige tut``, sollte dies nicht klar sein werden wir die Funktionsweise nur grob erläutern. Ausführliche Beweise sind im Wesentlichen dann gefordert, wenn man zum Beispiel zeigen möchte, dass eine Sprache nicht DFA-erkennbar ist.


\subsection{Abschlusseigenschaften DFA-erkennbarer Sprachen}\label{sec:regular_closure}
Bei einer Einteilung aller möglichen Sprachen in Klassen will man in einer möglichst sinnvollen Weise vorgehen. Damit meint man u.a., dass die einzelnen Klassen in sich abgeschlossen sind bzgl. verschiedener Operationen oder auch andere Eigenschaften haben, die in einer wissenschaftlichen Weise ``schön`` sind. Die folgenden Abschnitte sind dazu da um zu zeigen, dass DFA-erkennbare Sprachen dies in vielerlei Hinsicht erfüllen. In diesem Abschnitt beginnen wir damit zu zeigen, dass DFA-erkennbare Sprachen unter den üblichen Mengenoperationen (Komplementbildung, Vereinigung und Schnitt) abgeschlossen sind. Im späteren Verlauf werden wir noch einige andere Operationen betrachten.\par
Wir zeigen als erstes, dass die DFA-erkennbaren Sprachen unter Komplementbildung abgeschlossen sind.
\begin{theorem}\label{thm:regular_complement}
	Sei $L \subseteq \Sigma^\ast$ eine DFA-erkennbare Sprache. Dann ist auch $\comp{L}$ DFA-erkennbar.
	\begin{proof}
		Sei $L \subseteq \Sigma^\ast$ eine beliebige DFA-erkennbare Sprache. D.h. es existiert ein DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$, der $L$ erkennt. Wir konstruieren aus $\mathcal{A}$ den DFA
		$$