kurzskript.tex

\documentclass{scrreprt}


\usepackage[ngerman]{babel} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{color}
\usepackage{longtable}
\usepackage[shortlabels]{enumitem}
\usepackage{framed}
\usepackage{tabularx}
\usepackage{syntax}
\usepackage{proof}
\usepackage{multirow}
\usepackage{stmaryrd}
\usepackage[colorlinks,
pdfpagelabels,
pdfstartview = FitH,
bookmarksopen = true,
bookmarksnumbered = true,
linkcolor = black,
plainpages = false,
hypertexnames = false,
citecolor = black] {hyperref}
\usepackage{zed-csp}

\newtheoremstyle{example}
  {\topsep}{\topsep}%
  {\itshape}{}%
  {\bfseries}{.}%
  {\newline}{}%

\newtheoremstyle{algorithm}
  {\topsep}{\topsep}%
  {\itshape}{}%
  {\bfseries}{.}%
  {\newline}{}%
  
\theoremstyle{definition}
\newtheorem{Definition}{Definition}[section]
\newtheorem{Satz}{Satz}[section]
\newtheorem{Lemma}{Lemma}[section]

\theoremstyle{example}
\newtheorem{Beispiel}{Beispiel}[section]

\theoremstyle{algorithm}
\newtheorem{Algorithmus}{Algorithmus}[section]

\begin{document}
% {\uppercase\expandafter{\romannumeral1}}:\\Komplexität und formale Sprachen
\title{Theoretische Informatik}
\subtitle{Kurzskript zu den Vorlesungen von}
\author{Prof. Van Bang Le \and Prof. Karsten Wolf}

\maketitle
\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{chapter}{-1}
\chapter{Wichtige Begriffe aus der Berechenbarkeitstheorie}
{\Large\textbf{\textsf{Ist ein Problem algorithmisch lösbar?}}}
\begin{Definition}[Turingmaschine]
Eine \textcolor{blue}{deterministische Turingmaschine} (DTM) (oder ein deterministisches Turingprogramm) $M$ ist ein 5-Tupel $M=(Z,\Sigma,\delta,z_a,z_e)$ mit:
\begin{itemize}
\item $Z$ ist eine endliche Menge von Zuständen
\item $z_a$ ist der ausgezeichnete Anfangszustand
\item $z_e$ ist der ausgezeichnete Endzustand
\item $\Sigma$ ist eine endliche Menge, das \textcolor{blue}{Bandalphabet}\\
$\Box$ ist ein ausgezeichnetes Symbol in $\Sigma$: es heißt \textcolor{blue}{Leersymbol} (Blank) und zeigt an, dass die Bandzelle leer ist
\item $Z \cap \Sigma = \emptyset$
\item $\delta : Z \times \Sigma \rightarrow Z \times \Sigma \times \{+1,-1,0\}$ ist eine nicht notwendig überall definierte Funktion, die \textcolor{blue}{Übergangsfunktion} 
\end{itemize}
\end{Definition}

\begin{Definition}[Turing-berechenbar]
Eine (partielle) Funktion $f: \Sigma^* \rightarrow \Sigma^*$ heißt \textcolor{blue}{Turingprogramm-berechenbar}, falls eine DTM $M$ existiert mit $f=f_M$.
\end{Definition}

\begin{Definition}[Entscheidbarkeit]
Eine Menge $A\subseteq \mathbb{N}$ (bzw. $A\subseteq \mathbb{N}^k$ oder $A\subseteq \Sigma^*$) heißt \textcolor{blue}{entscheidbar}, wenn die charakteristische Funktion $\chi_A : \mathbb{N} \rightarrow \{0,1\}$ (bzw. $\chi_A : \mathbb{N}^k \rightarrow \{0,1\}$ oder $\chi_A : \Sigma^* \rightarrow \{0,1\}$) von $A$,
\begin{flalign*}
\chi_A(x) =
\begin{cases}
1&\text{falls $x\in A$}\\
0&\text{sonst, also falls $x\not\in A$}\\
\end{cases}
\end{flalign*}
berechenbar ist.
\end{Definition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Komplexität}
{\Large\textbf{\textsf{Wie schwierig ist ein lösbares Problem?}}}

\section{Graphen}
\begin{Definition}
Ein (ungerichteter, einfacher) Graph $G$ ist ein Paar $G=(V,E)$ bestehend aus \textcolor{blue}{Knotenmenge} $V$ und \textcolor{blue}{Kantenmenge} $E\subseteq \binom{V}{2}$.\\
$\binom{V}{2}$ steht hierbei für die Menge aller 2-elementigen Teilmengen von $V$.
\end{Definition}
\begin{Definition}
Sei $G=(V,E)$ ein Graph. Dann gilt:
\begin{enumerate}
\item Zwei Knoten $x,y \in V$ sind \textcolor{blue}{verbunden}, wenn $\{x,y\} \in E$ ist.
\item Eine Menge $Q \subseteq V$ von Knoten ist eine \textcolor{blue}{Clique}, wenn je zwei Knoten in $Q$ verbunden sind.
\item Eine Menge $U \subseteq V$ von Knoten ist eine \textcolor{blue}{unabhängige Menge} (independent set), wenn je zwei Knoten in $U$ unverbunden sind.
\end{enumerate}
\end{Definition}

\section{Zeitaufwand und Komplexitätsklassen}
\begin{Definition}[$\mathcal{O}$-Notation]
Für Funktionen $f, g: \mathbb{N} \rightarrow \mathbb{R}$ schreiben wir \textcolor{blue}{$f \in \mathcal{O}(g)$} oder auch \textcolor{blue}{$f=\mathcal{O}(g)$}, falls es eine Konstante $c>0$ gibt mit: Es existiert ein $n_0$, sodass $f(n) \leq c \cdot g(n)$ für alle $n\geq n_0$ gilt. Man sagt, dass $f$ asymptotisch höchstens so stark wächst wie $g$.\\
Formal: $f \in \mathcal{O}(g) \Leftrightarrow \exists c>0 \, \exists n_0 \in \mathbb{N}\, \forall n\geq n_0:f(n)\leq c \cdot g(n)$
\end{Definition}

\begin{Definition}[Zeitaufwand von DTM-Programmen]
Sei $M$ eine DTM über dem Alphabet $\Sigma$. Der \textcolor{blue}{Zeitaufwand} $t_M(w)$ von $M$ bei Eingabe $w \in \Sigma^*$ ist
\begin{flalign*}
t_M(w)=
\begin{cases}
\parbox[t]{0.5\textwidth}{Zahl der Konfigurationsübergänge der Berechnung von $M$ bei Eingabe $w$}&\text{falls Berechnung abbricht}\\
\infty&\text{sonst}\\
\end{cases}&&
\end{flalign*}
Der \textcolor{blue}{Zeitaufwand} $t_M(n)$ von $M$ bei Eingaben der Codierungslänge $n$ ist\\
$t_M(n)=\max \{t_M(w)|w\in\Sigma^n\}$
\end{Definition}

\begin{Definition}
Es sei $f : \mathbb{N} \rightarrow \mathbb{N}$ eine Funktion. Mit \textcolor{blue}{\textsf{DTIME($f$)}} bezeichnen wir die Menge aller Entscheidungsprobleme, die sich durch eine DTM $M$ mit Zeitaufwand $t_m = O(f)$ entscheiden lassen:\\
$\textcolor{blue}{\textsf{DTIME(f)}}=\{L\subseteq \Sigma^* \mid \text{$L$ ist entscheidbar durch eine DTM $M$ mit $t_m=\mathcal{O}(f)$} \}$
\end{Definition}

\begin{Definition}[Komplexitätsklasse \textsf{P}]
$\textsf{P} = \bigcup\limits_{k=0}^\infty \textsf{DTIME}(n^k)$ ist die Klasse aller in (deterministisch) \textbf{p}olynomiellem Zeitaufwand lösbaren (Entscheidungs-) Probleme.  \textsf{P} ist also die Klasse von Problemen, die effizient gelöst werden können.
\end{Definition}

\begin{Definition}[Komplexitätsklasse \textsf{EXPTIME}]
$\textsf{EXPTIME} = \bigcup\limits_{k=0}^\infty \textsf{DTIME}(2^{n^k})$ ist die Klasse aller in (deterministisch) exponentiellem Zeitaufwand lösbaren (Entscheidungs-) Probleme. (Es gilt: $\textsf{P}\subseteq \textsf{EXPTIME}$)
\end{Definition}

\begin{Definition}[Nichtdeterministische Turingmaschine]
Eine \textcolor{blue}{nichtdeterministische Turingmaschine} (NTM) (oder ein nichtdet. Turingprogramm) $M$ ist ein 5-Tupel $M=(Z,\Sigma,\delta,z_a,z_e)$ mit:
\begin{itemize}
\item $Z$,$z_a$,$z_e$,$\Sigma$ sind definiert wie bei einer deterministischen Turingmaschine
\item $\delta \subseteq (Z \times \Sigma) \times (Z \times \Sigma \times \{+1,-1,0\})$ ist eine \textcolor{red}{Relation}, die \textcolor{blue}{Übergangsrelation} 
\end{itemize}
In einem nichtdeterministischen Turingprogramm $\delta$ kann es zu einem Paar $(z,x)\in Z \times \Sigma$ mehr als einen Befehl mit der linken Seite $z,x$ geben.
\end{Definition}

\begin{Definition}[Nichtdeterministische Berechnung]
Jedem Eingabewort $w\in \Sigma^*$ kann man einen \glqq Berechnungsbaum \grqq zuordnen, dessen maximale Pfade den möglichen Berechnungen entsprechen:
\begin{itemize}
\item Die Wurzel des Berechnungsbaums ist mit der Anfangskonfiguration $z_a w$ beschriftet
\item Ist $v$ ein Knoten des Baums, der mit der Konfiguration $K = \alpha zx \beta$ markiert ist und ist $\delta(z,x) = \{ (z_1,x_1,\lambda_1),\ldots,(z_r,x_r,\lambda_r)\}$, so hat $v$ genau $r$ Söhne, die jeweils mit den Nachfolgekonfigurationen $K_i$ von $K$ bezüglich $(z_i,x_i,\lambda_i)$ beschriftet sind, $i=1,\ldots,r$.
\end{itemize}
\end{Definition}

\begin{Definition}[Nichtdeterministische Entscheidbarkeit]
Eine NTM $M$ entscheidet die Menge $L\subseteq \Sigma^*$, falls der Berechnungsbaum jedes Eingabewortes $w\in \Sigma^*$ endlich ist und für $w\in L$ mindestens einen erfolgreichen Berechnungspfad enthält.
\end{Definition}

\begin{Satz}
Sei $L\subseteq \Sigma^*$. Dann ist $L$ genau dann (deterministisch) entscheidbar, wenn $L$ nichtdeterministisch entscheidbar ist.
\end{Satz}

\begin{Definition}[Zeitaufwand von NTM-Programmen]
Sei $M$ eine NTM über dem Alphabet $\Sigma$. Der \textcolor{blue}{Zeitaufwand} $t_M(w)$ von $M$ bei Eingabe $w \in \Sigma^*$ ist
\begin{flalign*}
t_M(w)=
\begin{cases}
\parbox[t]{0.5\textwidth}{Tiefe des Berechnungsbaumes von $M$ bei Eingabe $w$}&\text{falls Baum endlich}\\
\infty&\text{sonst}\\
\end{cases}&&
\end{flalign*}
Der \textcolor{blue}{Zeitaufwand} $t_M(n)$ von $M$ bei Eingaben der Codierungslänge $n$ ist\\
$t_M(n)=\max \{t_M(w)|w\in\Sigma^n\}$
\end{Definition}

\begin{Definition}
Es sei $f : \mathbb{N} \rightarrow \mathbb{N}$ eine Funktion. Mit \textcolor{blue}{\textsf{NTIME($f$)}} bezeichnen wir die Menge aller Entscheidungsprobleme, die sich durch eine NTM $M$ mit Zeitaufwand $t_m = O(f)$ entscheiden lassen:\\
$\textcolor{blue}{\textsf{NTIME(f)}}=\{L\subseteq \Sigma^* \mid \text{$L$ ist entscheidbar durch eine NTM $M$ mit $t_m=\mathcal{O}(f)$} \}$
\end{Definition}

\begin{Definition}[Komplexitätsklasse \textsf{NP}]
$\textsf{NP} = \bigcup\limits_{k=0}^\infty \textsf{NTIME}(n^k)$ ist die Klasse aller in \textbf{n}ichtdeterministisch \textbf{p}olynomiellem Zeitaufwand lösbaren (Entscheidungs-) Probleme.
\end{Definition}

\begin{Satz}
$\textsf{P}\subseteq \textsf{NP} \subseteq \textsf{EXPTIME}$
\end{Satz}

\section{Polynomielle Reduktion und \textsf{NP}-Vollständigkeit}
\begin{Definition}[Polynomielle Reduktion]
Seien $L_1 \subseteq \Sigma_1^*$, $L_2 \subseteq \Sigma_2^*$ zwei Entscheidungsprobleme. $L_1$ ist auf $L_2$ \textcolor{blue}{polynomiell reduzierbar}, wenn es eine überall definierte, polynomiell berechenbare Funktion $f:\Sigma_1^* \rightarrow \Sigma_2^*$ gibt, so dass für alle $x\in\Sigma_1^*$ gilt:
\begin{equation*}
x\in L_1 \Leftrightarrow f(x) \in L_2
\end{equation*}
Ist $L_1$ polynomiell reduzierbar auf $L_2$ via $f$, so schreiben wir: $L_1 \leq_p L_2$
\end{Definition}

\begin{Definition}[\textsf{NP}-Vollständigkeit]
Es sei $L\subseteq\Sigma^*$. $L$ heißt \textcolor{blue}{\textsf{NP}-vollständig}, falls gilt:
\begin{enumerate}
\item[(i)] $L\in \textsf{NP}$
\item[(ii)] $\forall M\in\textsf{NP}: M\leq_p L$
\end{enumerate}
\end{Definition}
\begin{Lemma}
Ist $L$ \textsf{NP}-vollständig, so gilt: $\L \in \textsf{P} \Leftrightarrow \textsf{P} = \textsf{NP}$
\end{Lemma}
\begin{Satz}[Satz von Cook und Levin]
\textsf{SAT} ist \textsf{NP}-vollständig.
\end{Satz}
\begin{Satz}
Ist $A$ $\textsf{NP}$-vollständig, $A \leq_p B$ und $B \in \textsf{NP}$, so ist $B$ $\textsf{NP}$-vollständig.
\end{Satz}

\begin{Satz}
$\textsf{3-SAT}$ ist $\textsf{NP}$-vollständig.
\end{Satz}

\begin{Satz}
$\textsf{CLIQUE}$ ist $\textsf{NP}$-vollständig.
\end{Satz}

\begin{Satz}
$\textsf{INDSET}$ und $\textsf{VERTEX COVER}$ sind $\textsf{NP}$-vollständig.
\end{Satz}

\begin{Satz}
$\textsf{3-Färbbarkeit}$ ist $\textsf{NP}$-vollständig.
\end{Satz}

\begin{Satz}
$\textsf{SUBSET-SUM}$ ist $\textsf{NP}$-vollständig.
\end{Satz}

\begin{Definition}[Komplexitätsklasse \textsf{coK}]
Sei $\textsf{K}$ eine Komplexitätsklasse über dem Alphabet $\Sigma$. Dann heißt
\begin{equation*}
\textsf{coK} :=\{L\subseteq\Sigma^* \mid \overline{L} \in K\}
\end{equation*}
die Klasse der Sprachen (Entscheidungsprobleme) $L$, deren Komplement $\overline{L}$ in $K$ liegt.
\end{Definition}

\begin{Satz}
$\textsf{coP} = \textsf{P}$
\end{Satz}

\section{Platzkomplexität}
\begin{Definition}[Speicherbedarf von DTM-Programmen]
Sei $M$ eine DTM über dem Alphabet $\Sigma$. Der \textcolor{blue}{Speicherbedarf} $s_M(w)$ von $M$ bei Eingabe $w \in \Sigma^*$ ist
\begin{flalign*}
s_M(w)=
\begin{cases}
\parbox[t]{0.5\textwidth}{Zahl der Bandzellen, die $M$ bei Bearbeitung von Eingabe $w$ besucht}&\text{falls Berechnung abbricht}\\
\infty&\text{sonst}\\
\end{cases}&&
\end{flalign*}
Der \textcolor{blue}{Speicherbedarf} $s_M(n)$ von $M$ bei Eingaben der Codierungslänge $n$ ist\\
$s_M(n)=\max \{s_M(w)|w\in\Sigma^n\}$
\end{Definition}

\begin{Definition}
Sei $f: \mathbb{N} \rightarrow \mathbb{N}$ eine Funktion.
\begin{itemize}
\item
$\textcolor{blue}{\textsf{DSPACE}(f)}$ ist die Menge aller Entscheidungsprobleme, die sich durch eine DTM $M$ mit Speicherbedarf $s_M = O(f)$ entscheiden lassen.
\item
$\textcolor{blue}{\textsf{NSPACE}(f)}$ ist die Menge aller Entscheidungsprobleme, die sich durch eine NTM $M$ mit Speicherbedarf $s_M = O(f)$ entscheiden lassen.
\end{itemize}
\end{Definition}

\begin{Definition}[Platzkomplexitätsklassen \textsf{PSPACE} und \textsf{NSPACE}]
\begin{equation*}
\textsf{PSPACE} := \bigcup_{k=0}^\infty \textsf{DSPACE}(n^k) \quad \textsf{NSPACE} := \bigcup_{k=0}^\infty \textsf{NSPACE}(n^k)
\end{equation*}
\end{Definition}

\begin{Satz}[Satz von Savitch]
$\textsf{PSPACE}=\textsf{NSPACE}$
\end{Satz}

\begin{Satz}
$\textsf{P}\subseteq\textsf{NP}\subseteq\textsf{PSPACE}\subseteq\textsf{EXPTIME}$
\end{Satz}

\section{Umgang mit schwierigen Problemen}
\subsection{\textcolor{blue}{Betrachtung von Spezialfällen}}
Manchmal sind nur spezielle Fälle eines schwierigen Problems praktisch relevant. Für diese kann es möglich sein, sie effizient zu lösen.
\begin{Beispiel}
\textsf{SUBSET SUM} ist für {\glqq}super-wachsende{\grqq} Eingaben polynomiell lösbar.
\end{Beispiel}
\subsection{\textcolor{blue}{Annäherungsverfahren}}
Man betrachtet die \textcolor{blue}{Optimierungsversion} des zugehörigen Entscheidungsproblems und probiert die Lösung zu approximieren.
\begin{Definition}
Ein \textcolor{blue}{$c$-Approximationsalgorithmus} $A$ (mit Güte $c > 1$) ist ein Algorithmus mit:
\begin{itemize}
\item
Die Laufzeit von $A$ ist polynomiell zur Eingabelänge.
\item
Die Ausgabe $v$ von $A$ zur Eingabe $w$ ist eine zulässige Lösung.
\item
$c=
\begin{cases}
\frac{v}{v^*}& \text{bei Minimierungsproblemen}\\
\frac{v^*}{v}& \text{bei Maximierungsproblemen}\\
\end{cases}$, wobei $v^*$ eine optimale Lösung ist.
\end{itemize}
\end{Definition}
\subsection{\textcolor{blue}{Parametrisierte Algorithmen}}
Komplexe Parameter des Problems werden von der Eingabe getrennt.

\subsection{\textcolor{blue}{Randomisierte Algorithmen}}
Ein randomisierter Algorithmus hat in seinem Ablauf Zugriff auf eine Quelle von Zufallszahlen.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Formale Sprachen}
{\Large\textbf{\textsf{Wie können Sprachen beschrieben werden?}}}

\section{Grundbegriffe}
\begin{Definition}[Alphabete, Wörter, Sprachen]
\noindent
\begin{itemize}
\item
Ein \textcolor{blue}{Alphabet} $\Sigma$ ist eine nichtleere, endliche Menge.
\item
Die Elemente von $\Sigma$ heißen \textcolor{blue}{Zeichen} (Symbole, Buchstaben) des Alphabets.
\item
Ein \textcolor{blue}{Wort} $w$ über dem Alphabet $\Sigma$ ist eine endliche Folge von Zeichen aus $\Sigma$.
\item
Die \textcolor{blue}{Länge} $|w|$ des Wortes $w$ ist die Anzahl der Zeichen in $w$.
\item
Das \textcolor{blue}{leere Wort} $\varepsilon$ bezeichnet das Wort der Länge $0$.
\item
$\Sigma^*$ ist die Menge aller Wörter über $\Sigma$.
\item
Eine \textcolor{blue}{formale Sprache} über dem Alphabet $\Sigma$ ist eine Teilmenge von $\Sigma^*$.
\end{itemize}
\end{Definition}

\begin{Definition}[Grammatik]
Eine Grammatik ist ein 4-Tupel $G=(N,\Sigma,R,S)$ mit
\noindent
\begin{itemize}
\item
einem endlichem Alphabet $N$ von \textcolor{blue}{\textbf{N}ichtterminalen},
\item
einem endlichen Alphabet $\Sigma$ von \textcolor{blue}{Terminalen}, $N\cap \Sigma = \varnothing$,
\item
einer endlichen Menge $R \subseteq (N \cup \Sigma)^* N (N \cup \Sigma)^* \times (N \cup \Sigma)^*$ von (Produktions-) \textcolor{blue}{\textbf{R}egeln},
\item
und einem \textcolor{blue}{\textbf{S}tartsymbol} $S\in N$.
\end{itemize}
\end{Definition}

\begin{Definition}
Die von einer Grammatik $G=(N,\Sigma,R,S)$ \textcolor{blue}{erzeugte Sprache} ist $L(G)=\{w\in \Sigma^* \mid S \Rightarrow^* w\}$.
\end{Definition}

\begin{Definition}
Zwei Grammatiken $G_1=(N_1,\Sigma_1,R_1,S_1)$ und $G_2=(N_2,\Sigma_2,R_2,S_2)$ heißen \textcolor{blue}{äquivalent}, wenn $L(G_1)=L(G_2)$ gilt.
\end{Definition}

\begin{Satz}
$L\subseteq\Sigma^*$ ist aufzählbar $\Leftrightarrow$ Es gibt Grammatik $G=(N,\Sigma,R,S)$ mit $L = L(G)$.
\end{Satz}

\section{Chomsky Hierarchie}
\begin{Definition}[Typ 0: Unbeschränkte Grammatiken]
\noindent
\begin{itemize}
\item
Eine Grammatik $G=(N,\Sigma,R,S)$ heißt \textcolor{blue}{unbeschränkt}.
\item
Eine Sprache $L$ ist \textcolor{blue}{aufzählbar}, falls es eine unbeschränkte Grammatik $G$ gibt mit $L(G)=L$.
\end{itemize}
\end{Definition}

\begin{Definition}[Typ 1: Kontextsensitive Grammatiken]
\noindent
\begin{itemize}
\item
Eine Grammatik $G=(N,\Sigma,R,S)$ heißt \textcolor{blue}{kontextsensitiv}, wenn für jede Regel $u\rightarrow v$ in $R$ gilt: $|u| \leq |v|$, mit der Ausnahme $S \rightarrow \varepsilon$, falls das Startsymbol $S$ auf keiner rechten Seite einer Regel vorkommt.
\item
Eine Sprache $L$ heißt \textcolor{blue}{kontextsensitiv}, falls es eine kontextsensitive Grammatik $G$ gibt mit $L(G)=L$.
\end{itemize}
\end{Definition}

\begin{Satz}
Kontextsensitive Sprachen sind entscheidbar.
\end{Satz}

\begin{Definition}[Typ 2: Kontextfreie Grammatiken]
\noindent
\begin{itemize}
\item
Eine Grammatik $G=(N,\Sigma,R,S)$ heißt \textcolor{blue}{kontextfrei}, wenn für jede Regel $u\rightarrow v$ in $R$ gilt: $u \in N$.
\item
Eine Sprache $L$ heißt \textcolor{blue}{kontextfrei}, falls es eine kontextfreie Grammatik $G$ gibt mit $L(G)=L$.
\end{itemize}
\end{Definition}

\begin{Definition}[Typ 3: Reguläre Grammatiken]
\noindent
\begin{itemize}
\item
Eine Grammatik $G=(N,\Sigma,R,S)$ heißt \textcolor{blue}{regulär} (oder rechtslinear), wenn für jede Regel $u\rightarrow v$ in $R$ gilt: $u \in N$ und $v\in\{\varepsilon\}\cup\Sigma\cup\Sigma N$.
\item
Eine Sprache $L$ heißt \textcolor{blue}{regulär}, falls es eine reguläre Grammatik $G$ gibt mit $L(G)$.
\end{itemize}
\end{Definition}

\begin{Satz}[Chomsky-Hierarchie]
Typ 3 $\subset$ Typ 2 $\subset$ Typ 1 $\subset$ Typ 0
\end{Satz}

\section{Endliche Automaten}
\begin{Definition}[Endliche Automaten]
Ein \textcolor{blue}{nichtdeterministischer endlicher Automat} (NEA) ist ein $5$-Tupel $A=(Z,\Sigma,\delta,z_0,F)$ mit:
\begin{itemize}
\item
$Z$ endliche Zustandsmenge
\item
$z_0 \in Z$ \textcolor{blue}{Anfangszustand}
\item
$F \in Z$ Menge der akzeptierenden Zustände (\textcolor{blue}{Endzustände})
\item
$\Sigma$ endlichens \textcolor{blue}{Eingabealphabet}
\item
$\delta : Z \times \Sigma \rightarrow 2^Z$ \textcolor{blue}{Überführungsrelation}
\end{itemize}
Ist die Überführungsrelation eine Funktion, also $\delta : Z \times \Sigma \rightarrow Z$, so ist der endliche Automat \textcolor{blue}{deterministisch} (DEA).
\end{Definition}

\begin{Definition}[Sprache eines NEA]
Sei $A=(Z,\Sigma,\delta, z_0,F)$ ein NEA.
\begin{itemize}
\item
Ein \textcolor{blue}{Lauf} von $A$, gesteuert durch Eingabefolge $w=x_0 x_1 \ldots x_n \in \Sigma^*$ ist \textcolor{red}{eine} Folge von Zuständen $z_0$, $z_1$, $\ldots$, $z_{n+1}$ mit $z_{i+1}\textcolor{red}{\in} \delta(z_i,x_i)$, $0 \leq i \leq n$.\par
Ist $w=\varepsilon$, so besteht der Lauf nur aus dem Anfangszustand $z_0$.
\item
Die von $A$ \textcolor{blue}{akzeptierte Sprache} ist
\begin{flalign*}
L(A) = \{ w\in \Sigma^* \mid \,&\text{\textcolor{red}{es gibt einen} Lauf von $A$, gesteuert durch $w$,}&\\
&\text{der zu einem Endzustand führt}\}&
\end{flalign*}
\end{itemize}
\end{Definition}

\begin{Definition}[Sprache eines DEA]
Sei $A=(Z,\Sigma,\delta, z_0,F)$ ein DEA.
\begin{itemize}
\item
Ein \textcolor{blue}{Lauf} von $A$, gesteuert durch Eingabefolge $w=x_0 x_1 \ldots x_n \in \Sigma^*$ ist \textcolor{red}{die} Folge von Zuständen $z_0$, $z_1$, $\ldots$, $z_{n+1}$ mit $z_{i+1}\textcolor{red}{=} \delta(z_i,x_i)$, $0 \leq i \leq n$.\par
Ist $w=\varepsilon$, so besteht der Lauf nur aus dem Anfangszustand $z_0$.
\item
Die von $A$ \textcolor{blue}{akzeptierte Sprache} ist
\begin{flalign*}
L(A) = \{ w\in \Sigma^* \mid \,&\text{\textcolor{red}{der} Lauf von $A$, gesteuert durch $w$,}&\\
&\text{führt zu einem Endzustand}\}&
\end{flalign*}
\end{itemize}
\end{Definition}

\begin{Definition}
Zwei endliche Automaten sind \textcolor{blue}{äquivalent}, wenn sie die gleiche Sprache akzeptieren.
\end{Definition}

\begin{Satz}
Zu jedem NEA gibt es einen äquivalenten DEA.\par
Ist $A=(Z,\Sigma,\delta,z_0,F)$ ein NEA, dann ist der Potenzmengenautomat $A^\prime = (2^Z,\Sigma,\delta^\prime,\{z_0\},F^\prime)$ mit:
\begin{itemize}[$\vartriangleright$]
\item
$F^\prime=\{M\subseteq Z \mid M \cap F \neq \varnothing \}$
\item
$\delta^\prime(M,x)=\bigcup\limits_{z\in M} \delta(z,x)$
\end{itemize}
ein DEA mit $L(A)=L(A^\prime)$.
\end{Satz}

\begin{Satz}
Zu jedem DEA $A$ gibt es eine reguläre Grammatik $G$ mit $L(G)=L(A)$.\par
Ist $A = (Z,\Sigma,\delta,z_0,F)$ ein DEA, dann ist $G = (Z,\Sigma,R,z_0)$ mit
\begin{itemize}[$\vartriangleright$]
\item
ist $z_0 \in F$, so ist $z_0 \rightarrow \varepsilon \in R$
\item
ist $\delta(z,x)=z^\prime$, so ist $z \rightarrow xz^\prime \in R$\par
ist $z^\prime \in F$, so ist außerdem $z^\prime \rightarrow \varepsilon \in R$
\end{itemize}
eine reguläre Grammatik mit $L(G)=L(A)$.
\end{Satz}

\begin{Satz}
Zu jeder regulären Grammatik $G$ gibt es einen NEA $A$ mit ${L(A)=L(G)}$.
\end{Satz}

\section{Reguläre Ausdrücke}

\begin{Definition}[Syntax regulärer Ausdrücke]
Sei $\Sigma$ ein Alphabet.
\begin{enumerate}
\item
\textcolor{blue}{$\varnothing$} und \textcolor{blue}{$\varepsilon$} sind reguläre Ausdrücke.
\item
Für jedes $a\in \Sigma$ ist \textcolor{blue}{$a$} ein regulärer Ausdruck.
\item
Sind $x$ und $y$ reguläre Ausdrücke, so sind auch\par
\textcolor{blue}{$(x)+(y)$}, \textcolor{blue}{$(x)(y)$} und \textcolor{blue}{$(x)^*$} reguläre Ausdrücke.
\item
Weitere reguläre Ausdrücke gibt es nicht.
\end{enumerate}
\end{Definition}

\begin{Definition}[Semantik regulärer Ausdrücke]
Sei $x$ ein regulärer Ausdruck über $\Sigma$. Die von $x$ beschriebene Sprache $L(x)$ ist:
\begin{enumerate}
\item
\textcolor{blue}{$L(\varnothing) = \varnothing$} und \textcolor{blue}{$L(\varepsilon) = \{\varepsilon\}$}.
\item
Für jedes $a\in\Sigma$ ist \textcolor{blue}{$L(a) = \{a\}$}.
\item
\textcolor{blue}{$L(x+y)=L(x)\cup L(y)$}, \textcolor{blue}{$L(xy)=L(x)L(y)$} und \textcolor{blue}{$L(x^*)=L(x)^*$}.
\end{enumerate}
\end{Definition}

\begin{Definition}
Zwei reguläre Ausdrücke $x$, $y$ über $\Sigma$ heißen \textcolor{blue}{äquivalent}, wenn ${L(x)=L(y)}$ gilt, dass heißt wenn sie die gleiche Sprache beschreiben. Schreibweise: ${x \equiv y}$.
\end{Definition}

\begin{Satz}
Zu jedem regulären Ausdruck $x$ gibt es eine reguläre Grammatik $G$ mit ${L(G)=L(x)}$. 
\end{Satz}

\begin{Satz}
Zu jedem DEA $A$ gibt es einen regulären Ausdruck $r$ mit ${L(r)=L(A)}$.
\end{Satz}

\begin{Satz}
$L\subseteq \Sigma^*$ ist regulär genau dann, wenn $L$ aus den Sprachen $\varnothing$, $\{\varepsilon\}$ und $\{a\}$, $a\in\Sigma$, durch Vereinigung $\cup$, Konkatenation (Produkt) und Iteration $^*$ konstruiert werden kann.
\end{Satz}

\section{Reguläre Sprachen}

\begin{Definition}
Ein vollständig definierter DEA $A$ ist \textcolor{blue}{minimal}, falls für alle zu $A$ äquivalenten vollständig definierten DEA $A^\prime$ gilt: $A^\prime$ enthält mindestens soviele Zustände wie $A$.
\end{Definition}

\begin{Definition}[Nerode-Relation]
Sei $L\subseteq\Sigma^*$. Auf der Wortmenge $\Sigma^*$ ist die Relation \textcolor{red}{$\sim_L$} wie folgt definiert:
\begin{equation*}
v \textcolor{red}{\sim_L} w \iff (\forall u \in \Sigma^*: vu \in L \Leftrightarrow wu\in L)
\end{equation*}
Die Relation \textcolor{red}{$\sim_L$} ist eine Äquivalenzrelation auf $\Sigma^*$. Die Anzahl der Äquivalenzklassen heißt der \textcolor{blue}{Myhill-Nerode-Index} von $\sim_L$. Schreibweise: \textcolor{blue}{$\textsc{Index}(\textcolor{red}{\sim_L})$}
\end{Definition}

\begin{Satz}[Myhill \& Nerode]
$L$ ist regulär $\iff$ $\textsc{Index}(\textcolor{red}{\sim_L})$ ist endlich.
\end{Satz}

\begin{Algorithmus}[Minimierung endlicher Automaten]
Sei auf der Zustandsmenge $Z$ eine Äquivalenzrelation wie folgt definiert:
\begin{equation*}
z\equiv z^\prime \iff (\forall u\in \Sigma^*: \delta^*(z,u)\in F \Leftrightarrow \delta^*(z^\prime,u)\in F)
\end{equation*}
Dann gilt $z\not\equiv z^\prime$ genau dann, wenn:
\begin{itemize}[$\vartriangleright$]
\item
$z\in F$, $z^\prime \not\in F$ oder umgekehrt, oder
\item
es gibt ein $a\in\Sigma$ mit $\delta(z,a) \not\equiv \delta(z^\prime, a)$.
\end{itemize}
Sei $A=(Z,\Sigma,\delta,z_0,F)$ ein DEA ohne überflüssige Zustände.
\begin{framed}
\begin{enumerate}[\color{red}(1)]
\item
Markiere alle Paare $\{z,z^\prime\}$ mit: $z\in F$, $z^\prime \not\in F$ oder umgekehrt
\item
Für unmarkierte Paare $\{z,z^\prime\}$ prüfe, ob es ein $a\in\Sigma$ gibt mit markiertem Paar $\{\delta(z,a,),\delta(z^\prime,a)\}$.\\
Wenn ja, dann markiere auch $\{z,z^\prime\}$.
\item
Wiederhole Schritt \textcolor{red}{(2)} bis kein neues markiertes Paar mehr entsteht.
\end{enumerate}
\end{framed}
Dann gilt $z\not\equiv z^\prime \Leftrightarrow \{z,z^\prime\}\,\text{ist markiert}$. Den gesuchten Minimalautomat $A^\prime = (Z^\prime, \Sigma,\delta^\prime,z_0^\prime,F^\prime)$ erhält man aus $A$, indem man die $\equiv$-äquivalenten Zustände zusammen zieht.
\begin{itemize}[$\vartriangleright$]
\item
$Z^\prime=\{[z]:z\in Z\}$, $z_0^\prime = [z_0]$, $F^\prime=\{ [z]:z\in F\}$
\item
$\delta^\prime([z],a) = [\delta(z,a)]$ für alle $[z]\in Z^\prime$ und $a\in \Sigma$
\end{itemize}
\end{Algorithmus}

\begin{Lemma}[Pumping-Lemma für reguläre Sprachen]
Sei $L$ regulär. Dann existiert eine Zahl $n \in \mathbb{N}$, so dass jedes Wort $w \in L$ mit $|w| \geq n$ eine Zerlegung $w=xyz$ mit folgenden Eigenschaften besitzt:
\begin{enumerate}[\color{blue}(1)]
\item
$|y|\geq 1$
\item
$|xy| \leq n$
\item
$xy^kz \in L$ für alle $k=0,1,2,\ldots$
\end{enumerate}
\end{Lemma}

\begin{Satz}[Abschlusseigenschaften]
Die Klasse aller regulären Sprachen über demselben Alphabet ist abgeschlossen unter Vereinigung, Produkt, Stern, Komplement und Schnitt: Sind $L$ und $M$ regulär, so auch $L \cup M$, $LM$, $L^*$, $\overline{L}$ ($= \Sigma^* \setminus L$) und $L \cap M$ regulär.
\end{Satz}

\begin{Beispiel}[Wichtige Entscheidungsprobleme regulärer Sprachen]
\begin{tabular}{ll}
\multicolumn{2}{l}{\textbf{Das Wortproblem}}\\
Gegeben:&DEA $A=(Z,\Sigma,\delta,z_0,F)$ und $w\in\Sigma^*$.\\
Frage:&Ist $w\in L(A)$?\\
\end{tabular}\newline
\begin{tabular}{ll}
\multicolumn{2}{l}{\textbf{Äquivalenztest}}\\
Gegeben:&DEA's $A=(Z,\Sigma,\delta,z_0,F)$ und $A^\prime=(Z^\prime,\Sigma,\delta^\prime,z_0^\prime,F^\prime)$.\\
Frage:&Ist $L(A) = L(A^\prime)$?\\
\end{tabular}\newline
\begin{tabular}{ll}
\multicolumn{2}{l}{\textbf{Leerheitstest}}\\
Gegeben:&DEA $A=(Z,\Sigma,\delta,z_0,F)$.\\
Frage:&Ist $L(A) = \varnothing$?\\
\end{tabular}\newline
\begin{tabular}{ll}
\multicolumn{2}{l}{\textbf{Endlichkeitstest}}\\
Gegeben:&DEA $A=(Z,\Sigma,\delta,z_0,F)$.\\
Frage:&Ist $L(A)$ endlich?\\
\end{tabular}
\end{Beispiel}

\section{Kontextfreie Sprachen}
\begin{Definition}
Eine kontextfreie Grammatik ist in \textcolor{blue}{Chomsky-Normalform} (CNF), wenn alle Regeln von der Form $X\rightarrow YZ$ oder $X \rightarrow a$ für $X, Y, Z \in N$ und $a\in \Sigma$ sind.
\end{Definition}

\begin{Lemma}[Pumping-Lemma für kontextfreie Sprachen]
Sei $L$ kontextfrei. Dann existiert eine Zahl $n \in \mathbb{N}$, so dass jedes Wort $w \in L$ mit $|w| \geq n$ eine Zerlegung $w=uvxyz$ mit folgenden Eigenschaften besitzt:
\begin{enumerate}[\color{blue}(1)]
\item
$|vy|\geq 1$
\item
$|vxy| \leq n$
\item
$uv^kxy^kz \in L$ für alle $k=0,1,2,\ldots$
\end{enumerate}
\end{Lemma}

\begin{Satz}[Abschlusseigenschaften]
Die Klasse aller kontextfreien Sprachen über demselben Alphabet ist abgeschlossen unter Vereinigung, Produkt und Iteration: Sind $L$ und $M$ kontextfrei, so auch $L \cup M$, $LM$ und $L^*$ kontextfrei.\par
Die Klasse aller kontextfreien Sprachen ist jedoch \underline{nicht} abgeschlossen unter Schnitt und Komplement.
\end{Satz}

\begin{Satz}
Das Wortproblem für Kontextfreie Sprachen ist in $\mathcal{O}(|w|^3)$ Zeit lösbar, wobei eine kontextfreie Grammatik in CNF gegeben und $w$ das Eingabewort ist.
\end{Satz}

\begin{Definition}[Kellerautomat]
Ein \textcolor{blue}{nichtdeterministischer Kellerautomat} (NKA) ist ein 7-Tupel $K=(Z,\Sigma,\Gamma,\delta,z_0,\$,F)$ mit:
\begin{itemize}
\item
$Z$ endliche Zustandsmenge
\item
$z_0 \in Z$ Anfangszustand
\item
$F\subseteq Z$ Menge der akzeptierenden Zustände (Endzustände)
\item
$\Sigma$ endliches Eingabealphabet
\item
$\Gamma$ endliches Kelleralphabet
\item
$\$\in\Gamma$ das Kellerbodensymbol
\item
$\delta : Z \times (\Sigma\cup\{\varepsilon\}) \times \Gamma \rightarrow 2^{(Z\cup\Gamma^*)}$ Überführungsrelation
\end{itemize}
\end{Definition}

\begin{Satz}[Sprache von NKA's]
\noindent
\begin{enumerate}[1)]
\item
Jede von einem NKA akzeptierte Sprache ist kontextfrei.
\item
Zu jeder kontextfreien Grammatik $G$ existiert ein NKA $K$ mit ${L(G)=L_\varepsilon(K)}$.
\end{enumerate}
\end{Satz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Semantik von Programmiersprachen}
{\Large\textbf{\textsf{Welche (rechnerische) Bedeutung hat ein Programm?}}}

\section{Eine einfache Programmiersprache: $W$}
\setlength{\grammarindent}{3cm} % increase separation between LHS/RHS
\begin{grammar}
<cmd_seq> ::= <command>
\alt <cmd_seq> `;' <command>

<command> ::= <identifier> `=' <expression>
\alt `skip'
\alt `while' <expression> `do' <cmd_seq> `end'
\alt `if' <expression> `then' <cmd_seq> `end'
\alt `if' <expression> `then' <cmd_seq> `else' <cmd_seq> `end'

<expression> ::= <term>
\alt <expression> (`+' | `-' | `OR') <term>

<term> ::= <factor>
\alt term (`*'  | `/' | `AND') <factor>

<factor> ::= <number> | <identifier>
\alt `true' | `false' | `NOT' <factor>
\alt `(' <expression> `)'
\alt <expression> (`<' | `>' | `<=' | `>=' | `<>' | `=') <expression>
\end{grammar}

\section{Operationelle Semantik}
\textbf{\textsf{Wie entsteht der Effekt eines Programms?}}\\
Die Bedeutung eines Programms wird angegeben als Sequenz von Schritten, die Zustandstransformationen eines abstrakten Maschinenmodells beschreiben. Über Axiome und Schlussregeln kann so das Verhalten des Programms aus dem Verhalten seiner Komponenten hergeleitet werden. Formale operationelle Semantik ermöglicht die Argumentation über Terminierung, semantische Äquivalenz, Determiniertheit und Korrektheit einer Übersetzung.\\
\textbf{Anwendung:} Vergleich von Systemen, Model Checking

\subsection{Natural Semantics (Big Step)}
\textbf{\textsf{Jedes Programm ist eine Zustandstransformation.}}\\
\begin{tabularx}{\linewidth}{lX}
$\langle C,s\rangle\rightarrow s^\prime$&Gestartet in Zustand $s$ terminiert Programm $C$ und führt zu Zustand $s^\prime$\\
\end{tabularx}
Geeignet für Blockstrukturen.

\begin{framed}
\begin{tabularx}{\linewidth}[t]{lX}
$[\text{skip}_\text{NatS}]$&$\langle \text{skip},s\rangle\rightarrow s$\\
$[\text{ass}_\text{NatS}]$&$\langle x:=E,s\rangle\rightarrow s[x\rightarrow \mathbb{A} \llbracket E \rrbracket (s)]$\\
$[\text{comp}_\text{NatS}]$&\infer{\langle C_1;C_2,s \rangle \rightarrow s^{\prime\prime}}{\langle C_1,s \rangle \rightarrow s^\prime & \langle C_2,s^\prime \rangle \rightarrow s^{\prime\prime}}\\
$[\text{if}^1_\text{NatS}]$&\infer{\langle \text{if $b$ then $C_1$ else $C_2$ end},s\rangle\rightarrow s^\prime}{\langle C_1,s\rangle\rightarrow s^\prime & \mathbb{B}\llbracket b \rrbracket (s) = T}\\
$[\text{if}^2_\text{NatS}]$&\infer{\langle \text{if $b$ then $C_1$ else $C_2$ end},s\rangle\rightarrow s^\prime}{\langle C_2,s\rangle\rightarrow s^\prime & \mathbb{B}\llbracket b \rrbracket (s) = F}\\
$[\text{while}^1_\text{NatS}]$&\infer{\langle \text{while $b$ do $C$ end},s\rangle\rightarrow s^{\prime\prime}}{\langle C,s\rangle\rightarrow s^\prime & \langle \text{while $b$ do $C$ end},s^\prime\rangle\rightarrow s^{\prime\prime} &\mathbb{B}\llbracket b \rrbracket (s) = T}\\
$[\text{while}^2_\text{NatS}]$&\infer{\langle \text{while $b$ do $C$ end},s\rangle\rightarrow s}{\mathbb{B}\llbracket b \rrbracket (s) = F}\\
\end{tabularx}
\begin{equation*}
\mathbb{S}_\text{NatS} \llbracket C \rrbracket (s) :=
\begin{cases}
s^\prime&\langle C, s \rangle\rightarrow s^\prime\\
\bot&\text{sonst}\\
\end{cases}
\end{equation*}
\end{framed}

\subsection{Structural Operational Semantics (Small Step)}
\textbf{\textsf{Jedes Programm ist eine Folge elementarer Zustandstransformation.}}\\
\begin{tabularx}{\linewidth}{lX}
$\langle C,s\rangle\rightarrow s^\prime$&Gestartet in Zustand $s$ terminiert Programm $C$ und führt zu Zustand $s^\prime$\\
$\langle C,s\rangle\rightarrow \langle C^\prime,s^\prime\rangle$&Die Ausführung von Programm $C$ im Zustand $s$ kann auf die Ausführung von Programm $C^\prime$ im Zustand $s^\prime$ reduziert werden\\
\end{tabularx}
Geignet für Nichtdeterminismus und Parallelität.

\begin{framed}
\begin{tabularx}{\linewidth}[t]{lX}
$[\text{skip}_\text{SOS}]$&$\langle \text{skip},s\rangle\rightarrow s$\\
$[\text{ass}_\text{SOS}]$&$\langle x:=E,s\rangle\rightarrow s[x\rightarrow \mathbb{A} \llbracket E \rrbracket (s)]$\\
$[\text{comp}^1_\text{SOS}]$&\infer{\langle C_1;C_2,s \rangle \rightarrow \langle C_2, s^{\prime} \rangle}{\langle C_1,s \rangle \rightarrow s^\prime}\\
$[\text{comp}^2_\text{SOS}]$&\infer{\langle C_1;C_2,s \rangle \rightarrow \langle C_1^\prime;C_2, s^{\prime} \rangle}{\langle C_1,s \rangle \rightarrow \langle C_1^\prime, s^\prime\rangle}\\
$[\text{if}^1_{SOS}]$&\infer{\langle \text{if $b$ then $C_1$ else $C_2$ end},s\rangle\rightarrow \langle C_1, s\rangle}{\mathbb{B}\llbracket b \rrbracket (s) = T}\\
$[\text{if}^2_{SOS}]$&\infer{\langle \text{if $b$ then $C_1$ else $C_2$ end},s\rangle\rightarrow \langle C_2, s\rangle}{\mathbb{B}\llbracket b \rrbracket (s) = F}\\
\multirow{2}{*}{$[\text{while}_{SOS}]$}&$\langle \text{while $b$ do $C$ end},s\rangle\rightarrow$\\
&$\langle \text{if $b$ then C; while $b$ do $C$ end else skip end},s\rangle$\\
\end{tabularx}
\begin{equation*}
\mathbb{S}_\text{SOS} \llbracket C \rrbracket (s) :=
\begin{cases}
s^\prime&\langle C, s \rangle\rightarrow s^\prime\\
\bot&\text{sonst}\\
\end{cases}
\end{equation*}
\end{framed}

\section{Denotationelle Semantik}
\textbf{\textsf{Was ist der Effekt eines Programms?}}\\
Die Bedeutung eines Programms wird angegeben durch mathematische Formalismen wie Funktionen, Relationen und Gleichungen.\\
\textbf{Anwendung:} Statische Analyse (erhalten von Informationen über die Semantik eines Programms ohne dessen Ausführung)

\subsection{Direct-Style-Semantik}
\begin{itemize}
\item
\textcolor{blue}{kompositional}: Semantik eines Konstrukts allein auf der Basis seiner Teilkonstrukte definiert
\item
Kleinste \textcolor{blue}{Fixpunkte} werden zur Definition der Semantik von Schleifen verwendet
\item
Fixpunkttheorie liefert Existenz solcher Fixpunkte
\end{itemize}

\begin{framed}
\begin{align*}
\mathbb{S}_\text{DS}\llbracket x:=E \rrbracket (s)&= s[x\rightarrow\mathbb{A}\llbracket E\rrbracket(s)]\\
\mathbb{S}_\text{DS}\llbracket \text{skip} \rrbracket&= \text{id}\\
\mathbb{S}_\text{DS}\llbracket C_1;C_2 \rrbracket&= \mathbb{S}_\text{DS}\llbracket C_2 \rrbracket \circ \mathbb{S}_\text{DS}\llbracket C_1 \rrbracket\\
\mathbb{S}_\text{DS}\llbracket \text{if $b$ then $C_1$ else $C_2$ end} \rrbracket&= \text{cond}(\mathbb{B}\llbracket b\rrbracket,\mathbb{S}_\text{DS}\llbracket C_1 \rrbracket,\mathbb{S}_\text{DS}\llbracket C_2 \rrbracket)\\
\mathbb{S}_\text{DS}\llbracket \text{while $b$ do $C$ end} \rrbracket&= \text{FIX}(F)\\
\text{wobei}\,F(g)&=\text{cond}(\mathbb{B}\llbracket b\rrbracket,g \circ \mathbb{S}_\text{DS}\llbracket C \rrbracket,\text{id})
\end{align*}
\end{framed}

\subsection{Flussgraph-Analyse}

\begin{Definition}[Available Expressions]
Zu einem Knoten des Flussgraphen, bestimme alle Expressions, die auf allen Pfaden bereits berechnet sind und seitdem nicht modifiziert wurden.
\end{Definition}

\begin{Definition}[Reaching Definitions]
Für einen Knoten $k$: Welche Zuweisungen sind auf mindestens einem Pfad zu $k$ noch nicht überschrieben?
\end{Definition}

\begin{Definition}[Very busy expressions]
Eine Expression ist very busy an einem Knoten, falls ihr Wert auf jedem Kontrollpfad noch einmal benutzt wird (ohne dass vorkommende Variablen ihren Wert ändern). Very busy expressions können gleich berechnet werden.
\end{Definition}

\begin{Definition}[Live Variables]
Variable ist live an einem Knoten, falls ihr Wert auf mindestens einem Kontrollpfad noch einmal benutzt wird (ohne dass ihr Wert überschrieben wurde). Zuweisungen an Variablen, die nicht live sind, können gestrichen werden.
\end{Definition}

\section{Axiomatische Semantik}
\textbf{\textsf{Was lässt sich über den Effekt eines Programms aussagen?}}\\
Die Bedeutung eines Programms wird angegeben durch Logische Aussagen und Beweiskalküle.\\
\textbf{Anwendung:} Programmverifikation

\subsection{Hoare-Kalkül}

\begin{Definition}[Hoare-Tripel]
$\{P\}\,S\,\{S\}$ heißt Hoare-Tripel, wobei $P$ die Vorbedingungen, $S$ ein Programmsegment und $Q$ die Nachbedingungen bezeichnet.
\begin{itemize}
\item Partielle Korrektheit\\
Wenn $S$ terminiert und vor Abarbeitung von $S$ die Aussage $P$ gilt, so gilt nach der Abarbeitung von $S$ die Aussage $Q$.
\item Totale Korrektheit\\
Wenn vor Abarbeitung von $S$ die Aussage $P$ gilt, dann terminiert $S$ und nach der Abarbeitung von $S$ gilt die Aussage $Q$.
\end{itemize}
\end{Definition}

\begin{framed}
\begin{tabularx}{\linewidth}[t]{lX}
$[\text{skip}_\text{par}]$&$\{ P \}\,\text{skip}\,\{P\}$\\
$[\text{ass}_\text{par}]$&$\{ P[x\rightarrow \mathbb{A} \llbracket E \rrbracket ] \}\,x:=E\,\{P\}$\\
$[\text{comp}_\text{par}]$&\infer{\{P\}\, S_1;S_2 \,\{R\}}{\{P\}\,S_1\,\{Q\} & \{Q\}\,S_2\,\{R\}}\\
$[\text{if}_\text{par}]$&\infer{\{P\}\, \text{if $b$ then $S_1$ else $S_2$ end} \,\{Q\}}{\{P \land \mathbb{B}\llbracket b \rrbracket\}\,S_1\,\{Q\} & \{P \land \lnot\mathbb{B}\llbracket b \rrbracket\}\,S_2\,\{Q\}}\\
$[\text{while}_\text{par}]$&\infer{\{I\}\, \text{while $b$ do $S$ end} \,\{ I \land \lnot \mathbb{B}\llbracket b \rrbracket\}}{\{I \land \mathbb{B}\llbracket b \rrbracket\}\,S\,\{I\}}\\
$[\text{cons}_\text{par}]$&\infer{\{P^\prime\}\, S \,\{Q^\prime\}}{P^\prime \Rightarrow P&\{P\}\,S\,\{Q\} & Q\Rightarrow Q^\prime}\\
\end{tabularx}
\end{framed}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Formale Systeme}
{\Large\textbf{\textsf{Wie kann man Systeme modellieren?}}}

\section{Prozessalgebra}
\begin{Definition}[Prozessalgebra]
Prozessalgebren sind Formalismen zur Beschreibung und zum Studium nebenläufiger/interaktiver Systeme. 
\begin{enumerate}
\item
Es gibt Prozesse und Aktionen.
\item
Ein Prozess kann Aktionen ausführen.
\item
Eine Aktion ändert den ausführenden Prozess.
\item
$\tau$ bezeichnet eine interne, nach außen nicht sichtbare Aktion.
\end{enumerate}
\end{Definition}

\begin{tabularx}{\linewidth}{llX}
\textit{definition}&$P:=Q$&$P$ verhält sich wie $Q$\\
\textit{action}&$P:=a.Q$&In $P$ kann Aktion $a$ stattfinden, danach verhält sich $P$ wie $Q$\\
\textit{choice}&$P:=Q+R$&$P$ kann sich wie $Q$ oder wie $R$ verhalten\\
\textit{termination}&$P:=0$&In $P$ findet keine Aktion mehr statt\\
\textit{parallel}&$P:=Q\,\mid\, R$&$R$ und $Q$ arbeiten parallel\\
\textit{restriction}&$P:=Q\setminus \{a_1,\ldots,a_n\}$&$P$ verhält sich wie $Q$ ohne die Aktionen $a_1,\ldots,a_n$\\
\textit{relabeling}&$P:=Q[a_1 \leftarrow a_1^\prime,\ldots,a_n \leftarrow a_n^\prime\}$&$P$ verhält sich wie $Q$, wobei einige Aktionen umbenannt wurden\\
\end{tabularx}

\begin{itemize}
\item
\textbf{CSP (Communicating Sequential Processes)}\\
$?a.P$ Lies ein $a$ aus der Umgebung und verhalte Dich weiter wie $P$\\
$!a.P$ Schreibe ein $a$ an die Umgebung und verhalte Dich weiter wie $P$
\item
\textbf{CCS (Calculus of Communicating Systems)}\\
Zu jeder Aktion $a$ wird die Existenz einer Komplementäraktion $\overline{a}$ angenommen\\
Kommunikation ist Synchronisation von $a$ und $\overline{a}$\\
\end{itemize}

\begin{Definition}[Trace Semantik]
Eine \textcolor{blue}{Trace} vom Prozess $P$ bezeichnet ein Wort $w$ von Aktionen mit $P-w\rightarrow Q$.
\begin{align*}
\text{T}(P)&:=\text{Menge aller Traces von P}&P&=_T Q \Leftrightarrow \text{T}(P)=\text{T}(Q)
\end{align*}
\end{Definition}

\begin{Definition}[Completed Trace Semantik]
Eine Trace $w$ vom Prozess $P$ heißt \textcolor{blue}{vollständig}, falls $P-w\rightarrow Q$ und $Q=0$.
\begin{align*}
\text{CT}(P)&:=\text{Menge aller vollständigen Traces von P}\\
P=_\text{CT} Q &\Leftrightarrow \text{T}(P)=\text{T}(Q) \land \text{CT}(P)=\text{CT}(Q)
\end{align*}
\end{Definition}

\begin{Definition}[Failure Semantik]
$(w,M)$ heißt \textcolor{blue}{failure pair} vom Prozess $P$, falls $P-w\rightarrow Q$ und keine Aktion $a\in M$ ist in $Q$ ausführbar.
\begin{align*}
\text{FT}(P)&:=\text{Menge aller failure pairs von P}
\end{align*}
\end{Definition}

\begin{Definition}[Simulation Semantik]
$P$ simuliert $Q$, falls $Q$ für jeden Schritt, den $P$ macht, einen passenden Schritt ausführen kann.
\begin{align*}
P-a\rightarrow P^\prime \land P\,s\,Q \Rightarrow \exists Q^\prime : Q-a\rightarrow Q^\prime \land P^\prime \, s\, Q^\prime
\end{align*}
\end{Definition}

\section{Statecharts}
\begin{Definition}[Mealy-Automat]
Ein Mealy-Automat ist ein 6-Tupel $A=(Z,\Sigma,\Omega,\delta,\lambda,z_0)$ mit:
\begin{itemize}
\item
$Z$ endliche Zustandsmenge
\item
$\Sigma$ endliches Eingabealphabet
\item
$\Omega$ endliches Ausgabealphabet
\item
$\delta : Z\times\Sigma\rightarrow Z$ Übergangsfunktion
\item
$\lambda : Z\times\Sigma\rightarrow\Omega$ Ausgabefunktion
\item
$z_0$ Startzustand
\end{itemize}
\end{Definition}

\begin{Definition}[Statecharts]
Statecharts oder Harel-Automaten zur Modellierung reaktiver Systeme erweitern Mealy-Automaten um
\begin{enumerate}
\item
bedingte Zustandsübergänge: $\text{Ereignis}[\text{Bedingung}]/\text{Aktivität}$
\item
hierarchische Zustände
\item
Gedächtnis
\item
Nebenläufigkeit
\end{enumerate}
\end{Definition}

\section{Temporal Logic of Actions (TLA)}
\begin{tabularx}{\linewidth}{lX}
Var&Menge von Variablen\\
Val&Menge von Werten\\
$s: \text{Var}\rightarrow\text{Val}$&Zustand\\
$(s_1,s_2)$&Ein Paar von Zuständen ist ein Schritt.\\
&Eine Folge von Zuständen oder eine Folge von Schritten ist ein Ablauf.\\
&Eine Menge von Abläufen ist ein System.\\
\end{tabularx}

\begin{Definition}[Zustandsformel]
Eine Zustandsformel ist ein Prädikat mit Variablen in Var. Ein Zustand $s$ erfüllt die Zustandsformel $\Phi$, falls $\Phi$ bei der durch $s$ definierten Belegung der Variablen gilt.\\
Schreibweise: $s \models \Phi$
\end{Definition}

\begin{Definition}[Schrittformel]
Eine Schrittformel ist ein Prädikat mit Variablen in $\text{Var} \cup \text{Var}^\prime$. Ein Schritt $(s_1,s_2)$ erfüllt die Schrittformel $\Phi$, falls $\Phi$ bei folgender Belegung $f$ für alle Variablen $v\in\text{Var}$ erfüllt ist:
\begin{align*}
f(v)&=s_1(v)&f(v^\prime)&=s_2(v)
\end{align*}
\end{Definition}

\begin{Definition}[Ablaufformel]
Eine Ablaufformel kann zusätzlich Terme wie $\Box\Phi$ enthalten, wobei $\Phi$ eine Schrittformel ist. Dies bedeutet, dass für einen Ablauf ${\sigma = (s_0,s_1,s_2,\ldots)}$ die Schrittformel $\Phi$ für jeden Schritt von $\sigma$ erfüllt ist.
\end{Definition}

\begin{Definition}[Fairness]
Eine Schrittformel $\Phi$ ist aktiviert in Zustand $s$, falls es ein $s^\prime$ gibt mit $(s,s^\prime)\models \Phi$.
\begin{itemize}
\item
Weak Fair: $\text{WF}_f(\Phi)$\\
Wenn im Ablauf $\sigma$ irgendwann $\Phi\land f \not = f^\prime$ aktiviert ist und für immer aktiviert bleibt, so enthält $\sigma$ unendlich viele Schritte, die $\Phi \land f \not = f^\prime$ erfüllen.
\item
Strong Fair: $\text{SF}_f(\Phi)$\\
Wenn im Ablauf $\sigma$ unendlich oft $\Phi\land f \not = f^\prime$ aktiviert ist, so enthält $\sigma$ unendlich viele Schritte, die $\Phi \land f \not = f^\prime$ erfüllen.
\end{itemize}
\end{Definition}

\section{Petri-Netze}
\begin{Definition}[Petri-Netz]
Ein \textcolor{blue}{Petri-Netz} ist ein $5$-Tupel $N=(S,T,F,W,m_0)$ mit:
\begin{itemize}
\item
$S$ ist eine endliche Menge von \textcolor{blue}{Stellen}
\item
$T$ ist eine endliche Menge von \textcolor{blue}{Transitionen}
\item
$S\cap T = \varnothing$
\item
$S\cup T$ ist die Menge der \textcolor{blue}{Knoten}
\item
$F \subseteq (S\times T) \cup (T \times S)$ ist eine endliche Menge von \textcolor{blue}{Bögen} (\textit{flow relations})
\item
$W: F \rightarrow \mathbb{N} \setminus \{0\}$ sind die \textcolor{blue}{Bogengewichte} (\textit{Weights}) 
\item
$m_0: S \rightarrow \mathbb{N}$ ist die \textcolor{blue}{Anfangsmarkierung}
\item
\textcolor{blue}{Low Level}: Informationsträger tragen keine Daten
\item
\textcolor{blue}{High Level}: Informationsträger tragen Daten
\end{itemize}
\end{Definition}

\begin{Definition}[Bereiche von Knoten]
\noindent
\begin{enumerate}[(a)]
\item
Der \textcolor{blue}{Vorbereich} eines Knotens $x$ ist $\bullet x = \{y \mid (y,x) \in F\}$.\item
Der \textcolor{blue}{Nachbereich} eines Knotens $x$ ist $x\bullet = \{y \mid (x,y) \in F\}$.
\end{enumerate}
\end{Definition}

\begin{Definition}[Schaltung]
\noindent
\begin{itemize}
\item
Eine Transition $t$ ist \textcolor{blue}{aktiviert} (hat Konzession) in Markierung $m : S\rightarrow\mathbb{N}$:
\begin{equation*}
\forall s \in \bullet t: W((s,t)) \leq m(s)
\end{equation*}
\item
Eine Transition $t$ \textcolor{blue}{schaltet/feuert} in Markierung $m : P\rightarrow\mathbb{N}$ und führt zu $m^\prime$:
\begin{equation*}
\text{$t$ ist aktiviert in $m$}\,\land\,\forall s \in S: m^\prime(s) = m(s) - W((s,t)) + W((t,s))
\end{equation*}
Schreibweise: $m \overset{t}{\longrightarrow} m^\prime$
\end{itemize}
\end{Definition}

\begin{Definition}[Markierungen, Stellen, Transitionen]
\noindent
\begin{itemize}
\item
Eine Markierung $m^\prime$ ist \textcolor{blue}{erreichbar} von Markierung $m$, wenn es eine beliebige Transitionssequenz $w$ gibt, sodass $m\overset{w}{\longrightarrow}m^\prime$, also wenn $m\overset{*}{\longrightarrow}m^\prime$.
\item
Die Menge der von $m$ erreichbaren Markierungen ist
\begin{equation*}
R_N(m) = \{m^\prime \mid m\overset{*}{\longrightarrow}m^\prime\}
\end{equation*}
\item
Eine Transition $t$ ist \textcolor{blue}{tot} in Markierung $m$, wenn $t$ in keinem $m^\prime \in R_N(m)$ aktiviert ist.
\item
Eine Transition $t$ ist \textcolor{blue}{lebendig} in Markierung $m$, wenn von jedem $m^\prime \in R_N(m)$ ein $m^{\prime\prime}$ erreichbar ist, in dem $t$ aktiviert ist.
\item
Eine Stelle $s$ heißt \textcolor{blue}{$k$-beschränkt} in Markierung $m$, wenn gilt:
\begin{equation*}
\forall m^\prime \in R_N(m): m^\prime(s)\leq k
\end{equation*}
\end{itemize}
\end{Definition}

\begin{Definition}[Eigenschaften von Petri-Netzen]
\noindent
\begin{itemize}
\item
$N$ ist \textcolor{blue}{verklemmungsfrei}, wenn in jedem $m$ aus $R_N(m_0)$ mindestens eine Transition aktiviert ist.
\item
$N$ ist \textcolor{blue}{lebendig}, wenn alle Transitionen von $N$ lebendig sind.
\item
$N$ ist \textcolor{blue}{reversibel}, wenn von jedem $m \in R_N(m_0)$ $m:0$ erreichbar ist.
\item
$N$ ist \textcolor{blue}{$k$-beschränkt}, wenn jede Stelle von $N$ $k$-beschränkt ist.
\item
$N$ ist \textcolor{blue}{beschränkt}, wenn es ein $k$ gibt, sodass $N$ $k$-beschränkt ist.
\end{itemize}
\end{Definition}

\begin{Definition}[Zustandsmaschine]
Eine \textcolor{blue}{Zustandsmaschine} ist ein Petri-Netz, wo jede Transition genau einen Vor- und einen Nachplatz hat. Dies bedeutet, dass die Markenzahl konstant bleibt. Jede Zustandsmaschine ist also beschränkt. Eine Zustandsmaschine ist lebendig genau dann, wenn sie stark zusammenhängend ist und $\boldsymbol{m_0} > \boldsymbol{0}$ ist.
\end{Definition}

\begin{Definition}[Synchronisationsgraph]
Ein \textcolor{blue}{Synchronisationsgraph} ist ein Petri-Netz, wo jede Stelle genau eine Vor- und eine Nachtransition hat. In jedem Kreis eines Synchronisationsgraphen bleibt die Markenzahl konstant. Ein Synchronisationsgraph ist lebendig genau dann, wenn jeder Kreis initial markiert ist.
\end{Definition}

\begin{Definition}[Free-Choice-Netz]
Ein \textcolor{blue}{Free-Choice-Netz} ist ein Petri-Netz, wenn gilt: Wenn Transitionen Vorplätze teilen, teilen sie alle Vorplätze. Free-Choice-Netze sind konfusionsfrei.
\end{Definition}

\begin{Definition}[Siphons (Strukturelle Deadlocks)]
Ein nichtleere Stellen-Menge $D\subseteq S$ heißt \textcolor{blue}{Siphon}, falls $\bullet D \subseteq D\bullet$. Enthält ein Siphon in einer Markierung $m$ keine Marken, dann enthält er auch in allen von $m$ erreichbaren Markierungen keine Marken.
\end{Definition}

\begin{Definition}[Fallen/Traps]
Ein Stellen-Menge $Q\subseteq S$ heißt \textcolor{blue}{Falle}, falls $Q\bullet \subseteq \bullet Q$. Enthält eine Falle in einer Markierung $m$ Marken, dann enthält sie auch in allen von $m$ erreichbaren Markierungen Marken.
\end{Definition}

\begin{Satz}[Commoners Theorem]
Ein Free-Choice-Netz ist lebendig genau dann, wenn jeder Siphon eine initial markierte Falle enthält.
\end{Satz}

\section{Z-Notation}
Ausgangspunkt ist die Beschreibung von Mengen durch Angabe ihrer charakteristischen Eigenschaft.
\begin{schema}{Name}
\text{Deklaration}
\where
\text{Prädikat}
\end{schema}
Ein Schritt bezeichnet ein Schema mit ungestrichenen und gestrichenen Variablen.\\
Variablen, die auf $?$ enden, sind die Eingabe.\\
Variablen, die auf $!$ enden, sind die Ausgabe.\\

\begin{tabularx}{\linewidth}{XXX}
\multicolumn{1}{c}{\textbf{Schritt}}&\multicolumn{1}{c}{\textbf{Immer}}&\multicolumn{1}{c}{\textbf{Initialisierung}}\\
\begin{schema}{\Delta X}
X\\
X^\prime
\where
\end{schema}
&
\begin{schema}{\Xi X}
X\\
X^\prime
\where
\theta X = \theta X^\prime
\end{schema}&
\begin{schema}{XInit}
X^\prime
\where
\end{schema}\\
\end{tabularx}
\end{document}