Sprachen 186

Definition

Eine Teilmenge von $\Sigma^{*}$ wird als Sprache Bezeichnet. ( $A\in\Sigma^{*}$)

Rechenregeln

Da es sich bei Sprachen um Mengen handelt, gelten für sie (fast) alle Operatoren und Regeln der Mengen.

Eine Sprache lässt sich aus anderen Sprachen zusammensetzen (ähnlich Konkatenation). Dies bedeutet, das der ein Wort aus der neuen Sprache, aus den Teilen der anderen Sprachen zusammengesetzt wird.

• $A^{0}=\left\{ \varepsilon\right\}$
• $A^{1}=A$
• $A^{n+1}=AA^{n}$
• $A^{i}A^{j}=A^{i+j}$
• $\left(A^{i}\right)^{j}=A^{ij}$
• $A^{*}=\cup_{n\geq0}A^{n}$
• $A^{+}=\cup_{n\geq1}A^{n}$
• Menge aller Sprachen (Potenzmenge über $\Sigma^{*}$)
  $\mathcal{P}\left(\Sigma^{*}\right)=2^{\Sigma^{*}}=\left\{ A\vert A\subseteq\Sigma^{*}\right\}$

Relationen auf Sprachen 187

Eine zweistellige Relation zwischen $a$ und $b$ $\left(aRb\right)$ mit $R\subset\Sigma^{*}\times\Sigma^{*}$ ist wahr, wenn $\left(a,b\right)\in R$ und falsch, wenn $\left(a,b\right)\notin R$.

• Hintereinandschreiben von Relationen:
  $RS=\left\{ \left(x,y\right)\vert\exists_{\Sigma}^{z}:xRz\wedge zSz\right\}$
• $R^{0}=\left\{ x,x\vert x\in\Sigma^{*}\right\} =$ Identität
• $R^{n+1}=RR^{n}$
• $R=\cup_{n\geq0}R^{n}$
• $R^{+}=\cup_{n\geq1}R^{n}$
• $R$ heißt reflexiv wenn:
  $\forall_{\Sigma}^{x}:xRx$
• $R$ heißt transitiv wenn:
  $xRy\wedge yRz\Rightarrow xRz$
• $R^{*}$ ist die kleinste reflexive und transitive Relation, die $R$ umfasst (die reflexive und transitive Hülle von $R$)
  • kleiner als hoch $*$ geht es nicht, da $R$ sonst nicht transitiv wäre (es muss jede Hintereinanderausführung von zwei Realtionen enthalten)
  • $R^{0}$ muss enthalten sein, damit auch die Reflexivität gilt.
• $R$ heißt symmetrisch wenn:
  $xRy\Leftrightarrow yRx$
• $R$ heißt Äquivalenzrelation wenn:
  $R$ ist reflexiv und transitiv und symmetrisch

Äquivalenzklassen & Index

Jedem Element aus dem Grundbereich (hier: $\Sigma^{*}$) kann die Menge der Elemente zugeordnet werden, die zu $x$ äquivalent sind. Diese werden mit $\left[x\right]_{R}$ bezeichnet.

$$\left[x\right]_{R}=\left\{ y\vert yRx\right\} =\left\{ y\vert xRy\right\}$$

Wenn $R$ aus dem Kontext hervorgeht, schreiben wir auch einfach $\left[x\right]$. Diese Mengen heißen Äquivalenzklassen.

Die Grundmenge $\Sigma^{*}$ lässt sich in Äquivalenzklassen zerlegen:

$$\Sigma^{*}=\dot{\cup}_{k=0}^{n}\left[x_{k}\right]\quad\mathrm{Index}\left(R\right)=n$$

Mit $\mathrm{Index}\left(R\right)$ bezeichnen wir die Anzahl der verschiedenen Äquivalenzklassen, die $R$ hat.

• $\mathrm{Index}\left(R\right)$ ist die maximale Anzahl von Elementen $x_{1},x_{2},\ldots,x_{n},\ldots$ mit $\neg\left(x_{i}Rx_{j}\right)\ \left(i\neq j\right)$
• Falls $\mathrm{Index}\left(R\right)<\infty$ gilt, so sagen wir: $R$ hat einen endlichen Index