Äquivalenzrelation und Minimalautomat 42

Definition Äquivalenzrelation 42

Es gilt $xR_{L}y$ genau dann, wenn für alle Wörter $z\in\Sigma^{*}$ gilt: $xz\in L\Leftrightarrow yz\in L$:

$$\left(xR_{L}y\right)\Leftrightarrow\left(\forall_{\Sigma^{*}}^{z}:xz\in L\Leftrightarrow yz\in L\right)$$

Mit Hilfe von $R_{L}$ wird die Sprache $L$ in disjunkte Äquivalenzklassen unterteilt. Wenn der Index von $R_{L}$ ( $\mathrm{Index}\left(R_{L}\right)$ ist die Anzahl solcher Äquivalenzklassen, siehe sub:=C4quivalenzklassen-&-Index) endlich ist, ist $L$ eine reguläre Sprache:

$$\left(\mathrm{Index}\left(R_{L}\right)<\infty\right)\Leftrightarrow L\in\mathcal{L}_{3}$$

Algorithmus Minimalautomat 46

Gegeben sei ein DFA $M=\left(Z,\Sigma,\delta,z_{0},E\right)$, der nach folgenden Algorithmus in eine Zustandsminimalen DFA $M'=\left(Z',\Sigma,\delta',z_{0},E'\right)$ überführt wird.

• entferne alle Zustände aus $Z$ die vom Startzustand aus nicht erreicht werden können.
• Stelle eine Kreuztabelle aller Zustandspaare $\left\{ z,z'\right\}$ mit $z\neq z'$ von $M$ auf (entspricht einer quadratischen Matrize, von der nur das ober/unter Dreieck ohne die Hauptdiagonale genommen wurde)
• Markiere alle Paare $\left\{ z,z'\right\}$ mit $z\in E$ und $z'\notin E$ (oder umgekehrt).
• Wiederhole folgendes, bis sich keine Änderung in der Tabelle mehr ergibt
  • Für jedes noch unmarkierte Paar $\left\{ z,z'\right\}$ und jedes $a\in\Sigma$ (es reicht, das dies für ein Terminal gilt) teste, ob $\left\{ \delta\left(z,a\right),\delta\left(z',a\right)\right\}$ bereits markiert ist. Wenn ja: markiere auch $\left\{ z,z'\right\}$
• Alle jetzt noch unmarkierten Paare können jeweils zu einem Zustand verschmolzen werden. Das heißt, das man wenn z.B. das Paar $\left(z,z'\right)$ nicht markiert ist, wird für beide zusammen ein neuer Zustand geschaffen.

Dieser Algorithmus hat (bei geeigneter Implementierung (siehe Hopcroft/Ullmann)) die Laufzeitkomplexität $O\left(n^{2}\right)$