Prof. Dr. Hans-Jörg Kreowski Mai 2003 Studiengang Informatik Universität Bremen OAS 3001 Tel.: 2956, 3697 (Sekr.), Fax: 4322 E-Mail: kreo@informatik.uni-bremen.de

Theoretische Informatik 2 (SS 2003)

Wie im Extra-Material versprochen, kann ein endlicher Automat konstruiert werden, der den Durchschnitt zweier Sprachen erkennt, die selbst von endlichen Automaten erkannt werden. Es wird außerdem gezeigt, dass das Leerheitsproblem für endliche Automaten entscheidbar ist.

1 Produktautomat erkennt Durchschnitt

Seien A_{i} = (Z_{i}, I, d_{i}, s_{0i}, F_{i}) für i = 1, 2 zwei deterministische Automaten. Dann ist der Produktautomat definiert durch

A_{1} × A_{2} = (Z_{1} × Z_{2}, I, d, (s_{01}, s_{02}), F_{1} × F_{2})

mit d((s_{1}, s_{2}), x) = (d_{1}(s_{1}, x), d_{2}(s_{2}, x)) für alle (s_{1}, s_{2}) ∈ Z_{1} × Z_{2} und x ∈ I. Der Produktautomat führt also die Zustandsübergänge der beiden Einzelautomaten parallel durch. Wie das folgende Lemma zeigt, gilt das auch für die fortgesetzte Zustandsüberführung. Da der Anfangszustand aus den beiden einzelnen Anfangszuständen und die Endzustände Paare der einzelnen Endzustände sind, ergibt sich aus dem Lemma die gewünschte Durchschnittseigenschaft.

Beobachtung: L(A_{1} × A_{2}) = L(A_{1}) ∩ L(A_{2}).

Beweis: w ∈ L(A_{1} × A_{2}) gdw. nach folgendem Lemma

d^{∗}((s_{01}, s_{02}), w) = (d_{1}^{∗}(s_{01}, w), d_{2}^{∗}(s_{02}, w)) ∈ F_{1} × F_{2}

gdw. d_{i}^{∗}(s_{0i}, w) ∈ F_{i} für i = 1, 2 gdw. w ∈ L(A_{i}) für i = 1, 2.

Lemma: d^{∗}((s_{1}, s_{2}), w) = (d_{1}^{∗}(s_{1}, w), d_{2}^{∗}(s_{2}, w)) für alle (s_{1}, s_{2}) ∈ Z_{1} × Z_{2} und w ∈ I^{∗}.

Beweis: Der Beweis wird mit vollständiger Induktion über den Aufbau von w geführt. IA: d^{∗}((s_{1}, s_{2}), λ) = (s_{1}, s_{2}) = (d_{1}^{∗}(s_{1}, λ), d_{2}^{∗}(s_{2}, λ)), wobei die Definition der fortgesetzten Zustandsüberführung verwendet wird.

IS: d^{∗}((s_{1}, s_{2}), wx) = d(d^{∗}((s_{1}, s_{2}), w), x) = d((d_{1}^{∗}(s_{1}, w), d_{2}^{∗}(s_{2}, w)), x) = (d_{1}(d_{1}^{∗}(s_{1}, w), x), d_{2}(d_{2}^{∗}(s_{2}, w), x) = (d_{1}^{∗}(s_{1}, wx), d_{2}^{∗}(s_{2}, wx)).

Dabei ergeben sich die Gleichheiten in der gegebenen Reihenfolge aus der Definition der fortgesetzten Zustandsüberführung, der Induktionsvoraussetzung, der Definition der Zustandsüberführung des Produktautomaten und erneut aus der Definition der fortgesetzten Zustandsüberführung.

2 Entscheidbarkeit des Leerheitsproblems

Sei A = (Z, I, d, s_{o}, F) ein deterministischer Automat. Sei

H(A) = {s ∈ Z | d^{∗}(s, w) ∈ F für einw ∈ I^{∗}}

die Menge aller Zustände, die zu Endzuständen führen. Dann gilt offensichtlich:

L(A) ≠ ∅ gdw. s_{0} ∈ H(A).

H(A) lässt sich folgermaßen iterieren: H_{0} = F und H_{i+1} = H_{i} ∪ {s ∈ Z | d(s, x) ∈ H_{i} für ein x ∈ I} sowie H(A) = H_{m} für kleinstes m mit H_{m+1} = H_{m}.

Nach Definition gilt: F = H_{0} ⊆ H_{1} ⊆ ⋯ ⊆ H_{i} ⊆ H_{i+1} ⊆ ⋯ ⊆ Z. Da Z endlich ist, können nur endlich viele dieser Inklusionen echt sein, so dass es m geben muss. Dann gilt auch H_{m+k} = H_{m} für alle k ∈ ℕ (einfache Induktion über k). Daraus folgt die gewünschte Gleichheit. Denn mit Induktion über i ergibt sich H_{i} ⊆ H(A):

IA: H_{0} = F ⊆ H(A) wegen d^{∗}(s, λ) = s ∈ F f.a. s ∈ F. IS: H_{i+1} = H_{i} ∪ {s ∈ Z | d(s, x) ∈ H_{i} für ein x ∈ I}

⊆ H(A) ∪ {s ∈ Z | d(s, x) ∈ H(A) für ein x ∈ I}

= H(A) ∪ {s ∈ Z | d^{∗}((d)s, x), w)) ∈ F für ein w ∈ I^{∗}, x ∈ I}
= H(A) ∪ {s ∈ Z | d^{∗}(s, xw) ∈ F für ein xw ∈ I^{∗}}
⊆ H(A) ∪ H(A) = H(A).

Insbesondere gilt H_{m} ⊆ H(A).

Betrachte umgekehrt s ∈ H(A). Dann gibt es w ∈ I^{∗} mit d^{∗}(s, w) ∈ F. Das impliziert s ∈ H_{length(w)}, wie eine einfache Induktion ergibt. Daraus folgt wie gewünscht: s ∈ H_{length(w)} ⊆ H_{m}.