fosap.tex 136 KB
Newer Older
Niklas Rieken's avatar
Niklas Rieken committed
1
\documentclass[11pt, a4paper]{article}
2
\usepackage[left=3cm, right=3cm]{geometry}
Niklas Rieken's avatar
Niklas Rieken committed
3
4
5
6
7
8
9
10

% packages
\usepackage{natbib}
\usepackage[utf8]{inputenc}
\usepackage[german]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
Niklas Rieken's avatar
Niklas Rieken committed
11
12
\usepackage{bm}
\usepackage{stmaryrd}
Niklas Rieken's avatar
Niklas Rieken committed
13
14
15
16
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{mathrsfs}
\usepackage{mathdots}
Niklas Rieken's avatar
Niklas Rieken committed
17
\usepackage{mathtools}
Niklas Rieken's avatar
Niklas Rieken committed
18
\usepackage{listings}
Niklas Rieken's avatar
Niklas Rieken committed
19
\usepackage[linesnumbered, ruled, vlined, ngerman]{algorithm2e}
Niklas Rieken's avatar
Niklas Rieken committed
20
21
22
\usepackage{enumitem}
\usepackage{wrapfig}
\usepackage{float}
23
\usepackage{array}
Niklas Rieken's avatar
Niklas Rieken committed
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
\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})}
49
50
51
52
53
54
\makeatletter
\newcommand*{\shifttext}[2]{
	\settowidth{\@tempdima}{#2}
	\makebox[\@tempdima]{\hspace*{#1}#2}
}
\makeatother
Niklas Rieken's avatar
Niklas Rieken committed
55
56
57
58
\def\Rho{\mathrm{P}}

\newenvironment{problem}[1]{\begin{tabular}{|p{.96\textwidth}|} \hline \textsc{#1}\\}{\\ \hline \end{tabular}}
\newcommand{\comp}[1]{\overline{#1}}
59
60
\newcommand{\qedw}{\hfill$\square$}
\newcommand{\qedb}{\hfill$\blacksquare$}
61
\newcommand{\shuffle}{\mathrel{\shifttext{5pt}{$\equiv$}\shifttext{-5pt}{$=$}}}
Niklas Rieken's avatar
Niklas Rieken committed
62
\newcommand{\reaches}[1]{\overset{#1}{\rightarrow}}
Niklas Rieken's avatar
Niklas Rieken committed
63
\newcommand{\reachess}[2]{\overset{#1}{\underset{#2}{\rightarrow}}}
64
\DeclareMathOperator{\id}{id}
65
66
\DeclareMathOperator{\bin}{bin}
\DeclareMathOperator{\xor}{xor}
Niklas Rieken's avatar
Niklas Rieken committed
67
\let\emptyset\varnothing
Niklas Rieken's avatar
Niklas Rieken committed
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

\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:\\
86
    		\today\\[2em]
Niklas Rieken's avatar
Niklas Rieken committed
87
88
89
		Autor:\\
		Niklas Rieken\\
	\end{Large}
90
91
92
93
94
	\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.
Niklas Rieken's avatar
Niklas Rieken committed
95
96
97
98
99
100
101
\end{center}


\newpage
% acknowledgements
\vspace*{\fill}
\section*{Hinweise}
102
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.
Niklas Rieken's avatar
Niklas Rieken committed
103
104
105
106
107
108
109
110
111
112
113
\vspace*{\fill}


\newpage
% table of contents
\tableofcontents


\newpage
\pagestyle{headings}
\section{Mathematisches Vorwissen}\label{sec:pre}
Niklas Rieken's avatar
Niklas Rieken committed
114
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.
Niklas Rieken's avatar
Niklas Rieken committed
115
116
117
118
119


\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}
120
	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.
Niklas Rieken's avatar
Niklas Rieken committed
121
122
123
124
\end{quote}

Wir definieren eine Menge wie folgt
\begin{definition}
125
	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$).
Niklas Rieken's avatar
Niklas Rieken committed
126
127
128
\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}
129
130
131
	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.
Niklas Rieken's avatar
Niklas Rieken committed
132
133
134
\end{definition}
Wir kommen nun zum Mächtigkeitsbegriff der Mengenlehre, der für die Anzahl der Elemente einer Menge beschreibt.
\begin{definition}
135
	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$.
Niklas Rieken's avatar
Niklas Rieken committed
136
137
138
\end{definition}
Um eine konkrete Menge zu zu benennen gibt es im Wesentlichen vier verschiedene Möglichkeiten:
\begin{enumerate}
139
140
	\item \textit{Aufzählen.} Die Elemente der Menge werden aufgelistet und in Mengenklammern ($\{, \}$) eingeschlossen. Reihenfolge und Wiederholungen spielen keine Rolle.
		$$
Niklas Rieken's avatar
Niklas Rieken committed
141
			\{ 3, 4.5, \pi, \diamondsuit \} = \{ \pi, 4.5, \diamondsuit, \diamondsuit, 3 \} \subseteq \{ \diamondsuit, \pi, 4.5, 3, \clubsuit \}. 
142
		$$
Niklas Rieken's avatar
Niklas Rieken committed
143
	\item \textit{Beschreiben.} Mengen können durch Worte beschrieben werden.
144
		$$
Niklas Rieken's avatar
Niklas Rieken committed
145
			\text{Menge der natürlichen Zahlen} = \{ 0, 1, 2, 3, \ldots \} \eqqcolon \mathbb{N}.
146
		$$
Niklas Rieken's avatar
Niklas Rieken committed
147
		Aber Achtung: Natürliche Sprache neigt zu Uneindeutigkeit!
148
149
	\item \textit{Aussondern.} Sei $M$ eine Menge, dann ist
		$$
150
			\{ x \in M \mid \varphi(x) \}
151
152
153
		$$
		die Menge aller Elemente aus $M$, die die Eigenschaft $\varphi$ erfüllen. Zum Beispiel:
		$$
Niklas Rieken's avatar
Niklas Rieken committed
154
			\mathbb{P} \coloneqq \{ n \in \mathbb{N} \mid n \text{ hat genau zwei Teiler} \}
155
		$$
Niklas Rieken's avatar
Niklas Rieken committed
156
		als Menge aller Primzahlen.
157
158
	\item \textit{Abbilden.} Sei $M$ eine Menge und $f$ ein Ausdruck, der für jedes $x \in M$ definiert ist. Dann ist
		$$
Niklas Rieken's avatar
Niklas Rieken committed
159
			\{ f(x) : x \in M \}
160
161
162
		$$
		die Menge aller Ausdrücke $f(x)$, wobei jedes $x \in M$ in $f$ eingesetzt wird. Zum Beispiel:
		$$
Niklas Rieken's avatar
Niklas Rieken committed
163
			\{ n^2 : n \in \mathbb{N} \}
164
		$$
Niklas Rieken's avatar
Niklas Rieken committed
165
166
167
		als Menge aller Quadtratzahlen.
\end{enumerate}
Wir können Abbilden und Aussondern auch kombinieren, zum Beispiel mit:
168
$$
169
	\{ n^2 : n \in \mathbb{N} \mid n \text{ ungerade} \}
170
$$
Niklas Rieken's avatar
Niklas Rieken committed
171
als Menge aller Quadratzahlen von ungeraden natürlichen Zahlen. Man würde hier jedoch abkürzend schreiben:
172
$$
Niklas Rieken's avatar
Niklas Rieken committed
173
	\{ n^2 : n \in \mathbb{N} \text{ ungerade} \}
174
$$
Niklas Rieken's avatar
Niklas Rieken committed
175
oder auch
176
$$
Niklas Rieken's avatar
Niklas Rieken committed
177
	\{ n^2 : n \in 2\mathbb{N}+1 \}.
178
179
$$
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}.
Niklas Rieken's avatar
Niklas Rieken committed
180
\begin{remark*}
181
	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\}$.
Niklas Rieken's avatar
Niklas Rieken committed
182
\end{remark*}
Niklas Rieken's avatar
Niklas Rieken committed
183
184
185


\subsection{Operationen auf Mengen}\label{sec:pre_setops}
186
187
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.
Niklas Rieken's avatar
Niklas Rieken committed
188
189
190
\begin{figure}
	\centering
	\input{figs/venn_subset}
191
	\caption{Venn-Diagramm für $A \subseteq B$.}
Niklas Rieken's avatar
Niklas Rieken committed
192
193
	\label{fig:venn_subset}
\end{figure}
194
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.
Niklas Rieken's avatar
Niklas Rieken committed
195
\begin{definition}\label{def:setops}
196
	Seien $A, B$ Mengen. 
Niklas Rieken's avatar
Niklas Rieken committed
197
	\begin{enumerate}[label=(\alph*)]
198
199
		\item Die \textit{Vereinigung} von $A$ und $B$ ist definiert als 
			$$ 
Niklas Rieken's avatar
Niklas Rieken committed
200
				A \cup B \coloneqq \{ a \in \mathcal{U} \mid a \in A \text{ oder } a \in B \}.
201
202
203
			$$
			Für endliche und unendliche Vereinigungen (z.B. gegeben durch eine Indexmenge $I = \{ 0, 1, \ldots \}$) schreiben wir abkürzend
			$$
Niklas Rieken's avatar
Niklas Rieken committed
204
				\bigcup_{i \in I} A_i = A_0 \cup A_1 \cup \ldots
205
206
207
			$$
		\item Der \textit{Schnitt} von $A$ und $B$ ist definiert als
			$$
Niklas Rieken's avatar
Niklas Rieken committed
208
				A \cap B \coloneqq \{ a \in A \mid a \in B \}.
209
210
211
			$$
			Für endlichen und unendlichen Schnitt (z.B. gegeben durch eine Indexmenge $I = \{ 0, 1, \ldots \}$) schreiben wir abkürzend
			$$
Niklas Rieken's avatar
Niklas Rieken committed
212
				\bigcap_{i \in I} A_i = A_0 \cap A_1 \cap \ldots
213
214
215
			$$
		\item Das \textit{Komplement} von $A$ is definiert als
			$$
Niklas Rieken's avatar
Niklas Rieken committed
216
				\comp{A} \coloneqq \{ a \in \mathcal{U} \mid a \notin A \}.
217
218
219
			$$
		\item Die \textit{Differenz} (auch: \textit{relatives Komplement}) von $A$ und $B$ ist definiert als
			$$
Niklas Rieken's avatar
Niklas Rieken committed
220
				A \setminus B \coloneqq A \cap \comp{B}.
221
222
223
			$$
		\item Das \textit{kartesische Produkt} zwischen $A$ und $B$ ist definiert als
			$$
Niklas Rieken's avatar
Niklas Rieken committed
224
				A \times B \coloneqq \{(a, b) : a \in A, b \in B \}.
225
226
227
			$$
			Für ein endliches Produkt einer Menge $A$ auf sich selbst schreiben wir abkürzend
			$$
Niklas Rieken's avatar
Niklas Rieken committed
228
				A^k \coloneqq A \times A^{k-1}, \quad\quad A^1 \coloneqq A, \quad\quad A^0 \coloneqq \{ \bullet \},
229
230
231
232
233
			$$
			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
			$$
Niklas Rieken's avatar
Niklas Rieken committed
234
				2^A \coloneqq \{ M \subseteq \mathcal{U} \mid M \subseteq A \}.
235
			$$
Niklas Rieken's avatar
Niklas Rieken committed
236
237
238
239
240
241
242
	\end{enumerate}
\end{definition}
\begin{figure}
	\centering
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_union}
243
		\caption{$A \cup B$}
Niklas Rieken's avatar
Niklas Rieken committed
244
245
246
247
248
		\label{fig:venn_union}
	\end{subfigure}
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_intersection}
249
		\caption{$A \cap B$}
Niklas Rieken's avatar
Niklas Rieken committed
250
251
252
253
254
255
		\label{fig:venn_intersection}
	\end{subfigure}\\
	\ \\
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_complement}
256
		\caption{$\comp{A}$}
Niklas Rieken's avatar
Niklas Rieken committed
257
258
259
260
261
		\label{fig:venn_complement}
	\end{subfigure}
	\begin{subfigure}[b]{.49\textwidth}
		\centering
		\input{figs/venn_setminus}
262
		\caption{$A \setminus B$}
Niklas Rieken's avatar
Niklas Rieken committed
263
264
265
266
267
268
269
270
271
272
		\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}
273
	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$).
Niklas Rieken's avatar
Niklas Rieken committed
274
\end{definition}
275
Für 2-stellige Relationen verwenden wir oft Symbole wie $\sim, \prec$ und schreiben dann statt $(a, b) \in\, \sim$ intuitiver $a \sim b$.
Niklas Rieken's avatar
Niklas Rieken committed
276
\begin{definition}
277
	Sei $\sim \,\subseteq M \times M$ eine 2-stellige Relation. $\sim$ heißt
Niklas Rieken's avatar
Niklas Rieken committed
278
	\begin{itemize}
279
280
281
282
		\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$.
Niklas Rieken's avatar
Niklas Rieken committed
283
284
285
	\end{itemize}
\end{definition}
Wir klassifizieren außerdem 2-stellige Relationen, falls sie bestimmte Eigenschaften haben.
286
\begin{definition}\label{def:relations}
287
	Sei $\sim \,\subseteq M \times M$ eine 2-stellige Relation. $\sim$ heißt
Niklas Rieken's avatar
Niklas Rieken committed
288
289
290
	\begin{itemize}
		\item \textit{Äquivalenzrelation}, falls sie reflexiv, symmetrisch und transitiv ist,
		\item \textit{(partielle) Ordnung}, falls sie reflexiv, antisymmetrisch und transitiv ist,
291
		\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. 
Niklas Rieken's avatar
Niklas Rieken committed
292
293
294
295
296
	\end{itemize}	 
\end{definition}
\begin{example*}
	\
	\begin{enumerate}
297
298
		\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}$.
Niklas Rieken's avatar
Niklas Rieken committed
299
300
301
	\end{enumerate}
\end{example*}

302
\begin{definition}\label{def:equivalenceclass}
303
304
	Sei $\sim$ eine Äquivalenzrelation auf einer Menge $M$. Für $x \in M$ heißt
	$$
Niklas Rieken's avatar
Niklas Rieken committed
305
		[x] \coloneqq [x]_\sim \coloneqq \{ y \in M \mid x \sim y \}
306
307
	$$
	die \textit{Äquivalenzklasse} von $x$. Die Menge aller Äquivalenzklassen von $\sim$ wird notiert mit $M /_\sim \coloneqq \{ [x]_\sim : x \in M \}$.
Niklas Rieken's avatar
Niklas Rieken committed
308
309
310
311
312
313
314
\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*}
315
316
	Für die Inklusion gilt offensichtlich für jede Menge $M$
	$$
Niklas Rieken's avatar
Niklas Rieken committed
317
		\emptyset \subseteq M \subseteq M \subseteq \mathcal{U}.
318
319
320
	$$
	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. 
Niklas Rieken's avatar
Niklas Rieken committed
321
322
323
324
325
326
\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*}
327
	Für Mengen $A, B, C$ gilt:
Niklas Rieken's avatar
Niklas Rieken committed
328
	\begin{enumerate}
329
330
		\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)$.
Niklas Rieken's avatar
Niklas Rieken committed
331
332
333
	\end{enumerate}
	\begin{proof}
		Wir zeigen nur Aussage (i), die zweite Hälfte geht analog. Wir müssen zwei Richtungen beweisen.\\
334
		``$\subseteq$``: Sei $a \in A \cup (B \cap C)$. D.h. $a \in A$ oder $a \in B \cap C$.
Niklas Rieken's avatar
Niklas Rieken committed
335
		\begin{itemize}
336
337
			\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.
Niklas Rieken's avatar
Niklas Rieken committed
338
		\end{itemize}
339
		``$\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:
Niklas Rieken's avatar
Niklas Rieken committed
340
		\begin{itemize}
341
342
			\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)$. 
Niklas Rieken's avatar
Niklas Rieken committed
343
		\end{itemize}
344
		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.
Niklas Rieken's avatar
Niklas Rieken committed
345
346
347
348
	\end{proof}
\end{remark*}
Weiterhin nützlich sind noch folgende Bemerkungen.
\begin{remark*}[DeMorgan'sche Gesetze]
349
	Für Mengen $A, B$ gilt:
Niklas Rieken's avatar
Niklas Rieken committed
350
	\begin{itemize}
351
352
		\item $\comp{(A \cup B)} = \comp{A} \cap \comp{B}$,
		\item $\comp{(A \cap B)} = \comp{A} \cup \comp{B}$.
Niklas Rieken's avatar
Niklas Rieken committed
353
354
355
	\end{itemize}
\end{remark*}
\begin{remark*}[Absorptionsgesetz]
356
	Für Mengen $A, B$ gilt:
Niklas Rieken's avatar
Niklas Rieken committed
357
	\begin{itemize}
358
359
		\item $A \cup (A \cap B) = A$,
		\item $A \cap (A \cup B) = A$.
Niklas Rieken's avatar
Niklas Rieken committed
360
361
362
363
364
	\end{itemize}
\end{remark*}
Die Beweise hierfür bleiben als Übung.


365
\subsection{Funktionen}\label{sec:pre_mappings}
Niklas Rieken's avatar
Niklas Rieken committed
366
\begin{definition}
367
368
	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
	$$
Niklas Rieken's avatar
Niklas Rieken committed
369
		f\colon M \to N, \quad x \mapsto f(x).
370
371
	$$
	$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}.
Niklas Rieken's avatar
Niklas Rieken committed
372
373
\end{definition}
\begin{definition}
374
	Sei $f\colon M \to N$ eine Funktion.
375
	\begin{itemize}
376
377
		\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$}.
378
379
380
	\end{itemize}
\end{definition}
\begin{definition}
381
	Zu einer Menge $M$ ist $\id_M\colon M \to M, x \mapsto x$ die \textit{Identität}.
382
383
\end{definition}
\begin{definition}
384
	Eine Funktion $f\colon M \to N$ heißt
Niklas Rieken's avatar
Niklas Rieken committed
385
	\begin{itemize}
386
387
388
		\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.
Niklas Rieken's avatar
Niklas Rieken committed
389
390
391
	\end{itemize}
\end{definition}
\begin{example*}
392
	Die Addition zweier natürlicher Zahlen kann als Funktion aufgefasst werden:
393
	$$
Niklas Rieken's avatar
Niklas Rieken committed
394
		+\colon \mathbb{N}^2 \to \mathbb{N}, \quad (m, n) \mapsto m+n.
395
396
	$$
	$+$ 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).
Niklas Rieken's avatar
Niklas Rieken committed
397
\end{example*}
398
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
399
Wir fügen nun noch ein paar nützliche Definitionen an um dieses Skript in sich abgeschlossen zu halten.
Niklas Rieken's avatar
Niklas Rieken committed
400
\begin{definition}
401
	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$.
Niklas Rieken's avatar
Niklas Rieken committed
402
\end{definition}
403
\begin{definition}
404
	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)$.
405
406
\end{definition}
\begin{definition}
407
	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))$.
408
409
\end{definition}
\begin{definition}
410
	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}$.
411
412
\end{definition}
\begin{remark*}
413
	Die Schreibweise $f^{-1}$ benutzen wir sowohl für das Urbild als auch für Umkehrabbildungen, was jedoch zwei verschiedene Begriffe sind!
414
\end{remark*}
Niklas Rieken's avatar
Niklas Rieken committed
415
416


417
\subsection{Strukturen}\label{sec:pre_structures}
418
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.
419
\begin{definition}
420
	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.
421
\end{definition}
422
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
423
Wir können Strukturen wieder klassifizieren nach sogenannten \textit{Axiomen}, die sie erfüllen.
Niklas Rieken's avatar
Niklas Rieken committed
424
\begin{definition}
425
	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)$.
Niklas Rieken's avatar
Niklas Rieken committed
426
\end{definition}
427
\begin{definition}
428
	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:
429
	\begin{enumerate}
430
431
		\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$.
432
433
434
	\end{enumerate}
	Gilt zusätzlich
	\begin{enumerate}\setcounter{enumi}{3}
435
		\item \textit{Kommutativität}, für alle $a, b \in A$ gilt $a \bullet b = b \bullet a$.
436
437
438
439
	\end{enumerate}
	so heißt das Monoid \textit{abelsch}.
\end{definition}
\begin{example}
440
	Sei $A$ eine beliebige nicht-leere Menge und $\mathbb{B} = \{ 0, 1 \}$.
441
	\begin{enumerate}
442
443
444
445
		\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$.
446
447
	\end{enumerate}
\end{example}
448
Es ist bei Monoiden auch üblich, dass das neutrale Element mit in die Struktur geschrieben wird also, z.B. $(\mathbb{R}, \cdot, 1)$.
449
\begin{definition}
450
	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}).
451
452
\end{definition}
\begin{remark*}
453
	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.
454
\end{remark*}
455
\begin{definition}
456
	Sei $(A, \bullet, e)$ Monoid und $a \in A$.
457
	\begin{itemize}
458
459
460
461
		\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$. 
462
	\end{itemize}
463
	Die \textit{Menge aller Einheiten} von $A$ bezeichnen wir mit $A^\times$.
464
\end{definition}
465
Wir bezeichnen die Inversen zu Einheiten $a$ in der Regel mit $a^{-1}$ oder $-a$. 
466
\begin{definition}
467
	Sei $\mathfrak{A} = (A, \bullet, e)$ ein Monoid. Falls in $\mathfrak{A}$ zusätzlich
468
	\begin{enumerate}\setcounter{enumi}{2}
469
		\item \textit{Invertierbarkeit}, für alle $a \in A$ existiert $b \in A$ mit $a \bullet b = b \bullet a = e$, 
470
	\end{enumerate}
471
	dann ist $\mathfrak{A}$ eine \textit{Gruppe} (bzw. \textit{abelsche Gruppe}).
472
473
\end{definition}
\begin{lemma}
474
	Ist $(A, \bullet, e)$ Monoid, so ist $(A^\times, \bullet, e)$ Gruppe (Einheitengruppe).
475
	\begin{proof}
476
		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}$:
477
		\[
478
			(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
479
480
481
482
		\]
	\end{proof}
\end{lemma}
\begin{example}
483
	Sei $\mathbb{B} = \{ 0, 1 \}$. Das Symbol $\nleftrightarrow$ steht für das Boolsche exklusive Oder ($\xor$).
484
	\begin{enumerate}
485
486
487
		\item $(\mathbb{B}, \nleftrightarrow)$ ist abelsche Gruppe,
		\item $(\mathbb{R} \setminus \{ 0 \}, \cdot)$ ist abelsche Gruppe,
		\item $(\mathbb{Z}, -)$ ist Gruppe.
488
489
490
	\end{enumerate}
\end{example}
\begin{definition}
491
	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.
492
\end{definition}
Niklas Rieken's avatar
Niklas Rieken committed
493
494
Natürlich ist es auch möglich eine solche Klassifizierung von Strukturen mit mehr als einer Funktion vorzunehmen.
\begin{definition}
495
	Eine Struktur $(A, \oplus, \odot)$ heißt \textit{Ring}, falls gilt
Niklas Rieken's avatar
Niklas Rieken committed
496
	\begin{enumerate}
497
498
499
		\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$.
Niklas Rieken's avatar
Niklas Rieken committed
500
	\end{enumerate}
501
	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}.
Niklas Rieken's avatar
Niklas Rieken committed
502
503
\end{definition}
\begin{definition}
504
	Eine Struktur $(A, \oplus, \odot)$ heißt \textit{Körper}, wenn gilt
Niklas Rieken's avatar
Niklas Rieken committed
505
	\begin{enumerate}
506
507
		\item $(A, \oplus)$ ist abelsche Gruppe,
		\item $(A \setminus \{0\}, \odot)$ ist abelsche Gruppe (mit $0$ neutralem Element bzgl. $\oplus$),
Niklas Rieken's avatar
Niklas Rieken committed
508
509
		\item Distributivität ist erfüllt.
	\end{enumerate}
510
	Ist $(A \setminus \{0\}, \odot)$ nur Gruppe (ohne Kommutativität), so ist $(A, \oplus, \odot)$ \textit{Schiefkörper}.
Niklas Rieken's avatar
Niklas Rieken committed
511
512
513
514
\end{definition}
\begin{remark*}
	Jeder Körper ist ein kommutativer Ring und auch ein Schiefkörper. Jeder Schiefkörper ist ein Ring.
\end{remark*}
515

516
517

\subsection{Graphen}\label{sec:pre_graphs}
Niklas Rieken's avatar
Niklas Rieken committed
518
519
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}
520
	Ein \textit{Graph} ist eine Struktur $G = (V, E)$ mit \textit{Knotenmenge} $V$ und \textit{Kantenmenge} (oder Multimenge) $E \subseteq V \times V$.
Niklas Rieken's avatar
Niklas Rieken committed
521
522
\end{definition}
\begin{definition}
523
	Sei $G = (V, E)$ ein Graph, $v, w \in V$ und $e = (v, w) \in E$.
Niklas Rieken's avatar
Niklas Rieken committed
524
	\begin{itemize}
525
526
527
		\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$.
Niklas Rieken's avatar
Niklas Rieken committed
528
		\item Ein Graph heißt \textit{einfach}, falls er keine parallelen Kanten enthält.
529
		\item Ein Graph heißt \textit{ungerichtet}, falls $(v, w) \in E$ impliziert, dass $(w, v) \in E$, ansonsten \textit{gerichtet}. 
Niklas Rieken's avatar
Niklas Rieken committed
530
531
532
	\end{itemize}
\end{definition}
\begin{definition}
533
534
	Sei $G = (V, E)$ ein Graph und $v \in V$. Der \textit{Knotengrad} von $v$ ist definiert durch
	$$
Niklas Rieken's avatar
Niklas Rieken committed
535
		\deg(v) = \left| \{ e \in E \,\vert\, e = (v, w), w \neq v \} \right|.
536
	$$
Niklas Rieken's avatar
Niklas Rieken committed
537
538
\end{definition}
\begin{definition}
539
540
541
	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$.
Niklas Rieken's avatar
Niklas Rieken committed
542
543
\end{definition}
\begin{remark*}
544
	Den Graphen $S_n = K_{1,n-1}$ nennt man auch \textit{Stern}.
Niklas Rieken's avatar
Niklas Rieken committed
545
546
\end{remark*}
\begin{definition}
547
	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]$.
Niklas Rieken's avatar
Niklas Rieken committed
548
549
\end{definition}
%TODO Pfade, Kreise, Cliquen, Zusammenhang
550

551

552
\subsection{Beweismethoden}\label{sec:pre_proofs}
Niklas Rieken's avatar
Niklas Rieken committed
553
%TODO Deduktion, Induktion, Widerspruchsbeweis, Kontraposition
554
555
556
557
558
559
\begin{theorem}\label{thm:primes}
	Es gibt unendlich viele Primzahlen.
	\begin{proof}
		TODO %TODO
	\end{proof}
\end{theorem}
Niklas Rieken's avatar
Niklas Rieken committed
560
561
562
563
564
565
566
567
568
569
570
571



\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}
572
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.
Niklas Rieken's avatar
Niklas Rieken committed
573
574
575
\begin{example}
	\
	\begin{enumerate}
576
577
		\item Das \textit{Boole'sche Alphabet} $\{ 0, 1 \}$.
		\item Das \textit{Morsealphabet} $\{ \cdot, -, \,\,\, \}$.
Niklas Rieken's avatar
Niklas Rieken committed
578
579
580
581
582
		\item Das \textit{ASCII-Alphabet} für zum Beispiel Textdateien.
	\end{enumerate}
\end{example}

\begin{definition}
583
584
	Ein \textit{Wort} über einem Alphabet $\Sigma$ ist eine Abbildung
	$$
Niklas Rieken's avatar
Niklas Rieken committed
585
		w\colon [n] \to \Sigma.
586
587
588
589
	$$
	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$.
Niklas Rieken's avatar
Niklas Rieken committed
590
\end{definition}
591
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.
Niklas Rieken's avatar
Niklas Rieken committed
592
\begin{definition}
593
	Sei $\Sigma$ ein Alphabet. Dann ist $\Sigma^n \coloneqq \Sigma^{[n]}$ die \textit{Menge aller Wörter mit Länge} $n$ über $\Sigma$.
Niklas Rieken's avatar
Niklas Rieken committed
594
	Die \textit{Menge aller Wörter} ist definiert als
595
	$$
Niklas Rieken's avatar
Niklas Rieken committed
596
		\Sigma^\ast \coloneqq \bigcup_{n \in \mathbb{N}} \Sigma^n
597
598
	$$
	und $\Sigma^+ \coloneqq \Sigma^\ast \setminus \{ \varepsilon \}$.
Niklas Rieken's avatar
Niklas Rieken committed
599
\end{definition}
600
Wie in Abschnitt~\ref{sec:pre_setops} angekündigt wird für ein fixiertes $\Sigma$ die Menge $\Sigma^\ast$ unser Universum sein.
Niklas Rieken's avatar
Niklas Rieken committed
601
\begin{definition}
602
	Eine \textit{(formale) Sprache} über einem Alphabet $\Sigma$ ist eine Teilmenge von $\Sigma^\ast$.
Niklas Rieken's avatar
Niklas Rieken committed
603
\end{definition}
604
Sprachen bezeichnen wir in der Regel mit $L, K, \ldots$ und Varianten.
Niklas Rieken's avatar
Niklas Rieken committed
605
606
607
\begin{example}
	\
	\begin{itemize}
608
609
610
		\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} \}$.
Niklas Rieken's avatar
Niklas Rieken committed
611
612
613
614
615
		\item Die Menge aller grammatikalisch korrekten deutschen Sätze.
	\end{itemize}
\end{example}


616
\subsection{Operationen und Relationen auf Wörtern und Sprachen}\label{sec:awl_wordops}
Niklas Rieken's avatar
Niklas Rieken committed
617
618
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}
619
	Seien $u, v \in \Sigma^\ast$ mit $m = \left| u \right|, n = \left| v \right|$. Die \textit{Konkatenation} (Verkettung) ist definiert als
Niklas Rieken's avatar
Niklas Rieken committed
620
	\begin{align*}
Niklas Rieken's avatar
Niklas Rieken committed
621
		(u \cdot v)&\colon [m{+}n] \to \Sigma \text{ mit}\\
Niklas Rieken's avatar
Niklas Rieken committed
622
623
		(u \cdot v)(i) &= \left\lbrace \begin{array}{ll}u(i), & i < m\\ v(i-m), & i \geq m. \end{array} \right.
	\end{align*}
624
	Außerdem ist $u^0 \coloneqq \varepsilon$ und $u^n \coloneqq u \cdot u^{n-1}$.
Niklas Rieken's avatar
Niklas Rieken committed
625
626
627
\end{definition}
Aus Bequemlichkeitsgründen wird der Punkt auch weggelassen. Für Sprachen erhalten wir noch die Definitionen.
\begin{definition}
628
	Seien $L, K \subseteq \Sigma^\ast$ Sprachen.
Niklas Rieken's avatar
Niklas Rieken committed
629
	\begin{enumerate}
630
		\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}$.
Niklas Rieken's avatar
Niklas Rieken committed
631
632
		\item \textit{Inklusion.} Wie in Definition~\ref{def:subsets}.
		\item \textit{Vereinigung, Schnitt, Komplement, Differenz.} Wie in Definiton~\ref{def:setops}.
633
		\item \textit{Kleene'scher Abschluss.} (auch \textit{Iteration}, \textit{Kleene-Stern})
634
			$$
Niklas Rieken's avatar
Niklas Rieken committed
635
				L^\ast \coloneqq \bigcup_{n \in \mathbb{N}} L^n.
636
			$$
Niklas Rieken's avatar
Niklas Rieken committed
637
638
639
	\end{enumerate}
\end{definition}
\begin{definition}
640
	Seien $u, v$ Wörter. Dann ist $u$
Niklas Rieken's avatar
Niklas Rieken committed
641
	\begin{itemize}
642
643
644
		\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$.
Niklas Rieken's avatar
Niklas Rieken committed
645
646
647
	\end{itemize}
\end{definition}
\begin{example}
648
	Sei $v = aaba$.
Niklas Rieken's avatar
Niklas Rieken committed
649
	\begin{itemize}
650
651
652
		\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$.
Niklas Rieken's avatar
Niklas Rieken committed
653
654
655
656
	\end{itemize}
\end{example}


657
\subsection{Gesetze für Wörter und Sprachen}\label{sec:awl_wordlaws}
Niklas Rieken's avatar
Niklas Rieken committed
658
659
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*}
660
	Für das leere Wort $\varepsilon$ gilt:
Niklas Rieken's avatar
Niklas Rieken committed
661
662
	\begin{enumerate}
		\item Es ist für jedes Wort sowohl Präfix, Infix als auch Suffix.
663
664
665
666
667
		\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$.
Niklas Rieken's avatar
Niklas Rieken committed
668
669
670
671
	\end{enumerate}
\end{remark*}

\begin{remark*}
672
	Für Vereinigung, Schnitt, Differenz, \ldots von Sprachen gelten die selben Regeln (Assoziativ-, Kommutativ-, Distributivgesetze, deMorgan, Absorption, \ldots) wie für Mengen.
Niklas Rieken's avatar
Niklas Rieken committed
673
674
675
\end{remark*}

\begin{remark*}
676
	Für jede Sprache $L$ gilt, dass $\emptyset L = L \emptyset = \emptyset$.
Niklas Rieken's avatar
Niklas Rieken committed
677
	\begin{proof}
678
		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.
Niklas Rieken's avatar
Niklas Rieken committed
679
680
681
682
	\end{proof}
\end{remark*}


683
684
685
686
687
688
689
690

\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}
Niklas Rieken's avatar
Niklas Rieken committed
691
	Ein \textit{deterministischer endlicher Automat (DFA)} (von engl.: deterministic finite automaton) ist ein 5-Tupel
692
	$$
693
		(Q, \Sigma, \delta, q_0, F),
694
	$$
695
696
	mit
	\begin{itemize}
697
698
699
700
701
		\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}).
702
703
	\end{itemize}
\end{definition}
704
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.\\
705
706
707
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}
708
709
	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
	$$
710
		E = \{ (p, q) \mid \text{es ex. } a \in \Sigma \text{ mit } \delta(p, a) = q \}
711
	$$
712
	und
713
	$$
Niklas Rieken's avatar
Niklas Rieken committed
714
		\lambda\colon E \to 2^\Sigma, \quad (p, q) \mapsto \{ a \mid \delta(p, a) = q \}.
715
	$$
716
\end{definition}
717
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}.
718
719
720
721
722
723
724
725
726
\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}
727
728
729
	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
	$$
730
		(r_0, a_0, r_1, a_1, \ldots, a_{n-1}, r_n),
731
732
	$$
	wobei $r_0, \ldots, r_n \in Q$ und $a_0, \ldots, a_{n-1} \in \Sigma$, sodass
733
	\begin{enumerate}
734
735
		\item $r_0 = q_0$,
		\item $\delta(r_i, a_i) = r_{i+1}$ für $i \in [n]$.
736
	\end{enumerate}
737
	Wir sagen ein Lauf ist \textit{akzeptierend}, wenn zusätzlich $r_n \in F$ gilt.
738
\end{definition}
739
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.
740
\begin{remark*}
741
	Zu jedem Wort $w \in \Sigma^\ast$ existiert genau ein Lauf von $\mathcal{A}$ auf $w$.
742
743
744
745
\end{remark*}
\begin{definition}
\
	\begin{enumerate}
746
747
748
		\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
			$$
Niklas Rieken's avatar
Niklas Rieken committed
749
				L(\mathcal{A}) \coloneqq \{ w \in \Sigma^\ast \mid \mathcal{A} \text{ akzeptiert } w \}.
750
751
			$$
		\item Eine Sprache $L$ heißt \textit{DFA-erkennbar}, wenn es einen DFA $\mathcal{A}$ gibt, sodass $L = L(\mathcal{A})$.
752
753
754
	\end{enumerate}
\end{definition}
\begin{example}\label{exp:ex1}
755
	Betrachte erneut den Automaten $\mathcal{A}$ in Abbildung~\ref{fig:dfa_ex1}.
756
	\begin{itemize}
757
758
		\item Sei $w_1 = abaaba$. Der Lauf von $\mathcal{A}$ auf $w_1$ ist
			$$
759
				\varrho_1 = (q_0, q_1, q_2, q_1, q_1, q_2, q_1).
760
761
762
763
			$$
			D.h. $\mathcal{A}$ akzeptiert $w_1$.
		\item Sei $w_2 = baa$. Der Lauf von $\mathcal{A}$ auf $w_2$ ist
			$$
764
				\varrho_2 = (q_0, q_3, q_3, q_3).
765
766
767
768
			$$
			D.h. $\mathcal{A}$ verwirft $w_2$.
		\item $\mathcal{A}$ erkennt die Sprache 
			$$
769
				L = \{ w \in \{a, b\}^\ast \mid w \text{ beginnt und endet mit } a \}.
770
			$$
771
772
773
774
775
	\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}
776
777
778
			$\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
		$$
779
780
781
782
783
784
785
786
			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.
787
788
789
790
791
		$$
		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$.
792
		\begin{itemize}
793
794
			\item $a_0 \ldots a_{n-1} = \varepsilon$. Dann ist nach IH $r_n = q_0$ und somit
				$$
795
796
797
798
799
800
					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.
801
802
803
				$$
			\item $a_0 = a_{n-1} = a$. Dann ist nach IH $r_n = q_1$ und somit
				$$
804
805
806
807
808
809
					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.
810
811
812
				$$
			\item $a_0 = a$ und $a_{n-1} = b$. Dann ist nach IH $r_n = q_2$ und somit
				$$
813
814
815
816
817
818
					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.
819
820
821
				$$
			\item $a_0 = b$. Dann ist nach IH $r_n = q_3$ und somit
				$$
822
					r_{n+1} = \delta(r_n, a_n) = q_3
823
824
				$$
				unabhängig von $a_n$.
825
826
827
828
829
830
831
832
833
834
		\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}
Niklas Rieken's avatar
Niklas Rieken committed
835
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.
836
837
838
839
840
841


\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}
842
	Sei $L \subseteq \Sigma^\ast$ eine DFA-erkennbare Sprache. Dann ist auch $\comp{L}$ DFA-erkennbar.
843
	\begin{proof}
844
845
		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
		$$