2. Vorlesung

Es wurden die folgenden Definitionen eingeführt

• Produktautomat

Lemma: \(L(a_1 X a_2) = L(a_1) \cap L(a_2)\)

\[\begin{split}&w = a_1 ... a_n \in L(a_1 X a_2) \\ &\Longleftrightarrow^{\text{Definition Akzeptierbarkeit}} \exists \text{ Pfad } (p_0, r_0) a_1 (p_1, r_1) a_2 ...... \text{ mit } \\ &(p_0, r_0) = (q_1, q_2), ((p_i, r_i), a_{i+1}, (p_{i+1}, r_{i+1})) \in \Delta \text{ und } (p_n, r_n) \in F \\ &\Longleftrightarrow^{\text{Def } \Delta, F} \exists \text{ Pfad } p_0 a_1 p_1 ... a_n p_n \text{ mit } p_0 = q_1, (p_i, q_{i + 1}, p_{i + 1}) \in \Delta_1, p_n \in F_1 \\ &\text{ und } \exists \text{ Pfad } p_0 a_1 p_1 ... a_n p_n \text{ mit } r_0 = q_2, (p_i, q_{i + 1}, p_{i + 1}) \in \Delta_2, p_n \in F_2 \\ &\Longleftrightarrow^{\text{Definition Akzeptierbarkeit}} w \in L(a_1) \text{ und } w \in L(a_2) \\ &\Longleftrightarrow w \in L(a_1) \cap L(a_2)\end{split}\]

Satz: Zu jedem NEA a mit Worttransitionen gibt es einen äquivalenten NEA a’.

Lemma 1: Zu jedem NEA a mit Worttransitionen gibt es einen \(\varepsilon\)-NEA a’ mit L(a) = L(a’).

Beweis:

Ersetze jede Transition \((p, a_1,...,a_n, q)\) in a mit \(n \ge 2\) durch Transitionen \((p, a_1, q_1), (p, a_2, q_2),...., (p, a_n, q_n)\) mit jeweils neuen Zuständen \(q_1,...,q_{n - 1}\).

Lemma 2: Zu jedem \(\varepsilon\)-NEA a gibt es einen äquivalenten NEA a’

Beweis:

Sei \(a = (Q, \varSigma, q_0, \Delta, F)\) ein \(\varepsilon\)-NEA. O.B.d.A gibt es keine Transitionen nach q_0. Wir definieren \(a' = (Q, \varSigma, q_0, \Delta', F')\) mit

\[\begin{split}&(p,a,q) \in \Delta' \Longleftrightarrow \exists \text{ ein Pfad } \Pi \text{ durch a von p nach q mit Beschriftung } p(\Pi) = a \\ &F' = F \cup \{ q_0 \} \text{ falls } a: q_0 \rightarrow^\varepsilon F, \text{ ansonsten F}\end{split}\]

Behauptung: L(a) = L(a’)

“<”: a akzeptiert w. Sei \(p_0 a_1 p_1 ... a_n p_n\) Pfad von \(q_0\) durch \(\varepsilon\)-NEA a nach F mit Beschriftung w. Seien \(a_{i_1},...,a_{i_n}\) die \(a_i \neq \varepsilon\) (mit \(i_1 < i_2 < ... < i_n\)) \(\Longrightarrow w = a_{i_1}, ..., a_{i_n}\)

Fall 1: \(w = 0 \Longrightarrow w = \varepsilon \Longrightarrow a: q_0 \rightarrow^\varepsilon F \Longrightarrow q_0 \in F'\) und a’ akzeptiert \(\varepsilon\).

Fall 2: \(w > 0\) Dann ist die folgende Folge ein Pfad durch a’: \(p_0 a_{i_1} p_{i_1} a_{i_2} p_{i_2}, ...., p_{i_{n - 1}} a_{i_n} p_{i_n}\) Dazu zeige

\[\begin{split}&(p_0, a_{i_1}, p_{i_1}) \in \Delta' \\ &(p_{i_1}, a_{i_2}, p_{i_2}) \in \Delta' \\ &...\\ &(p_{i_{n - 1}}, a_{i_n}, p_{i_n}) \in \Delta' \\\end{split}\]

\(\Longrightarrow w \in L(a')\)

“>” ist analog zu zeigen.

\[(q_0, a, q_1) \in \Delta' \Longleftrightarrow \exists \text{ Pfad } \Pi = q_0 \varepsilon q_1 a q_1, \beta(\Pi) = a\]

Verfahren zur Entscheidung ob \(\varepsilon\)-NEA \(a: p \rightarrow q\) mit Pfad \(\Pi\)

Hierzu reicht ein Verfahren zur Entscheidung, ob \(a: p \rightarrow^\varepsilon p'\) bzw \(a: q \rightarrow^\varepsilon q'\) für \(p', q' \in Q\) durch \(\varepsilon\) - Pfade.

Gegeben: \(\varepsilon\)-NEA \(a = (Q, \varSigma, q_0, \Delta, F)\) mit \(Q = \{ q_0, q_1,..., q_{n - 1} \}\)

Definiere \(\varepsilon_{ij} = 1 falls (q_i, \varepsilon, q_j) \in \Delta\) oder i = j, ansonsten 0

Gesucht: Werte \(c_{ij} \text{ mit } c_{ij} = 1 falls a: q_i \rightarrow^\varepsilon q_j\), ansonsten 0

Dazu berechne rekursiv

\[c_{ij}^{(r)} = 1 falls \exists \text{ Pfad von } q_i \text{ nach } q_j \text{ der Länge } \le r\]

Behauptung: \(c_{ij} = c_{ij}^{(n - 1)} \text{ für } n = \mid Q \mid\)

Zeige: Es existiert ein \(\varepsilon\) - Pfad von \(q_i\) nach \(q_j \nLeftrightarrow\) Es existiert ein \(\varepsilon\) - Pfad von \(q_i\) nach \(q_j\) der Länge \(\le n - 1\)

<= ist trivial

=>: Es sei \(\Pi\) ein \(\varepsilon\) - Pfad von \(q_i\) nach \(q_j\) minimaler Länge Zeige: Länge von \(\Pi\) ist \(\le n - 1\)

Annahme: \(\Pi = q_i = p_0 \varsigma p_1 \varsigma ... \varsigma p_m = q_j \wedge m \ge n\)

=> Es gibt eine Zustandswiederholung \(p_k = p_{k'}\) mit \(k \subset k'\)

=> Es gibt einen kürzeren \(\varepsilon\) - Pfad von \(q_i\) nach \(q_j\), was ein Wiederspruch zur Minimalität ist.

Wie berechnet man \(c_{ij}^{(r)}\)?

\[\begin{split}&c_{ij}^{(0)} = 1 \text{ falls } i = j, \text{ ansonsten } 0 \\ &c_{ij}^{(r + 1)} = c_{ij}^{(r)} \vee \bigvee_{k = 0}^{n - 1}(c_{ik}^{(r)} \wedge \varsigma_{kj})\end{split}\]

Das heißt es gibt einen Pfad von \(q_i\) nach \(q_j\) der Länge \(\le r + 1\), wenn es einen Pfad der Länge \(\le r\) gibt oder es gibt einen Zwischenknoten \(q_k\) und einen Pfad der Länge \(\le r\) von \(q_i\) nach \(q_j\) und eine \(\varepsilon\) - Transition \((q_k, \varepsilon, q_j) \in \Delta\)

Zeitaufwand

O(n^4), reduzierbar auf 0(n^3)