4. Vorlesung

Allgemein zum Bestimmen von äuqivalenten Zuständen

Eingabe

DEA a, der nur erreichbare Zustände enthält

1. stelle eine Tabelle aller Zustandspaare \(\{ q, q' \}\) mit \(q \neq q'\) von a auf.
2. markiere alle Paare \(\{ q, q' \}\) mit \(q \in F \wedge q' \notin F\) (bzw. umgekehrt)
3. für jedes noch unmarkierte Paar \(\{ q, q' \}\) und jedes \(a \in \varSigma\) teste, ob \(\{ \delta(q,a), \delta(q', a) \}\) bereits markiert ist. Wenn ja markiere auch \(\{ q,q'\}\)
4. wiederhole Schritt (3) bis sich keine Änderungen mehr in der Tabelle ergeben.
5. alle noch unmarkierten Paare sind äuqivalente Zustände.

Korrektheit

1. es werden nur nicht-äquivalente Zustandspaare makiert.
2. der Algorithmus terminiert (es gibt nur endl. viele Paare)
3. bei Abbruch des Algorithmus sind alle nicht-äquivalenten Paare markiert:

Voraussetzung: Der Algorithmus endet nach m+1 Iterationen von Schritt 3.

Annahme: Ein nicht-äquivalentes Paar (p,q) ist noch nicht markiert. Wähle l > m +1 minimal aus, sodass

\[a: p \rightarrow^w F, a: q /rightarrow^w \notin F \wedge \mid w \mid = l\]

Sei w = u v mit \(\mid v \mid = m + 1\), so gilt:

\[a: p \rightarrow^u p' \rightarrow^v F, a: q \rightarrow^u q' \rightarrow^v \notin F\]

Das Paar (p’, q’) ist in der (m + 1) Iteration trennbar mit \(a: p' \rightarrow^v F, a: q' \rightarrow^v \notin F\), aber nicht in einer früheren Iteration (ansonsten wäre l nicht minimal). Daraus folgt, dass in der (m + 1) Iteration noch ein nicht-äquivalentes Paar gefunden wurde, woraus \(\ge (m + 2)\) Iterationen und daher ein Wiederspruch.

Es wurden die folgenden Definitionen eingeführt

• Äquivalenz ()
• Äquivalenz von Wörtern
• Index von

Satz von Nerode

Behauptung:

\(L \subset \varSigma^* \text{regulär} \Longleftrightarrow \text{Index von } \simeq_L \text{ ist endlich}\)

Beweis:

\(\Rightarrow\):

Sei a = (Q, \(\varSigma, q_0, \delta\), F) ein DEA, der L erkennt, so ist zu zeigen, dass verschiedene \(\simeq_L\)-Klassen in \(\varSigma^*\) bestimmen verschiedene \(\simeq_a\)-Klassen in Q.

Dann: \(\mid Q \mid \ge Index(\simeq_a) \ge Index(\simeq_L)\)

Seien \(u \not\simeq_L v\), d.h. \([u]_L \neq [v]_L\) gegeben. Bilde nun \(\delta(q_0, u), \delta(q_0,v)\) und \(\delta(q_0, u) \not\sim_a \delta(q_0,v)\).

Annahme: \(\delta(q_0, u) \sim_a \delta(q_0,v)\)

\[\begin{split}&\delta(q_0, u) \sim_a \delta(q_0,v) \\ & \forall w \in \varSigma^*: \delta(\delta(q_0, u), w) \in F \Longleftrightarrow \delta(\delta(q_0, v), w) \in F \\ & \forall w \in \varSigma^*: uw \in L \Longleftrightarrow vw \in L \\ & u \simeq_L v = WSP\\\end{split}\]

\(\Leftarrow\):

Sei Index (\(\simeq_L\)) endlich. Bilde DEA a, der L erkennt.

a = \((Q^\sim, \varSigma, q_0^\sim, \delta^\sim, F^\sim)\) mit

\(Q^\sim\) = Menge der \(\simeq_L\) - Äquivalenzklassen

\(q_0^\sim = [\varepsilon]\)

\(F^\sim = \{ [u] \mid u \in L \}\)

und \(\forall a \in \varSigma: \delta^\sim ([u], a) = [u a]\)

Beachte:

\(\forall w \in \varSigma^*: [u] = [v] \Longrightarrow [uw] = [vw]\)

Hieraus folgt: \(\delta^\sim\) ist wohldefiniert und es gilt ferner (per Induktion über \(\mid w \mid\)):

\(\forall w \in \varSigma^*: \delta^\sim([u], w) = [u w]\)

Dann gilt

\[\begin{split}w \in L(a) &\Longleftrightarrow \text{a akzeptiert w} \\ &\Longleftrightarrow \delta^\sim([\varepsilon], w) \in F^\sim \\ &\Longleftrightarrow [\varepsilon w ] = w \in F \\ &\Longleftrightarrow w \in L. \Rightarrow L(a) = L\end{split}\]

Satz:

Der kanonische DEA a ist isomorph zu jedem DEA \(a^\sim\), der gemäß dem Reduktionsverfahren aus einem belibigen DEA a, der L erkennt, entsteht.