Formale Sprachen
A heißt Alphabet $:\Leftrightarrow$ A ist eine endliche, nicht leere Menge aus Zeichen. w heißt Wort aus $A^ : \Leftrightarrow$ w ist eine endliche Aneinanderreihung von Zeichen aus A L heißt formale Sprache $: \Leftrightarrow L \subseteq A^$ G heißt formale Grammatik $: \Leftrightarrow G = (N, T, S, P)$ wobei:
- N die endliche Menge der Nichtterminalsymbole bezeichne,
- T die endliche Menge der Terminalsymbole mit $N \cap T = \emptyset$ bezeichne,
- $S \in N$ das Startsymbol,
- $P \subseteq N \times (N \cup T)^*$ die endliche Menge der Produktionen bezeichne.
Es seien $L_1$ und $L_2$ formale Sprachen und $n \in \mathbb{N}$. Dann:
$L_1 \cdot L_2 :\Leftrightarrow {w_1 w_2 | w_1 \in L_1 \land w_2 \in L_2}$ $L_1 \cup L_2 :\Leftrightarrow {w | w \in L_1 \lor w \in L_2}$ $L_1 \cap L_2 :\Leftrightarrow {w | w \in L_1 \land w \in L_2}$ $L_1 \setminus L_2 :\Leftrightarrow {w | w \in L_1 \land w \notin L_2}$ $L_1^0 :\Leftrightarrow { \varepsilon}$ $L_1^1 :\Leftrightarrow L$ $L_1^n :\Leftrightarrow L_1^{n-1} \cdot L_1$ $L_1^ :\Leftrightarrow \bigcup_{i=0}^\infty L_1^i$ $L_1^+ :\Leftrightarrow L_1^ \setminus L_1^0 = \bigcup_{i=1}^\infty L_1^i$
Kodierungstheorie
Seien $L_A, L_B$ formale Sprachen und $c: L_A \rightarrow L_B$.
c heißt codierung $: \Leftrightarrow$ c ist injektiv. $L_B$ heißt präfixfrei $: \Leftrightarrow \forall_{u, v, w \in L_B}: uv = w \Rightarrow u = \varepsilon \lor v = \varepsilon$
Sei $h:A \rightarrow B$ eine Abbildung. h heißt Homomorphismus $:\Leftrightarrow h(\varepsilon) = \varepsilon \land \forall_{x \in A} \forall_{w \in A*}: h(xw) = h(x)h(w)$
Abbildungen und Relationen
Seien A und B Mengen.
R heißt binäre Relation von A in B $:\Leftrightarrow R \subseteq A \times B$
Sei im Folgendem R eine binäre Relation von A in B.
R ist linkstotal $:\Leftrightarrow \forall_{a \in A} : \exists_{b \in B} : (a, b) \in R$ R ist rechtseindeutig $:\Leftrightarrow \forall_{a \in A} : \forall_{b_1, b_2 \in B: b_1 \neq b_2} : (a, b_1) \in R \Rightarrow (a, b_2) \notin R$ R heißt Abbildung $:\Leftrightarrow$ R ist linkstotal und rechtseindeutig. Für Abbildungen schreibt man auch: $R: A \rightarrow B$.
R heißt linkseindeutig $:\Leftrightarrow \forall_{(a_1, b_1) \in R} : \forall_{(a_2, b_2) \in R} : (a_1, b_1) \in R \Rightarrow (a_2, b_2) \notin R$ R heißt injektiv $:\Leftrightarrow$ R ist eine linkseindeutige Abbildung. R heißt rechtstotal $:\Leftrightarrow \forall_{b \in B} : \exists_{a \in A} : (a, b) \in R$ R heißt surjektiv $:\Leftrightarrow$ R ist eine rechtstotale Abbildung. R heißt bijektiv $:\Leftrightarrow$ R ist eine injektive und surjektive Abbildung
R heißt reflexiv $:\Leftrightarrow \forall_{x \in A} : (x, x) \in R$ R heißt symmetrisch $:\Leftrightarrow (x, y) \in R \rightarrow (y, x) \in R$ R heißt antisymmetrisch $:\Leftrightarrow (x, y) \in R \land (y, x) \in R \Rightarrow x = y$ R heißt transitiv $:\Leftrightarrow (x, y) \in R \land (y, z) \in R \Rightarrow (x, z) \in R$
R heißt Halbordnung $:\Leftrightarrow$ R ist reflexiv, antisymmetrisch und transitiv. Eine Halbordnung ist ein Spezialfall der Ordnungsrelation.
R heißt Äquivalenzrelation $:\Leftrightarrow$ R ist reflexiv, symmetrisch und transitiv.
Sei C eine Menge und $S \subseteq B \times C$. $S \circ R = {(x,z) \in M_1 \times M_3 | \exists y \in M_2: (x, y) \in R \land (y, z) \in S}$
Sei M eine Menge und $R \subseteq M \times M$ eine Halbordnung. Dann heißt M halbgeordnet bzw. $(M, R)$ halbgeordnete Menge. Sei $T \subseteq M$. $x \in T$ heißt minimales Element von T $:\Leftrightarrow$ Es gibt kein $y \in T$ mit xRy und $x \neq y$. $x \in T$ heißt kleinstes Element von T $:\Leftrightarrow$ $\forall_{y \in T}: xRy$. Das maximale Element und das größte Element werden analog definiert.
R heißt vollständige Halbordnung $:\Leftrightarrow$ R ist eine Halbordnung, besitzt ein kleinstes Element und jede aufsteigende Kette besitzt ein Supremum. R heißt Totalordnung $:\Leftrightarrow \forall_{a,b \in M} : aRb \lor bRa$
Sei $\equiv \subseteq M \times M$ eine Äquivalenzrelation, $f : M \rightarrow M$ eine Funktion und $\diamond$ eine binäre Operation auf der Menge M. $f$ heißt verträglich $: \Leftrightarrow \forall_{x,y \in M} : x \equiv y \Rightarrow f(x) \equiv f(y)$ $\diamond$ heißt verträglich $: \Leftrightarrow \forall_{x_1, x_2,y_1, y_2 \in M} : x_1 \equiv x_2 \land y_1 \equiv y_2 \Rightarrow x_1 \diamond y_1 \equiv x_2 \diamond y_2$
Komplexitätstheorie
Seien $f : \mathbb{N_0} \rightarrow \mathbb{R}^+, g : \mathbb{N_0} \rightarrow \mathbb{R}^+$ Funktionen, die die Laufzeit von Algorithmen beschreiben.
${\cal O}(f(n)) = {g(n) | \exists_{n_0 \in \mathbb{N}0} : \exists: g(n) \leq c \cdot f(n)}$ $\Omega(f(n)) = {g(n) | \exists_{n_0 \in \mathbb{N}}^+} : \forall_{n \geq n_00} : \exists: g(n) \geq c \cdot f(n)}$ $\Theta(f(n)) = \Omega(f(n)) \cap {\cal O}(f(n))$}^+} : \forall_{n \geq n_0
Graphentheorie
G heißt Graph $: \Leftrightarrow G = (V, E)$, wobei V eine endliche Menge an Knoten ist und $E \subseteq V \times V$ die Menge der Kanten bezeichne.
Sei G = (V, E) ein Graph. G heißt ungerichteter Graph $: \Leftrightarrow \forall_{v_n, v_m \in V} : (v_n, v_m) \in E \Rightarrow (v_m, v_n) \in E$ G heißt gerichteter Graph $: \Leftrightarrow$ G ist nicht ungerichtet. G heißt streng zusammenhängend $: \Leftrightarrow \forall_{x, y \in V}:$ Es gibt einen Pfad von x nach y. G heißt vollständig $: \Leftrightarrow \forall_{x, y \in V}: (x, y) \in E$
p heißt Pfad in G von $v_0$ nach $v_n: \Leftrightarrow p = (v_0, ..., v_n): \forall_{i \in \mathbb{G}n}: (v_i, v) \in E $
Ein Knoten $r \in V$ heißt Wurzel $: \Leftrightarrow \forall_{x \in V}:$ Es gibt genau einen Pfad von r nach x. G heißt Baum $: \Leftrightarrow \exists r \in V: \forall_{x \in V}$ Es gibt genau einen Pfad von r nach x.