Automatentheorie

WS 1994/95 RWTH Aachen

Mitschrift

ii

Vorwort

Die vorliegende Mitschrift der Vorlesung “Automatentheorie”, gelesen von Prof. Dr. F. Baader im Wintersemester 1994/95 an der RWTH Aachen, ist genau das, was der Name sagt: Die geTEXte Form der Vorlesungsmitschrift einer unwissenden Studentin, angereichert mit einigen wenigen, nicht weiter gekennzeichneten privaten Ergänzungen (in der Regel triviale Beweise, auf die Prof. Baader in der Vorlesung verzichtet hat). Es ist wahrscheinlich, daß sich an der einen oder anderen Stelle Fehler eingeschlichen haben. (Verbesserungsvorschläge und “Fehlermeldungen” aller Art sind mir natürlich willkommen.) Deshalb ist dieses Schriftstück mit Vorsicht zu genießen und von mir nur als kleine Unterstützung für Leute gedacht, die sich mit der Vorlesung auseinandersetzen (wollen). Auf gar keinen Fall sollte es als “Skript” mißverstanden werden. Dies ist es nicht!

Aachen, März 1996 Claudia Krobb

e-mail: claudia@kawo2.rwth-aachen.de iv Inhaltsverzeichnis

Inhaltsverzeichnis

Motivation und Einordnung 1

1 Reguläre Sprachen, endliche Monoide und logische Formeln 5 1.1 Reguläre Sprachen und endliche Automaten . . . . . . . . . . . . . . . . . 5 1.2 Reguläre Sprachen und endliche Monoide . . . . . . . . . . . . . . . . . . 8 1.3 Reguläre Sprachen und logische Formeln . . . . . . . . . . . . . . . . . . 19

2 Verallgemeinert-definite Sprachen und quantorenfreie Formeln 23 2.1 Verallgemeinert-definite Sprachen . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Die zugehörige S-Varietät . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Quantorenfreie Formeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Sternfreie Sprachen 31 3.1 Die Sprachkasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Aperiodische Monoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Formeln der Logik erster Stufe . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3.1 Beweis von “1 ⇒ 2” von Satz 3.9 . . . . . . . . . . . . . . . . . . 35 3.3.2 Beweis von “ 2 ⇒ 1” von Satz 3.9 . . . . . . . . . . . . . . . . . . 35 3.3.3 Beweis der Sätze 3.12 und 3.16 . . . . . . . . . . . . . . . . . . . 39

3.4 Die Theorie der totalen Ordnung . . . . . . . . . . . . . . . . . . . . . . . 45

4 Unendliche Wörter und Büchi-Automaten 47

5 Unendliche Wörter und logische Formeln 65

6 Automaten auf endlichen Bäumen 85

7 Automaten auf unendlichen Bäumen 99

8 Baumautomaten und logische Formeln 111 vi Inhaltsverzeichnis

Motivation und Einordnung

Man ist interessiert an der Untersuchung von Sprachen und deren Eigenschaften. Unter den \underline{formalen Sprachen} versteht man die Menge L ⊆ Σ^{∗}, wobei Σ meist endlich ist. Eine Klasse K formaler Sprachen ordnet jedem (endlichen) Alphabet Σ eine Menge K_{Σ} ⊆ 2^{Σ^{∗}} zu, d.h. eine Menge von Sprachen über Σ. Drei Fragestellungen sind für solche Sprachen interessant

1.

Charakterisierungen Gesucht ist eine Eigenschaft E, die die Bedingung

L ∈ K_{Σ} gdwL ⊆ Σ^{∗} undL erfülltE

erfüllt. Meist sind verschiedene äquivalente Charakterisierungen gesucht.

2.

Abschlußeigenschaften Unter welchen Operationen auf Sprachen (Vereinigung, Komplement, homomorphe Bilder, ...) ist die Klasse abgeschlossen?

3.

Entscheidbarkeit Welche Fragestellungen (w ∈ L, L ≠ ∅, L_{1} ⊆ L_{2}, ...) sind für die Sprachklasse entscheidbar? Dabei geht man davon aus, daß die Sprachen durch eine der Charakterisierungen endlich beschrieben sind.

Beispiel 0.1 (Chomsky-Hierarchie)

Klasse  Charakterisierung

Typ 0 allgemeine Chomsky-Grammatiken (Regeln der Form u → v, u enthält mindestens ein Nonterminal) akzeptiert von Turing-Maschinen

Typ 1 (kontextsensitiv) kontexsensitive Grammatiken (Regeln der Form u → v, 1 ≤ |u| ≤ |v|) akzeptiert von Turing-Maschinen mit linearer Beschränkung

Typ 2 (kontextfrei) kontextfreie Grammatiken (Regeln der Form X → v, X ist Nonterminal) akzeptiert durch Kellerautomaten (PDA)

Typ 3 (regulär) rechtslineare Grammatiken (Regeln der Form X → uY oder X → u, u ist Terminalwort, X,Y sind Nonterminals) akzeptiert durch endliche Automaten

□

Beispiel 0.2 (Äquivalente Charakterisierungen) Liefern deterministische Automaten / Maschinen bereits die gesamte Sprachklasse?

Typ 0 ja
Typ 1 offen
Typ 2 nein
Typ 3 ja
□

Beispiel 0.3 (Abschlußeigenschaften am Beispiel Komplement) Fragestellung: Gilt L ∈ K_{Σ} ⇒ (Σ^{∗}\L) ∈ K_{Σ} ?

Typ 0 nein (Komplement einer rekursiv aufzählbaren Menge ist im allge-

meinen nicht rekursiv aufzählbar)

Typ 1 ja  (1987)
Typ 2 nein (⇒ L(DPDA) ≠ L(PDA))
Typ 3 ja
□

Beispiel 0.4 (Entscheidungsprobleme)

Elementproblem Äquivalenzproblem
w ∈ L  L_{1} = L_{2}
Typ 0 unentscheidbar  unentscheidbar
Typ 1 entscheidbar  unentscheidbar
Typ 2 entscheidbar  unentscheidbar
Typ 3 entscheidbar  entscheidbar

□

Inhalt der Vorlesung Die Vorlesung befaßt sich mit den Sprachen vom Typ 3, insbesondere mit ihren Unterklassen, verschiedenen Charakterisierungen und Verallgemeinerungen auf unendliche Wörter und Bäume. Hauptmotivation der Vorlesung sind Anwendungen der Ergebnisse in der Logik (z.B. Entscheidbarkeitsresultate).

• Teil 1 befaßt sich mit

– Regulären Sprachen endlicher Wörter – Charakterisierungen

∗ algebraische Charakterisierung Jeder Sprache kann ein Monoid (der syntaktische Monoid) zugeordnet werden. Reguläre Sprachen sind genau die Sprachen mit endlichem syntaktischen Monoid.

∗ logische Charakterisierung Logische Formeln können Sprachen definieren. Es gibt eine Logik (die monadische Logik 2-ter Stufe), deren Formeln genau die regulären Sprachen definieren.

Mit Hilfe dieser Charakterisierungen können Unterklassen der Klasse der regulären Sprachen definiert werden. Eine solche Unterklasse ist die Klasse der sternfreien Sprachen. Diese werden durch Formeln der Logik 1-ter Stufe definiert. Ihre syntaktischen Monoide sind genau die aperiodischen Monoide.

• Teil 2 befaßt sich mit Sprachen unendlicher Wörter. Statt endlicher Wörter (endliche Folgen von Elementen des Alphabets) kann man unendliche Wörter (unendliche Folgen) als Eingabe für einen endlichen Automaten betrachten. Die Akzeptanzbedingung muß dabei geändert werden. Für endliche Wörter wird das Wort durch Erreichen eines Endzustandes nach dem Lesen akzeptiert. Für unendliche Wörter wird eine Bedingung an die unendlich oft erreichten Zustände gestellt. Wir werden Abschlußeigenschaften, Entscheidbarkeit und den Zusammenhang zur Logik betrachten.

• Teil 3 befaßt sich mit Baumsprachen (Wäldern). Wörter können als beschriftete Bäume vom Verzweigungsgrad 1 aufgefaßt werden. Baumautomaten sind eine Verallgemeinerung von endlichen Automaten, die Bäume vom Verzweigungsgrad > 1 behandeln können. Viele Resultate für reguläre Sprachen lassen sich auf Baumsprachenübertragen. Auch hier ist der Zusammenhang zur Logik wichtig. Anstelle von endlichen Bäumen kann man auch unendliche Bäume betrachten.

4 Motivation und Einordnung

Kapitel 1

Reguläre Sprachen, endliche Monoide und logische Formeln

1.1 Reguläre Sprachen und endliche Automaten

Definition 1.1 Für ein endliches Alphabet Σ ist die \underline{Klasse der regulären Sprachen} Reg_{Σ} über Σ die kleinste Klasse mit

• ∅, {ε}, {a} mit a ∈ Σ sind in Reg_{Σ}

• Sind L_{1} und L_{2} aus Reg_{Σ}, so auch

– L_{1}∪ L_{2},

– L_{1}· L_{2} (= {uv | u ∈ L_{1},v ∈ L_{2}}),

– L_{1}^{∗} (={u_{1}...u_{n} | u_{i} ∈ L_{1},n ≥ 0}).

□

Wie üblich beschreiben wir reguläre Sprachen durch \underline{reguläre Ausdrücke}, bei denen Mengenklammern (und häufig auch Konkatenationspunkte) wegfallen. Zum Beispiel beschreibt (ab)^{∗}a den Ausdruck ({a} · {b})^{∗}· {a}. Aus der Definition ergibt sich Abschluß unter Vereinigung, Konkatenation und Stern. Um Abschluß unter Komplement und Durchschnitt zu zeigen ist die Charakterisierung durch endliche Automaten besser geeignet.

Definition 1.2 Ein \underline{nicht-deterministischer endlicher Automat} A = (Q,Σ,I,Δ,F) besteht aus

• einer endlichen Menge von Zuständen Q

• einem endlichen Alphabet Σ

• einer Menge I ⊆ Q von Anfangszuständen

• einer Übergangsrelation Δ ⊆ Q × Σ × Q

• einer Menge F ⊆ Q von Endzuständen.

Wie üblich werden Automaten graphisch dargestellt. Ein \underline{Pfad} in einem Automaten ist eine Folge q_{0}a_{1}q_{1}a_{2}q_{2}...a_{n}q_{n}, wobei für 1 ≤ i ≤ n gilt, daß (q_{i−1} ,a_{i},q_{i}) ∈ Δ. Abkürzend schreiben wir q_{0} −→^{a_{1}...a_{n}}_{A} q_{n}. Der Pfad ist \underline{erfolgreich}, falls q_{0} ∈ I und q_{n} ∈ F. Die von A \underline{akzeptierte Sprache} ist L(A) := \{w | q_{0} −→^{w} _{A} q_{n} ist erfolgreich\}.

□

Der \underline{Satz von Kleene} sagt, daß eine Sprache genau dann regulär ist, wenn sie von einem endlichen Automaten akzeptiert wird. Als Beispiel verwenden wir diese Charakterisierung, um Abschluß der Klasse der regulären Sprachen unter Durchschnitt zu zeigen.

Satz 1.3 Sind L_{1}, L_{2} ∈ Reg_{Σ}, so ist auch L_{1}∩ L_{2} ∈ Reg_{Σ}.

Beweis Es seien A_{1} = (Q_{1},Σ,I_{1},Δ_{1},F_{1}) und A_{2} = (Q_{2},Σ,I_{2},Δ_{2},F_{2}) Automaten mit L_{1} = L(A_{1}) und L_{2} = L(A_{2}). Wir definieren

A := (Q_{1}× Q_{2},Σ,I_{1}× I_{2},Δ,F_{1}× F_{2}),

wobei

Δ = {((q_{1},q_{2}),a,(q′_{1},q′_{2})) | (q_{1},a,q′_{1}) ∈ Δ_{1},(q_{2},a,q′_{2}) ∈ Δ_{2}}.

Man sieht leicht: (q_{1},q_{2}) −→^{w} _{A} (q′_{1},q′_{2}) gdw q_{1} −→^{w} _{A} q′_{1} und q_{2} −→^{w} _{A} q′_{2}.

Nach Definition der Anfangs- und Endzustandsmengen in A ist daher

w ∈ L(A) gdww ∈ L(A_{1}) ∩ L(A_{2}).
□

Um Abschluß unter Komplement zu zeigen, sind nicht-deterministische Automaten nicht gut geeignet. Beachte: Ist A = (Q,Σ,I,Δ,F) ein NEA mit L ⊆ L(A), so ist im allgemeinen \overline{A}= (Q,Σ,I,Δ,Q\F) kein Automat für \overline{L}:= Σ^{∗}\L. Zum Beispiel ist für A := (\{1,2\},\{a\},\{1\},Δ,\{1\}) mit Δ := \{(1,a,1),(1,a,2)\} L(A) = a^{∗}, L(\overline{A}) = a^{+} ≠ ∅ = \overline{L(A)}. Damit eine solche Konstruktion funktioniert, benötigt man deterministische Automaten.

Definition 1.4 Der Automat A = (Q,Σ,I,Δ,F) heißt \underline{deterministisch}, falls gilt:

• |I| = 1, d.h. I = {q_{0}}

• Δ ist funktional, d.h. für q ∈ Q und a ∈ Σ existiert genau ein q′∈ Q mit (q,a,q′) ∈ Δ

Statt der Übergangsrelation Δ verwendet man daher die \underline{Übergangsfunktion}

δ: Q × Σ → Q: (q,a) ↦ q′, wobei(q,a,q′) ∈ Δ.

Die Funktion δ kann auf Wörter erweitert werden: δ(q,w) := q′, wobei q′der eindeutig bestimmte Zustand ist, für den es einen Pfad q −→^{w} _{A} q′gibt. Es ist dann L(A) = {w | δ(q_{0},w) ∈ F }.

□

Durch die sogenannte \underline{Potenzmengenkonstruktion} kann jedem nicht-deterministischen Automaten effektiv ein deterministischer Automat zugeordnet werden, der dieselbe Sprache akzeptiert. Dazu sei A = (Q,Σ,I,Δ,F) ein nicht-deterministischer Automat. Wir definieren P(A) = (2^{Q},Σ,q_{0},δ′,F′) durch

• q_{0} := I

• δ′(P,a) := {q | ∃p ∈ P : (p,a,q) ∈ Δ}

• F′:= {P ⊆ Q | P ∩ F ≠ ∅}

Man sieht leicht, daß L(A) = L(P(A)) ist .

Satz 1.5 Ist L ∈ Reg_{Σ}, so auch \overline{L}:= Σ^{∗}\L ∈ Reg_{Σ}.

Beweis Sei L = L(A) für einen deterministischen Automaten A = (Q,Σ,q_{0},δ,F). Dann gilt:

w ∈ L gdw δ(q_{0},w) ∈ F
w ∉ L gdw δ(q_{0},w) ∉ F
w ∈ \overline{L} gdw δ(q_{0},w) ∈ Q\F

Das zeigt: \overline{A} = (Q,Σ,q_{0},δ,Q\F) ist ein Automat für \overline{L}.

□

Zu jeder regulären Sprache L exisitert ein (bis auf Zustandsumbenennung) eindeutiger deterministischer Automat A mit minimaler Zustandsanzahl und L = L(A). Dieser \underline{minimale Automat} kann wie folgt effektiv konstruiert werden: Es sei A = (Q,Σ,q_{0},δ,F) ein deterministischer Automat für L.

1. Entferne unerreichbare Zustände, d.h. Zustände q ∈ Q, für die kein w ∈ Σ^{∗} exisitiert mit δ(q_{0},w) = q.

2. Identifiziere \underline{äquivalente Zustände}. Für q ∈ Q sei L_{q}(A) = \{w | δ(q,w) ∈ F \}. Wir definieren q ∼_{A} q′gdw L_{q}(A) = L_{q′}(A). Die Relation ∼_{A} ist eine Äquivalenzreaktion. Faßt man äquivalente Zustände zusammen, so erhält man den minimalen Automaten.

Alternativ kann man auch mit Hilfe der \underline{Nerode-Rechtskongruenz} den minimalen Automaten beschreiben: Für eine (beliebige) Sprache L ∈ Σ^{∗} definieren wir

uρ_{L}v gdw∀w ∈ Σ^{∗} : uw ∈ L ⇔ vw ∈ L

(d.h. zwei Wörter sind äquivalent, wenn sie bei Multiplikation eines beliebigen Wortes von rechts beide in L oder beide nicht in L liegen). Diese Relation ist eine Äquivalenzrelation auf Σ^{∗} und es gilt (für alle u,v,w ∈ Σ^{∗}) uρ_{L}v ⇒ uwρ_{L}vw (Rechtskongruenz). Der \underline{Satz von Nerode} sagt aus, daß L genau dann regulär ist, wenn ρ_{L} endlichen Index hat (d.h. nur endlich viele Äquivalenzklassen besitzt).

Diese Klassen können nun als Zustände eines Automaten aufgefaßt werden. Für u ∈ Σ^{∗} bezeichne [u] := {v | uρ_{L}v} die ρ_{L}-Klasse von u. Wir definieren A_{L}:= (Q,Σ,q_{0},δ,F), wobei • Q:= {[u] | u ∈ Σ^{∗}}

• q_{0} := [ε]

• δ([u],a) := [ua] (repräsentantenunabhängig, da ρ_{L} Rechtskongruenz)

• F := {[u] | u ∈ L}

Für eine reguläre Sprache L ist A_{L} der minimale Automat für L.

1.2 Reguläre Sprachen und endliche Monoide

Ein \underline{Monoid} (M,·_{M},1_{M}) besteht aus einer nichtleeren Trägermenge M, einer assoziativen binären Operation ·_{M} und einem Einselement 1_{M}.

Assoziativ: (x ·_{M}y) ·_{M}z = x ·_{M}(y ·_{M}z) für alle x,y,z ∈ M
Einselement: x ·_{M}1_{M} = 1_{M}·_{M}x = x für alle x ∈ M

Wir werden meist M anstatt (M,·_{M},1_{M}) schreiben und häufig den Index M bei ·_{M} und 1_{M} weglassen. Ein Monoid heißt \underline{endlich}, wenn M (Trägermenge) endlich ist. Sind M,N Monoide, so heißt eine Abbildung Φ : M → N \underline{Homomorphismus}, falls gilt

• Φ(x ·_{M}y) = Φ(x) ·_{N}Φ(y)

• Φ(1_{M}) = 1_{N}.

Beispiel 1.6 Für ein Alphabet Σ ist die Menge Σ^{∗} aller Wörter über Σ zusammen mit Konkatenation als Operation · und mit dem leeren Wort ε als Einselement ein Monoid. Σ^{∗} heißt \underline{freies Monoid} über Σ, da es die folgende universelle Eigenschaft besitzt: Für jedes Monoid M und jede Abbildung f : Σ → M gibt es genau einen Homomorphismus Φ : Σ^{∗} → M mit Φ_{|Σ} = f.

□

Homomorphismen von Σ^{∗} in ein Monoid M können verwendet werden, um Sprachen über Σ zu definieren.

Definition 1.7 Es sei M ein Monoid, Σ ein Alphabet und Φ : Σ^{∗} → M ein Homomorphismus. Jede Teilmenge N ⊆ M definiert eine Teilmenge von Σ^{∗}:

Φ^{−1} (N) := {w ∈ Σ^{∗} | Φ(w) ∈ N}.

Die Sprache L ⊆ Σ^{∗} wird von M \underline{akzeptiert}, wenn es N ⊆ M und Φ : Σ^{∗} → M mit L = Φ^{−1} (N) gibt.

□

Satz 1.8 Für eine Sprache L ⊆ Σ^{∗} sind äquivalent:

1. L wird von einem endlichen Monoid akzeptiert

2. L ist regulär Beweis 1 ⇒ 2 Es sei Φ : Σ^{∗} → M mit der Eigenschaft L = Φ^{−1} (N) für N ⊆ M gegeben, wobei M endlich sei. Der deterministische endliche Automat A_{M} :=(M,Σ,1_{M},δ,N) mit der Übergangsfunktion δ(m,σ) := m ·_{M}Φ(σ) akzeptiert L. Dazu zeigt man:

Für allew ∈ Σ^{∗} und allem ∈ M giltδ(m,w) = m · Φ(w).  (1.1)

Beweis von (1.1) durch vollständige Induktion über |w|: Induktionsanker: |w| = 0 ⇒ w = ε Sei nun m ∈ M, dann gilt δ(m,w) = δ(m,ε) = m · Φ(ε) = m · Φ(w). Induktionsschluß: |w| = n + 1 Es seien w = v · σ, |v| = n, σ ∈ Σ, v ∈ Σ^{∗}. Dann gilt

δ(m,w)  =  δ(m,vσ)
=  δ(δ(m,v),σ)
=^{IV}  δ(m · Φ(v),σ)
=  m · Φ(v) · Φ(σ)
=^{Homomorphie} m · Φ(v · σ)
=  m · Φ(w)

Damit ergibt sich δ(1,w) = 1 · Φ(w) = Φ(w). Also gilt

w ∈ L = Φ^{−1} (N) gdw Φ(w) ∈ N
gdw δ(1,w) ∈ N
gdw w ∈ L(A_{M})

2 ⇒ 1 Es sei A = (Q,Σ,q_{0},δ,F) ein endlicher deterministischer Automat mit L = L(A). Offenbar definiert jedes w ∈ Σ^{∗} eine Funktion δ_{w}: Q → Q: q ↦ δ(q,w). Es sei M = Q^{Q} die Menge der Funktionen von Q nach Q. Da Q endlich ist, ist M auch endlich. Mit Komposition von Funktionen und der Identitätsfunktion ist M ein Monoid. Komposition: (δ_{1}∘ δ_{2})(q) = δ_{2}(δ_{1}(q)). Man sieht leicht, daß die Abbildung

Φ : Σ^{∗} → M : w ↦ δ_{w}

ein Homomorphismus ist, denn

1. Φ(ε) = δ_{ε}
= Q → Q: (q ↦ δ(q,ε))
= Q → Q: (q ↦ q)
= Id_{Q} = 1_{M}
2. Φ(v · w) = δ_{v·w}

= Q → Q: (q ↦ δ(q,vw))
= Q → Q: (q ↦ δ(δ(q,v),w))
= Q → Q: (q ↦ δ_{v}∘ δ_{w}(q))
= δ_{v}∘ δ_{w}
= Φ(v) ∘ Φ(w)

Wie muß N ⊆ M definiert werden? Gesucht ist ein N, das die folgende Bedingung erfüllt:

• w ∈ L(A) gdw Φ(w) ∈ N.

Dabei ist (w ∈ L(A) ⇔ δ_{w}(q_{0}) = δ(q_{0},w) ∈ F) und (Φ(w) ∈ N ⇔ δ_{w} ∈ N). Wir definieren daher: N := {δ_{w} | δ_{w}(q_{0}) ∈ F }. Damit gilt L(A) = Φ^{−1} (N).

□

Das Bild von Φ bezeichnet man als \underline{Übergangsmonoid} von A.

Definition 1.9 Für einen endlichen deterministischen Automaten A = (Q, Σ, q_{0}, δ, F) ist das \underline{Übergangsmonoid} von A das Untermonoid M_{A} := {δ_{w} | w ∈ Σ^{∗}} von M = Q^{Q}.

□

Definition 1.10 Für eine reguläre Sprache L heißt derÜbergangsmonoid des minimalen Automaten \underline{syntaktischer Monoid} von L. Wir bezeichnen diesen mit M_{L}. Da der minimale Automat eindeutig durch L bestimmt ist, hängt M_{L} nur von L ab.

□

Man kann M_{L} auch direkt, d.h. ohne Bezugnahme auf den minimalen Automaten, definieren.

Definition 1.11 Für eine beliebige Sprache L ⊆ Σ^{∗} ist die \underline{syntaktische Kongruenz} ∼_{L} auf Σ^{∗} definiert durch u ∼_{L} v gdw ( ∀x,y ∈ Σ^{∗} : xuy ∈ L gdw xvy ∈ L). Man zeigt leicht, daß ∼_{L}eine Kongruenzrelation ist, d.h. eineÄquivalenzrelation, die zusätzlich erfüllt:

∀u,v,x ∈ Σ^{∗} : u ∼_{L} v ⇒ \{ \begin{matrix}ux ∼_{L} vx \\ xu ∼_{L} xv \end{matrix}

Daher kann man den \underline{Quotientenmonoid} Σ^{∗}/ ∼_{L} bilden: Trägermenge: {[w]_{∼_{L}} | w ∈ Σ^{∗}} (Menge der Äquivalenzklassen von ∼_{L}), wobei

[w]_{∼_{L}} := {w′| w ∼_{L} w′}.

Operation : [u]_{∼_{L}} · [v]_{∼_{L}} := [uv]_{∼_{L}}

repräsentantenunabhängig, da ∼_{L} Kongruenzrelation ist Beweis: Seien u ∼_{L} u′und v ∼_{L} v′.

⇒  ∀x,y ∈ Σ^{∗} : xuy ∈ L gdw xu′y ∈ L und
∀x,y ∈ Σ^{∗} : xvy ∈ L gdw xv′y ∈ L
⇒  ∀x,y ∈ Σ^{∗} : xuvy ∈ L gdw xu′vy ∈ L gdw xu′v′y ∈ L
⇒  [uv]_{∼_{L}} = [u′v′]_{∼_{L}}
⇒  uv ∼_{l} u′v′

Einselement: [ε]_{∼_{L}}
□

Satz 1.12 Sei L regulär. Σ^{∗}/ ∼_{L} ist isomorph zum \underline{syntaktischen Monoid} M_{L}.

Beweis Es sei A = (Q,Σ,q_{0},δ,F) der minimale deterministische Automat für L. Wir definieren

\begin{aligned}ψ: & Σ^{∗}/ ∼_{L} & → & M_{L} \\ & [u]_{∼_{L}} & ↦ & δ_{u} \end{aligned}

Zu zeigen ist:

1. Repräsentantenunabhängigkeit( = Wohldefiniertheit, d.h. ψ ist Funktion): u ∼_{L} v ⇒ δ_{u} = δ_{v} Beweis: Es gelte u ∼_{L} v. Angenommen δ_{u} ≠ δ_{v}. Dann gibt es q ∈ Q mit

δ_{u}(q) = δ(q,u) = q_{1} ≠ q_{2} = δ(q,v) = δ_{v}(q).

Da A minimal ist, ist q erreichbar, d.h. es gibt ein x ∈ Σ^{∗} mit δ(q_{0},x) = q. Da u ∼_{L} v gilt, folgt für alle y ∈ Σ^{∗} : xuy ∈ L gdw xvy ∈ L. Das heißt aber für alle y:

δ(q_{1},y) = δ(q_{0},xuy) ∈ F gdwδ(q_{2},y) = δ(q_{0},xvy) ∈ F

d.h. L_{q_{1}}(A) = L_{q_{2}}(A) (zur Definition von L_{q} siehe Definition des minimalen Automaten). Da A minimal ist (nach Voraussetzung) folgt q_{1} = q_{2} (weil (L_{q_{1}} = L_{q_{2}} ⇒ q_{1} ∼_{A} q_{2}) ⇒ q_{1} = q_{2}, weil q_{1} und q_{2} bei der Minimierung des Automaten zusammengefaßt werden). Widerspruch

2. ψ ist injektiv, d.h. δ_{u} = δ_{v} ⇒ u ∼_{L} v Beweis: Es sei δ_{u} = δ_{v} und xuy ∈ L. Zu zeigen ist, daß aus diesen Bedingungen xvy ∈ L folgt. Es gilt xuy ∈ L ⇒ δ(q_{0},xuy) ∈ F. Für q_{1} := δ(q_{0},x) ist

δ(q_{0},xuy) = δ(q_{1},uy)
= δ_{y}(δ_{u}(q_{1}))
= δ_{y}(δ_{v}(q_{1})) (da δ_{u} = δ_{v})
= δ(q_{1},vy)
= δ(q_{0},xvy)

Es folgt δ(q_{0},xvy) ∈ F und damit xvy ∈ L. (Dies war xuy ∈ L ⇒ xvy ∈ L, xvy ∈ L ⇒ xuy ∈ L geht völlig analog.)

3. ψ ist surjektiv Beweis: δ_{u} ist das Bild von [u]_{∼_{L}} ausführlich: zu zeigen ist ∀y ∈ M_{L}: ∃x: ψ(x) = y Beweis: Sei y ∈ M_{L} beliebig aber fest. ⇒ ∃w ∈ Σ^{∗}: δ_{w}= y. Setze x = [w]. ⇒ ψ(x) = ψ([w]) =^{Def} δ_{w} = y ⇒ für alle y ∈ M_{L} existiert ein x mit ψ(x) = y. Dies ist aber gerade die Behauptung.

4. ψ ist Homomorphismus Beweis:

ψ([u]_{∼_{l}} · [v]_{∼_{L}} ) = ψ([u · v]_{∼_{L}} )
= δ_{uv}= δ_{u}∘ δ_{v}
= ψ([u]_{∼_{L}} ) ∘ ψ([v]_{∼_{L}} )
□

Korollar 1.13 L ist regulär gdw ∼_{L} hat endlichen Index.

Beweis “⇒”

M_{L} ist der Übergangsmonoid des minimalen Automaten, also endlich. Die Trägermenge von Σ^{∗}/ ∼_{L} sind die ∼_{L}-Klassen. Mit Satz 1.12 gilt, daß M_{L} isomorph zu Σ^{∗}/ ∼_{L} ist, also hat ∼_{L} endlichen Index.

“⇐”

L wird von Σ^{∗}/ ∼_{L} akzeptiert, denn für

Φ : Σ^{∗} → Σ^{∗}/ ∼_{L} : u ↦ [u]_{∼_{L}}

ist Φ^{−1} (Φ(L)) = L. Dazu muß man zeigen:

u ∈ L undu ∼_{L} v ⇒ v ∈ L.  (1.2)

Hat ∼_{L} endlichen Index, so ist Σ^{∗}/ ∼_{L} endlich. Mit Satz 1.8 folgt: L regulär.

□

Beispiel 1.14 (Berechnung des syntaktischen Monoids zu einer Sprache) Σ = {σ,τ}, � = Σ^{∗}στΣ^{∗}

1. Bestimmung eines nicht-deterministischen endlichen Automaten für L:

[figure: ⟲; ⟲; 1; 2; 3; σ, τ; σ, τ; τ; σ]

1.2 Reguläre Sprachen und endliche Monoide 13

2. Potenzmengenkonstruktion zur Erzeugung des äquivalenten deterministischen endlichen Automaten. Folgende Zusammenfassungen werden zur Vereinfachung vorgenommen: q_{1} := {1} q_{2} := {1,2} q_{3} := {1,3} q_{4} := {1,2,3}

[figure: ⟲; ⟲; ⟲; ⟲; q_{1}; q_{2}; q_{3}; q_{4}; σ; τ; σ; τ; τ; σ; σ; τ]

3. Minimierung: Zusammenfassung äquivalenter Zustände

Äquivalenzrelation ∼_{A} auf Zuständen:

q ∼_{A} q′gdwL_{q}(A) = L_{q′}(A)

Wir definieren die Relation ∼_{n} (n ≥ 0):

• q ∼_{0} q′gdw (q ∈ F und q′∈ F) oder (q ∉ F und q′ ∉ F)

• q ∼_{n+1} q′gdw q ∼_{n} q′und ∀σ: δ(q,σ) ∼_{n} δ(q′,σ) Da Q endlich ist, exisitiert ein k mit ∼_{k}=∼_{k+1}. Man zeigt leicht, daß ∼_{k}=∼_{A}.

Im Beispiel:

• ∼_{0} hat die Klassen \overline{F} = \{q_{1},q_{2}\} und F = \{q_{3},q_{4}\}

• ∼_{1} hat die Klassen {q_{1}}, {q_{2}}, {q_{3},q_{4}}

• ∼_{2}=∼_{1} Der minimale Automat ist somit

[figure: ⟲; ⟲; ⟲; p_{0}; p_{1}; p_{2}; τ; σ; σ, τ; τ; σ]

4. Bildung des Übergangsmonoids

Trägermenge: {δ_{u} | u ∈ Σ^{∗}} ⊆ Q^{Q}

δ_{ε} = \frac{p_{0} p_{1} p_{2}}{p_{0} p_{1} p_{2}}
(gelesen: von p_{0} mit ε nach p_{0} usw.)
δ_{σ} = \frac{p_{0} p_{1} p_{2}}{p_{1} p_{1} p_{2}} = δσσ
δ_{τ} = \frac{p_{0} p_{1} p_{2}}{p_{0} p_{2} p_{2}} = δττ
δ_{στ} = \frac{p_{0} p_{1} p_{2}}{p_{2} p_{2} p_{2}} = δ_{στ} für alleu ∈ Σ^{∗}

δ_{τσ} = \frac{p_{0} p_{1} p_{2}}{p_{1} p_{2} p_{2}}
δ_{τσσ} = \frac{p_{0} p_{1} p_{2}}{p_{1} p_{2} p_{2}} = δ_{τσ}
δ_{τστ} = \frac{p_{0} p_{1} p_{2}}{p_{2} p_{2} p_{2}} = δ_{στ}

Alle Möglichkeiten wurden ausprobiert, es ergab sich nichts neues. Es ist damit

M_{L} = {δ_{ε}, δ_{σ}, δ_{τ}, δ_{στ}, δ_{τσ}}.

Die Multiplikationstabelle ergibt sich aus den festgestellten Identitäten.

□

Beispiel 1.15 endlicher Monoid, der nicht syntaktischer Monoid einer regulären Sprache ist

M = \{1,a,b,c\} \begin{matrix}· & 1 & a & b & c \\ 1 & 1 & a & b & c \\ a & a & a & b & c \\ b & b & a & b & c \\ c & c & a & b & c \end{matrix}

a,b,c sind Rechtsnullen, d.h. ∀x ∈ M : x · a = a, x · b = b, x · c = c. Es läßt sich leicht nachrechnen, daß M Monoid ist. Angenommen ψ: M → Σ^{∗}/ ∼_{L} ist ein Isomorphismus, wobei L ⊆ Σ^{∗} eine reguläre Sprache ist. Wir wissen: u ∈ L ⇒ [u]_{∼_{L}} ⊆ L. (Erinnerung: u ∼_{L}v gdw ∀x,y: xuy ∈ L gdw xvy ∈ L.) Für m ∈ \{a,b,c\} gilt also: ψ(m) ⊆ L oder ψ(m) ⊆ \overline{L}. Wir betrachten den Fall ψ(a) ⊆ L und ψ(b) ⊆ L. (alle anderen Fälle, z.B. ψ(b) ⊆ \overline{L}, ψ(c) ⊆ \overline{L}, können entsprechend behandelt werden). Behauptung: Es folgt ψ(a) = ψ(b). (Dies wäre ein Widerspruch zu ψ Isomorphismus.) Beweis: Es sei ψ(a) = [u]_{∼_{L}} und ψ(b) = [v]_{∼_{L}} . Wir zeigen u ∼_{L} v. Seien dazu x,y ∈ Σ^{∗} beliebig.

1. Fall [y]_{∼_{L}} ≠ [ε]_{∼_{L}}

ψ^{−1} ([xuy]) = ψ^{−1} ([x] · [u] · [y])
= ψ^{−1} ([x]) · ψ^{−1} ([u]) · \underbrace{ψ^{−1} ([y])}_{≠1da[y]≠[ε])}

= ψ^{−1} ([y]) (da [y] Rechtsnull ist)
= ψ^{−1} ([x]) · ψ^{−1} ([v]) · ψ^{−1} ([y])
= ψ^{−1} ([xvy])

Daraus folgt[xuy] = [xvy], da ψ Isomorphismus ist. Also gilt xuy ∼_{L} xvy. Damit gilt insbesondere xuy ∈ L gdw xvy ∈ L und somit ist u ∼_{L} v.

2. Fall [y] = [ε] Dann ist

ψ^{−1} ([xuy]) = ψ^{−1} ([x]) · ψ^{−1} ([u]) · \underbrace{ψ^{−1} ([y])}_{=1}
= ψ^{−1} ([x]) · \underbrace{ψ^{−1} ([u])}_{=a, ψ(a)=[u]}

= ψ^{−1} ([x]) · a
= a

Entsprechend gilt

ψ^{−1} ([xvy]) = b

Da ψ(a) ⊆ L und ψ(b) ⊆ L folgt [xuy] ⊆ L und [xvy] ⊆ L und damit xuy ∈ L gdw xvy ∈ L. Also u ∼_{L} v. Insgesamt folgt der Widerspruch zur Annahme, daß M syntaktisches Monoid ist.

□

Der Zusammenhang zwischen regulären Sprachen und endlichen Monoiden kann dazu verwendet werden, Teilklassen der Klasse der regulären Sprachen zu definieren.

Definition 1.16 Es sei V eine Klasse endlicher Monoide. Wir definieren die zugehörige Klasse L(V) von Sprachen durch

L(V) := {L ⊆ Σ^{∗} | M_{L} ∈ V }.
□

L(V) ist eine Klasse von regulären Sprachen. Um “vernünftige” Klassen von Sprachen zu erhalten, muß man Klassen von Monoiden betrachten, die ebenfalls “vernünftige” Abschlußeigenschaften haben.

Definition 1.17 Eine nicht-leere Klasse V endlicher Monoide, die abgeschlossen ist unter Bildung von Untermonoiden, (binärer) direkter Produkte und homomorpher Bilder, heißt \underline{M-Varietät} .

□ Untermonoid N ⊆ M ist Untermonoid von (M,·,1), falls gilt:

• 1 ∈ N

• n, n′∈ N ⇒ n · n′∈ N

Abschluß unter Untermonoidbildung

• M ∈ V, N Untermonoid von M ⇒ N ∈ V

Direktes Produkt M_{1}× M_{2}

• (m_{1},m_{2}) × (m′_{1},m′_{2}) = (m_{1}· m′_{1},m_{2}· m′_{2})
• 1_{M_{1}×M_{2}} = (1_{M_{1}},1_{M_{2}})
M_{1}, M_{2} Monoide ⇒ M_{1}× M_{2} Monoid

Homomorphes Bild Ist Φ : M_{1} → M_{2} surjektiver Homomorphismus, so ist M_{2} homomorphes Bild von M_{1}.

Beispiel 1.18 Es sei V_{G} die Klasse aller endlichen Gruppen. Man zeigt leicht, daß V_{G} M-Varietät ist.

• Abschluß unter homomorphen Bildern und direktem Produkt ist trivial

• Untermonoidbildung:

Wir benötigen hier Endlichkeit. (Beispiel: (ZZ,+,0) ist Gruppe, (IN,+,0) ist Untermonoid, das keine Gruppe ist.) Im endlichen Fall: Es sei G eine endliche Gruppe und N ein Untermonoid von G. Warum ist für n ∈ N auch das Gruppeninverse n^{−1} ∈ N? Betrachte die Abbildung φ_{n} : N → N : m ↦ m · n. Diese Abbildung ist injektiv, da G Gruppe ist: In G gilt ja m · n = m′· n ⇒ m = m′. Da N endlich ist, ist φ_{n} auch surjektiv. Wegen 1 ∈ N gibt es daher n′∈ N mit φ_{n}(n′) = 1, das heißt n′·n = 1. Damit ist n^{−1} = n′∈ N.

□

Varietäten können auch mit Hilfe von Gleichungen definiert werden. Es sei X ein abzählbar unendliches Alphabet (von Variablen). Eine Gleichung ist von der Form

u = v mitu,v ∈ X^{∗} (stattε schreiben wir 1).

Ein Monoid M \underline{erfüllt} die Gleichung u = v gdw für jeden Homomorphismus Φ : X^{∗} → M gilt: Φ(u) = Φ(v).

Beispiel xy = yx (x,y ∈ X) wird genau von den kommutativen Monoiden erfüllt. Kommutativ: ∀m,n ∈ M : m · n = n · m. M erfülle xy = yx. Seien m,n ∈ M und sei Φ : X^{∗} → M Homomorphismus mit m = Φ(x), n = Φ(y). Dann gilt

m · n = Φ(x) · Φ(y) = Φ(xy) = Φ(yx) = Φ(y) · Φ(x) = n · m.  □

Definition 1.19 Es sei (u_{n} = v_{n})_{n≥1} eine Folge von Gleichungen. Die Klasse V von endlichen Monoiden wird \underline{schließlich definiert} von dieser Folge, falls es für alle M ∈ V je ein k gibt mit der Eigenschaft

M erfülltu_{n} = v_{n} für allen > k

und umgekehrt ist jedes M, das diese Eigenschaft hat, in V.

□

Satz 1.20 (Eilenberg/Schützenberg)

1. Jede M-Varietät kann durch Gleichungen schließlich definiert werden.

2. Umgekehrt ist jede durch Gleichungen schließlich definierte Klasse endlicher Monoide eine M-Varietät.

□

Beispiel 1.18 (Fortsetzung) Mit dem obigen Satz muß eine Folge von Gleichungen existieren, die die M-Varietät V_{G} definiert. Die M-Varietät V_{G} aller endlichen Gruppen wird schließlich definiert durch

(x\overline{n} = 1)_{n≥1}

wobei \overline{n}= kgV (1,...,n).

1. Es sei G ∈ V_{G}. Offenbar gilt für k = |G|, daß g^{k} = 1 für alle g ∈ G.

Für n ≥ k ist k ein Teiler von \overline{n}. Es folgt g\overline{n} = 1 für alle g ∈ G und damit erfüllt G die Gleichung x\overline{n} = 1 für alle n ≥ k.

2. Erfüllt G die Gleichung x\overline{n} = 1 (für irgendein n), dann ist G eine Gruppe: für g ∈ G ist g^{\overline{n}−1} Inverses zu g.

□

Aus den Abschlußeigenschaften für M-Varietäten ergeben sich Abschlußeigenschaften für die dadurch definierten Klassen von Sprachen. Wir betrachten nur die Booleschen Operatoren (Schnitt, Vereinigung, Komplement). Dazu benötigen wir ein Lemma:

Lemma 1.21 Es sei V eine M-Varietät und L ⊆ Σ^{∗} eine Sprache, die von M ∈ V akzeptiert wird. Dann ist M_{L} ≃ Σ^{∗}/ ∼_{L} ∈ V.

Beweis Da M die Sprache L akzeptiert, gibt es einen Homomorphismus Φ : Σ^{∗} → M und ein N ⊆ M mit L = Φ^{−1} (N).

1. Œ sei Φ surjektiv Dies ist keine Einschränkung, da man sonst den Untermonoid M′:= Φ(Σ^{∗}) von M als Bildraum von Φ nehmen kann. Mit N′:= N ∩ M′gilt

• L = Φ^{−1} (N′)

• M′∈ V (da M′Untermonoid von M ∈ V und V Varietät)

2. Sei also Φ : Σ^{∗} → M surjektiv. Definiert man

u ∼_{Φ} v gdwΦ(u) = Φ(v)

so gilt: ∼_{Φ} ⊆∼_{L}. denn (Beweis) Gelte u ∼_{Φ} v und sei xuy ∈ L. Dann ist Φ(xuy) ∈ N und

Φ(xvy) = Φ(x) · Φ(v) · Φ(y)
= Φ(x) · Φ(u) · Φ(y) (da Φ(u) = Φ(v) wegen u ∼_{Φ} v)
= Φ(xuy) ∈ N

Also folgt xvy ∈ L = Φ^{−1} (N). Damit ist ∼_{Φ} ⊆∼_{L} gezeigt.

3. Wir definieren nun ψ: M → Σ^{∗}/ ∼_{L} durch m ↦ [u]_{∼_{L}} falls Φ(u) = m. Wegen 2 (u ∼_{Φ} v ⇔ Φ(u) = Φ(v) = m ⇒ u ∼_{L} v) ist diese Definition repräsentantenunabhängig. Wegen 1 gibt es zu jedem m ein passendes u. Man sieht leicht, daß ψ surjektiver Homomorphismus ist. Also ist Σ^{∗}/ ∼_{L} homomorphes Bild von M ∈ V ⇒ Σ^{∗}/ ∼_{L}∈ V (da eine Varietät bezüglich der Bildung homomorpher Bilder abgeschlossen ist).

□

Satz 1.22 Es sei V M-Varietät. Dann ist L(V) – die Menge der Sprachen, deren syntaktischer Monoid in V liegt – abgeschlossen unter Vereinigung, Durchschnitt und Komplement.

Beweis Wir können uns auf Schnitt und Komplement beschränken, da die Abgeschlossenheit bezüglich Vereinigung daraus folgt.

1. Komplement: M_{Σ^{∗}\L} = M_{L} (dies gilt aufgrund der Definition von ∼_{L})

2. Durchschnitt: Es seien L, L′∈ L(V)_{Σ}, das heißt M_{L}= Σ^{∗}/ ∼_{L}∈ V und M_{L′}= Σ^{∗}/ ∼_{L′}∈

V. Es seien weiter

Φ : Σ^{∗} → Σ^{∗}/ ∼_{L}: u ↦ [u]_{∼_{L}}

und

Φ′: Σ^{∗} → Σ^{∗}/ ∼_{L′}: u ↦ [u]_{∼_{L′}}

die kanonischen Homomorphismen. Wir wissen (vergleiche den Beweis zu Korollar 1.13), daß für N = Φ(L) und N′= Φ′(L′) gilt L = Φ^{−1} (N) und L′= Φ^{−1} (N′). Wir definieren

ψ: Σ^{∗} → Σ^{∗}/ ∼_{L} ×Σ^{∗}/ ∼_{L′}∈ V (da V abgeschlossen ist bzgl. ×)
u ↦ (Φ(u),Φ′(u))

Dann ist

ψ^{−1} (N × N′) = {u | Φ(u) ∈ N und Φ′(u) ∈ N′}
= Φ^{−1} (N) ∩ Φ^{′−1}(N′)
= L ∩ L′

Also akzeptiert M = Σ^{∗}/ ∼_{L} ×Σ^{∗}/ ∼_{L′} die Sprache L ∩ L′. Wegen M ∈ V folgt mit Lemma 1.21, daß M_{L∩L′} ∈ V.

□

Es ist manchmal günstiger, \underline{Halbgruppen} statt Monoide zu betrachten. Eine Halbgruppe hat wie ein Monoid eine binäre assoziative Operation, aber im allgemeinen kein Einselement. Die bisher betrachteten Begriffe und Ergebnisse lassen sich auf Halbgruppen übertragen:

• \underline{syntaktische Halbgruppe}: Die syntaktische Kongruenz ∼_{L} ist auch eine Kongruenz auf der freien Halbgruppe Σ^{+} = Σ^{∗}\{ε}. Die syntaktische Halbgruppe S_{L} der Sprache L ist Σ^{+} / ∼_{L}. Alternativ bezeichnet man mit S_{A} die Übergangshalbgruppe {δ_{u} | u ∈ Σ^{+} } des minimalen Automaten A für L.

• \underline{S-Varietät} (“S” steht für “semigroup”): Abgeschlossen unter Unterhalbgruppenbildung, direktem Produkt und homomorphen Bildern. Beachte: Unterhalbgruppen von Monoiden müssen keine Untermonoide sein. S-Varietäten können ebenfalls schließlich durch Gleichungen definiert werden. Diese Gleichungen sind von der Form u = v, u,v ∈ X^{+} , das heißt Satz 1.20 gilt in einer Halbgruppenvariante 1.20S. S-Varietäten liefern eine feinere Aufteilung in Klassen. Zum Beispiel wird die Gleichung xy = x nur von dem trivialen Monoid erfüllt (1 · m = 1 ⇒ m = 1). Es gibt aber nicht-triviale Halbgruppen, die xy = x erfüllen.

• \underline{zugehörige Sprachklasse:} Für eine S-Varietät V ist

L(V)_{Σ} := {L ⊆ Σ^{∗} | S_{L} ∈ V }.

Lemma 1.21 und Satz 1.22 gelten ebenfalls in Halbgruppenvarianten 1.21S und 1.22S.

1.3 Reguläre Sprachen und logische Formeln

Wir verwenden im folgenden eine Logik mit Gleichheit, das heißt “=” ist ein binäres Prädikat, das als Identität interpretiert wird. Als nicht-logische Symbole verwenden wir eine binäre Relation “<”, sowie endlich viele einstellige Relationen P_{1},...,P_{k}. Wir betrachten \underline{endliche Interpretationen}, in denen “<” als \underline{totale Ordnung} definiert ist. Solche Interpretationen lassen sich als Wörter über dem Alphabet Σ = {0,1}^{k} auffassen.

• dom(I) = {d_{1},...,d_{n}}, wobei d_{1} < d_{2} < ... < d_{n}

• Sei σ_{i} = (b_{i_{1}},...,b_{i_{k}}), wobei

b_{i_{j}} = \{ \begin{matrix}1 d_{i} ∈ P_{j}^{I} \\ 0 d_{i} ∉ P_{j}^{I} \end{matrix}

dann entspricht die Interpretation I dem Wort σ_{1}...σ_{n}. Umgekehrt liefert jedes Wort über Σ eine Interpretation.

Beispiel 1.23 k = 1, das heißt Σ = {0,1}. In diesem Fall entspricht das Wort 010 einer Interpretation mit

• dom(I) = {d_{1},d_{2},d_{3}}

• d_{1} < d_{2} < d_{3}

• P_{1}^{I} = {d_{2}} (die zweite Stelle im Wort ist die einzige “1”)

□

Anstelle von Interpretationen werden wir im folgenden stets Wörter verwenden. Es macht daher Sinn, zu sagen, daß ein Wort w ∈ Σ^{+} Modell einer Formel φ ist (w ⊧ φ).

Definition 1.24 Es sei φ eine geschlossene Formel (d.h. φ enthält keine freien Variablen) der Logik erster Stufe, die als nicht-logische Symbole nur < und P_{1},...,P_{k} verwendet. Das Alphabet Σ sei {0,1}^{k}. Dann definiert φ die Sprache

L(φ) = {w ∈ Σ^{+} | w ⊧ φ}.
□

Da Interpretationen stets nichtleeren Bereich haben, entspricht das leere Wort keiner Interpretation. Das ist keine wesentliche Einschränkung, zum Beispiel ist L regulär gdw L\{ε} regulär ist.

Beispiel 1.25 k = 1, das heißt Σ = {0,1}. Die Sprache 11^{∗}0^{∗} wird definiert durch die Formel

∃x: (P_{1}(x) ∧ ∀y: (y ≤ x → P_{1}(y)) ∧ ∀z: (x < z → ¬P_{1}(z)))
□

Satz 1.26 Boolesche Operatoren in Formeln entsprechen Booleschen Operatoren auf Sprachen, das heißt

• L(¬φ) = Σ^{+} \L(φ),

• L(φ ∨ ψ) = L(φ) ∪ L(ψ),

• L(φ ∧ ψ) = L(φ) ∩ L(ψ).

□

Bei der Beschreibung von Sprachen durch logische Formeln sind die folgenden Abkürzungen hilfreich:

• Für jedes σ ∈ Σ kann man mit einer Formel mit einer freien Variablen – Q_{σ}(x) – ausdrücken, daß an der Stelle x das Symbol σ steht.

Zum Beispiel für k = 2, das heißt Σ = {(0,0),(0,1),(1,0),(1,1)} gilt

Q_{(1,1)}(x) entspricht P_{1}(x) ∧ P_{2}(x)
Q_{(1,0)}(x) entspricht P_{1}(x) ∧ ¬P_{2}(x)

• Durch eine Formel Min(x) kann man ausdrücken, daß x der Wortanfang ist:

¬∃y: y < x

• Entsprechend kann man Max(x) als das Wortende verwenden:

∀y: y ≤ x

• Die auf x folgende Stelle im Wort wird ausgedrückt durch

Succ(x,y) : (x < y ∧ ¬∃z(x < z ∧ z < y))

• Häufig verwendet man statt einer Formel “Succ(x,y)” eine Funktion “s”:

Für x ist s(x) die auf x folgende Position im Wort, falls diese existiert; sonst sei s(x) = x.

s(x) = y ˆ= Succ(x,y) ∨ (Max(x) ∧ x = y)

Entsprechend kann man anstelle von Formeln Max(x) und Min(x) Konstanten max und min verwenden.

• Wie den Nachfolger kann man auch den Vorgänger durch eine logische Formel Pred(x,y) oder eine Funktion p(x) beschreiben.

Beispiel 1.27 Die reguläre Sprache a(ba)^{∗} kann beschrieben werden durch Q_{a}(min) ∧ ∀x ∀y: (Q_{a}(x) ∧ Succ(x,y) → Q_{b}(y)) ∧ ∀x ∀y: (Q_{b}(x) ∧ Succ(x,y) → Q_{a}(y)) ∧ Q_{a}(max)

□

Welche Sprachen lassen sich durch Formeln der Logik erster Stufe beschreiben? Wir werden später sehen: Nur reguläre Sprachen sind so beschreibbar. Kann man alle regulären Sprachen L ⊆ Σ^{+} durch eine Formel der Logik erster Stufe beschreiben?

Beispiel 1.28 Die reguläre Sprache L = a(aa)^{∗} kann nicht durch eine Formel der Logik erster Stufe beschrieben werden. Wir werden später sehen, wie man das zeigt.

□

Erlaubt man Quantifizierungen über einstellige Prädikate, so kann man zum Beispiel L = a(aa)^{∗} durch eine Formel definieren. Als Variablen für einstellige Prädikate verwenden wir große Buchstaben (X, Y, Z,...) und als Variablen für Objekte (Positionen im Wort) wie bisher kleine Buchstaben (x, y, z,...).

Die Sprache L = a(aa)^{∗} kann nun beschrieben werden durch

∃X∃Y (X(min) ∧
∀x ∀y: (X(x) ∧ Succ(x,y) → Y (y)) ∧
∀x ∀y: (Y (x) ∧ Succ(x,y) → X(y)) ∧
X(max) ∧
∀x: (X(x) ↔ ¬Y (x)) ∧
∀x: Q_{a}(x))

Die Idee dabei ist, daß X für die ungeraden Positionen und Y für die geraden Positionen steht. X(max) besagt, daß die letzte Position ungerade ist, das heißt daß das Wort ungerade Länge hat.

Wir werden später sehen, daß man durch Formeln, die derartige Quantifizierungen zweiter Stufe zulassen, genau die regulären Sprachen beschreiben kann. In Kapitel 3 werden wir die Klasse von Sprachen untersuchen, die genau durch Formeln der Logik erster Stufe definiert werden können. Wir betrachten zunächst in Kapitel 2 eine kleinere Klasse von Sprachen: die durch quantorenfreie Formeln beschreibbaren Sprachen.

Verallgemeinert-definite Sprachen und quantorenfreie Formeln

Wir führen zunächst die Sprachklasse direkt ein und zeigen dann, wie man sie mit Hilfe von Halbgruppen und Formeln charakterisieren kann.

2.1 Verallgemeinert-definite Sprachen

Informell sind diese Sprachen dadurch charakterisiert, daß Zugehörigkeit eines Wortes zu der Sprache nur von den k ersten und den k letzten Buchstaben abhängt. Definition 2.1 Die Klasse B_{0} der \underline{verallgemeinert-definiten Sprachen} ist wie folgt definiert: L ⊆ Σ^{∗} gehört zu(B_{0})_{Σ} gdw es gibt ein k ≥ 0, so daß für alle w ∈ L gilt: Ist w = uv = v′u′ mit |u| = k = |u′|, so ist

uΣ^{∗}∩ Σ^{∗}u′⊆ L gdww ∈ L.
□

Ob ein Wort w′zu L gehört, hängt also nur von den ersten und letzten k Buchstaben ab.

Lemma 2.2 Für ein endliches Alphabet Σ ist (B_{0})_{Σ} der \underline{Boolesche Abschluß} der Sprachen

{uΣ^{∗} | u ∈ Σ^{∗}} ∪ {Σ^{∗}u′| u′∈ Σ^{∗}}

Beweis

1. Es sei L ∈ (B_{0})_{Σ} und k die in Definition 2.1 geforderte Zahl.

1. Fall k = 0 In diesem Fall ist L = Σ^{∗} oder L = ∅.

• für u = ε ist uΣ^{∗} = Σ^{∗}

• für beliebiges u ist uΣ^{∗}∩ \overline{uΣ^{∗}} = ∅ 2. Fall k > 0

In diesem Fall gilt

L = ( ⋃_{{|u|=k=|u′| \atop uΣ^{∗}∩Σ^{∗}u′⊆L}} uΣ^{∗}∩ Σ^{∗}u′) ⋃ \{v ∈ L | |v| < k\}

denn (Beweis)

“⊇” trivial “⊆” Es sei w ∈ L. Der Fall |w| < k ist trivial. Sei also |w| ≥ k. Damit gibt es

u, u′, v, v′mit w = uv = v′u′und |u| = k = |u′|. Aus w ∈ L und der Definition der verallgemeinert-definiten Sprachen folgt

\underbrace{uΣ^{∗}∩ Σ^{∗}u′}_{w∈} ⊆ L.

Es bleibt zu zeigen, daß {v ∈ L | |v| < k} im Booleschen Abschluß liegt. Es gilt aber

{v} = Σ^{∗}\vΣΣ^{∗}
= vΣ^{∗}\ ⋃_{σ∈Σ} vσΣ^{∗}

2. (a) Wir wollen zeigen, daß wΣ^{∗} ∈ (B_{0})_{Σ} Wähle dazu k = |w|. Offenbar ist

w = uv = v′u′∈ L = wΣ^{∗} (mit|u| = k = |u′|) gdwu = w.

Es ist daher uΣ^{∗}∩ Σ^{∗}u′⊆ L = wΣ^{∗} falls w = uv ∈ L.

(b) Σ^{∗}w kann entsprechend behandelt werden

(c) Abschluß von B_{0} unter Vereinigung Es seien L_{1} ∈ B_{0}, L_{2} ∈ B_{0} mit Zahlen k_{1}, k_{2}. Für L_{1}∪L_{2} kann man k:= max{k_{1},k_{2}} verwenden. Beachte: Ist u = u_{1}u_{2}, so ist u_{1}Σ^{∗} ⊇ uΣ^{∗}. Aus u_{1}Σ^{∗} ⊆ L folgt also uΣ^{∗} ⊆ L. Damit zeigt man leicht, daß k das Gewünschte leistet.

(d) Abschluß von B_{0} unter Komplement Es sei L ∈ B_{0} und k die entsprechende Zahl. Dieses k kann auch für \overline{L}verwendet werden. Es sei w = uv = v′u′∈ \overline{L}, wobei |u| = k = |u′| gelte. Wäre uΣ^{∗} ∩ Σ^{∗}u′ ⊈ \overline{L}, so gäbe es w′∈ uΣ^{∗} ∩ Σ^{∗}u′ mit w′∈ L. Daraus würde uΣ^{∗}∩ Σ^{∗}u′⊆ L folgen, was im Widerspruch zu w ∈ \overline{L}stünde. Damit wissen wir, daß \overline{L}verallgemeinert-definit ist mit der Zahl k.

□

2.2 Die zugehörige S-Varietät

Um diese \underline{S-Varietät}zu definieren, benötigen wir den Begriff des idempotenten Elements in einer Halbgruppe.

2.2 Die zugehörige S-Varietät 25

Definition 2.3 Es sei S eine Halbgruppe. Ein Element e ∈ S heißt \underline{idempotent} gdw e · e = e.

□

Offenbar ist ein Einselement immer Idempotent. Es kann aber noch weitere Idempotente geben.

Satz 2.4 Es sei S eine endliche Halbgruppe und m ∈ S. Dann enthält die Menge {m, m^{2}, m^{3}, ...} ein Idempotentes.

Beweis Da S endlich ist, existieren i,k ≥ 1 mit m^{i} = m^{i+k}.

[figure: m; m^{2}; m^{i}; m^{i+2}; m^{i+1}; m^{i+k−1}; ...]

Es existiert ein l mit den Eigenschaften

• i ≤ l < i + k, das heißt l = i + p mit p < k

• l ≡ 0 mod k, das heißt ∃ l′: l = kl′.

Behauptung: m^{l} ist idempotent, denn

m^{l} · m^{l} = m^{i+p} · m^{k·l′}
= m^{i}· m^{k·l′}· m^{p}
= m^{i}· m^{k}· m^{k·(l′−1)}· m^{p}
= m^{i+k} · m^{k·(l′−1)}· m^{p}
= m^{i}· m^{k·(l′−1)}· m^{p}
...
= m^{i}· m^{p}
= m^{i+p}
= m^{l}
□

Beachte: Sind m^{i}, m^{i+1} , ··· , m^{i+k−1} alle verschieden (d.h. ist k minimal gewählt), so ist {m^{i}, m^{i+1} , ..., m^{i+k−1} } eine zyklische Gruppe mit Einselement m^{l}.

Korollar 2.5 Es sei S eine endliche Halbgruppe, |S| ≤ n. Dann gilt für \overline{n} = kgV (1,...,n) und alle m ∈ S: m\overline{n} ist idempotent.

Beweis Offenbar findet man im Beweis des vorigen Satzes i, k mit i + k − 1 ≤ n. Es ist daher l ≤ n, wobei l wie im Beweis des Satzes gewählt wird. Somit gilt l | \overline{n}, das heißt es existiert ein l′

mit \overline{n}= l · l′. Damit ist m\overline{n} = \underbrace{(m^{l})}_{idempotent}^{l′}= m^{l}. □

Definition 2.6 Die Klasse ÎDbesteht aus allen endlichen Halbgruppen, für die gilt:

• Für alle Idempotenten e ∈ S (S ∈ ÎD) ist eSe = e, d.h. {e · s · e|s ∈ S} = {e}.

□

Satz 2.7 ÎDist eine S-Varietät, die schließlich definiert ist durch

x\overline{n}yx\overline{n} = x\overline{n} (n ≥ 1, \overline{n}= kgV (1,...,n))  (2.1)

Beweis Es genügt zu zeigen, daß ÎDschließlich von (2.1) definiert wird.

1. Es sei S ∈ ÎD. Mit Korollar 2.5 ist für n ≥ |S| und m ∈ S stets m\overline{n} idempotent. Aus der Definition von ÎDfolgt damit für alle m′∈ S : m\overline{n}· m′· m\overline{n} = m\overline{n}. Also erfüllt S (2.1) schließlich.

2. Gilt in S die Gleichung (2.1) für ein n, so gilt für alle Idempotenten e ∈ S und alle

m ∈ S:

eme = e\overline{n}me\overline{n} =^{(2.1)} e\overline{n} = e,

also ist eSe = e.
□

Lemma 2.8 Es sei S ∈ ÎD. Dann gilt

1. Für n > |S| und m_{1},...,m_{n} ∈ S ist m_{1}· m_{2}· ...· m_{n} idempotent.

2. Sind e,f ∈ S idempotent und ist m ∈ S, so gilt emf = ef.

Beweis

1. Betrachte m_{1}, m_{1}m_{2}, m_{1}m_{2}m_{3}, ..., m_{1}m_{2}m_{3}...m_{n}. Wegen n > |S| gibt es i und j mit

i < j und

m_{1}...m_{i} = m_{1}...m_{i}m_{i+1} ...m_{j}.  (2.2)

Mit Satz 2.4 existiert ein l mit (m_{i+1} ...m_{j})^{l} =: e idempotent.

m_{1}...m_{n} =  m_{1}...m_{i}m_{i+1} ...m_{j}m_{j+1} ...m_{n}
=^{(2.2)} m_{1}...m_{i}(m_{i+1} ...m_{j})^{l}m_{j+1} ...m_{n}
=^{eSe=e} m_{1}...m_{i} \underbrace{(m_{i+1} ...m_{j})^{l}}_{e}\underbrace{m_{j+1} ...m_{n}m_{1}...m_{i}}_{s}\underbrace{(m_{i+1} ...m_{j})^{l}}_{e}m_{j+1} ...m_{n}
=^{(2.2)} m_{1}...m_{i}m_{i+1} ...m_{j}m_{j+1} ...m_{n}m_{1}...m_{i}m_{i+1} ...m_{j}m_{j+1} ...m_{n}
=  m_{1}...m_{n}m_{1}...m_{n}

2.

emf = \underbrace{efe}_{∈eSe}mf = e\underbrace{femf}_{∈fSf} = ef

□

Satz 2.9 L(ÎD) = B_{0}, d.h. für L ⊆ Σ^{∗} : S_{L} ∈ ÎDgdw L ∈ (B_{0})_{Σ}.

Beweis

“⊇” Es sei L ∈ (B_{0})_{Σ}, das heißt mit Lemma 2.2 ist L im Booleschen Abschluß der Spra-

chen

{uΣ^{∗}|u ∈ Σ^{∗}} ∪ {Σ^{∗}u′|u′∈ Σ^{∗}}

Nach Satz 1.22S ist L(ÎD) unter Booleschen Operationen abgeschlossen. Es genügt also zu zeigen, daß uΣ^{∗} und Σ^{∗}u′in L(ÎD) liegen. Wir beschränken uns auf den Fall L = uΣ^{∗}. Es sei n = |u|.

1. Fall n = 0, d.h. L = Σ^{∗} Dann ist ∼_{L}= Σ^{∗}× Σ^{∗} und somit besteht S_{L} = Σ^{+} / ∼_{L} aus einer einzigen Klasse, die offenbar idempotent ist. Es folgt S_{L} ∈ ÎD.

2. Fall n > 0 Behauptung: Ist |w| ≥ n, so gilt für alle v ∈ Σ^{∗} : wv ∼_{L} w denn (Beweis) Für alle x,y ∈ Σ^{∗} gilt

xwvy ∈ L = uΣ^{∗} ⇔ xwvy beginnt mitu
(|w| ≥ |u|) ⇔ xw beginnt mitu
⇔ xwy beginnt mitu
⇔ xwy ∈ L = uΣ^{∗}

Endes des Beweises der Behauptung Es sei nun e = [x]_{∼_{L}} ∈ S_{L} = Σ^{+} / ∼_{L} idempotent. Wegen |x| ≥ 1 ist |x^{n}| ≥ n und damit erfüllt w = x^{n} die Voraussetzung der Behauptung. Daher gilt für alle m = [y]_{∼_{L}} ∈ S_{L}:

eme = e^{n}me
= [x^{n}]_{∼_{L}} [y]_{∼_{l}} e
= [x^{n}y]_{∼_{L}} e
(mit Beh. ist x^{n}y ∼_{L} x^{n}) = [x^{n}]_{∼_{L}} e
= e^{n}e
(e ist idempotent) = e

Also gilt S_{L} ∈ ÎD.

“⊆” Es sei S_{L} ∈ ÎD, n = |S_{L}| + 1. Mit Lemma 2.8(1) gilt für alle Wörter u der Länge n, daß [u]_{∼_{L}} idempotent ist:

u = σ_{1}...σ_{n} [u]_{∼_{L}} = [σ_{1}]_{∼_{L}} ...[σ_{n}]_{∼_{L}}

Es sei nun x ∈ L mit |x| ≥ 2n. Dann ist x = uvu′für |u| = n = |u′|. Außerdem gilt, daß [u]_{∼_{L}} und [u′]_{∼_{L}} idempotent sind. Mit Lemma 2.8(2) gilt für alle Wörter w:

[u]_{∼_{L}} · [w]_{∼_{L}} · [u′]_{∼_{L}}= [u]_{∼_{L}} · [u′]_{∼_{L}}
= [u]_{∼_{L}} · [v]_{∼_{L}} · [u′]_{∼_{L}}

Also gilt uwu′∼_{L} \underbrace{uvu′}_{∈L da x∈L} und damit auch uwu′∈ L.

Das zeigt: uΣ^{∗}u′⊆ L. Damit ist

L = ⋃_{{uΣ^{∗}u′⊆L \atop |u|=n=|u′|}} uΣ^{∗}u′ ∪ \underbrace{\{w|w ∈ L und |w| < 2n\}}_{endliche Vereinigung von Einermengen \{w\}}.

Wir wissen bereits, daß Einermengen in B_{0} sind:

{w} = wΣ^{∗}\ ∪_{σ∈Σ} wσΣ^{∗}.

Es bleibt zu zeigen: uΣ^{∗}u′∈ B_{0}. Dazu:

uΣ^{∗}u′= \underbrace{uΣ^{∗}}_{∈B_{0}}∩\underbrace{Σ^{∗}u′}_{∈B_{0}}\\underbrace{\{w | |w| < 2n\}}_{∈B_{0}}.

□

Korollar 2.10 Es sei L eine reguläre Sprache (gegeben durch einen regulären Audruck, einen endlichen Automaten etc.). Dann kann man effektiv entscheiden, ob L ∈ B_{0} gilt oder nicht.

Beweis Zu L kann man effektiv die syntaktische Halbgruppe S_{L} konstruieren. Für diese (endliche) Halbgruppe kann man überprüfen, ob für alle Idempotenten e gilt, daß eS_{L}e = e oder nicht.

□

2.3 Quantorenfreie Formeln

Als nicht-logische Symbole verwenden wir zusätzlich zu der binären Relation < und den unären Relationen P_{1}, P_{2},..., P_{k} die Konstanten min und max sowie die Funktionssymbole s und p. Die Interpretation dieser Symbole sei wie in Abschnitt 1.3 fixiert. Es sei Σ = {0,1}^{k}. Für σ ∈ Σ verwenden wir die Formeln Q_{σ}(x) als Abkürzung. Beachte: Im Abschnitt 1.3 haben wir gesehen, daß man die zusätzlichen Symbole min, max, s und p auch durch Formeln ausdrücken kann, die nur =, < und P_{1}, ..., P_{k} enthalten. Diese Formeln enthalten aber Quantoren. Satz 2.11 Für L ⊆ Σ^{∗} sind äquivalent:

1. L ∈ B_{0}

2. L\{ε} = L(φ) für eine quantorenfreie geschlossene Formel φ, die nur die nichtlogischen Symbole <, P_{1}...P_{k}, min, max, s und p enthält.

Beachte: Da {ε} ∈ B_{0} gilt, ist L ∈ B_{0} gdw L\{ε} ∈ B_{0}.

Beweis “1 ⇒ 2” Da Disjunktion der Vereinigung und Negation dem Komplement entspricht, genügt es mit Lemma 2.2, Sprachen uΣ^{∗} und Σ^{∗}u′zu betrachten. Zu uΣ^{∗} konstruieren wir die zugehörige Formel wie folgt:

1. Fall u = σ_{1}...σ_{l} mit l ≥ 1

Q_{σ_{1}}(min) ∧ Q_{σ_{2}}(s(min)) ∧ ...∧ Q_{σ_{l}}(s^{l−1} (min)) ∧ s^{l−2} (min) < max

2. Fall u = ε, das heißt L\{ε} = Σ^{+} Man kann eine beliebige Formel nehmen, die immer wahr ist, zum Beispiel min = min. “1 ⇐ 2” Es sei φ eine geschlossene, quantorenfreie Formel über den zur Verfügung stehenden Symbolen. Offenbar enthält φ keine Variablen. \underline{Terme} sind aufgebaut aus min, max, p, s. Diese können normalisiert werden zu:

{s^{n}(min) n ≥ 0 \atop p^{n}(max) n ≥ 0}\} es werden keine weiteren Formeln benötigt

Dazu verwendet man s(max) = max, p(min) = min, s(p(d)) = d und p(s(d)) = d (außer an den Extremalpunkten min und max). Die Formel φ ist daher Œ Boolesche Kombination von atomaren Formeln der Formen

P_{i}(t), t = t′, t < t′, t ≤ t′, ¬P_{i}(t)

wobei t und t′normalisiert sind. Beachte: ¬(t = t′) ˆ= (t < t′) ∨ (t′< t) und ¬(t < t′) ˆ= t′≤ t. Es genügt für jede dieser atomaren Formeln zu zeigen, daß die akzeptierte Sprache in B_{0} ist.

• P_{i}(s^{n}(min)) wird erfüllt von – Wörtern der Länge ≤ n (mit bestimmten Eigenschaften), d.h. von endlichen

Mengen von Wörtern. Endliche Wortmengen sind aber immer in B_{0}, da sie Vereinigung von Einermengen sind

– Wörter der Länge > n, die als (n+1)-tes Symbol ein σ ∈ {0,1}^{k} haben, für das die i-te Komponente 1 ist:

⋃_{{|u|=n \atop σ hat i−te Komponente 1}}uσΣ^{∗} ∈ B_{0}

• entsprechend können P_{i}(p^{n}(max)) und die negierten Formeln ¬P_{i}(p^{n}(max)), ¬P_{i}(s^{n}(min)) behandelt werden.

• Formeln t = t′, t < t′ und t ≤ t′ sind entweder von allen Wörtern erfüllt oder sie schränken die Wortlänge ein:

– s^{n}(min) = s^{m}(min) für n < m sagt, daß das Wort Länge ≤ n + 1 hat, d.h. die Formel kann nur von einer endlichen Wortmenge erfüllt werden. Diese sind aber in B_{0}.

– s^{n}(min) < s^{m}(min) für n < m sagt, daß das Wort Länge > n+1 hat. Die Komplementmenge (Wörter der Länge ≤ n+1) ist endlich, also in B_{0}. Da B_{0} bezüglich den Booleschen Operationen abgeschlossen ist, liegt also auch die durch obige Formel beschriebene Menge in B_{0}.

– p^{n}(max) ≤ s^{m}(min) ergibt eine Wortlänge ≤ n + m + 1 (vergleiche Skizze). Damit hat man wieder eine endliche Wortmenge, die in B_{0} liegt.

[figure: ...; ...; s; s^{m}; s^{m+1}; p; p^{n}; min; max; m; n]
□

Sternfreie Sprachen

Die \underline{sternfreien Sprachen} sind genau die Sprachen, welche von den Formeln der Logik erster Stufe akzeptiert werden.

3.1 Die Sprachkasse

Die Klasse der regulären Sprachen erhält man, indem man mit endlichen Sprachen beginnt und dann den Abschluß unter

• Vereinigung (L_{1}∪ L_{2})

• Konkatenation (L_{1}· L_{2})

• Stern (L^{∗})

bildet. Würde man hier den Stern-Operator verbieten, so könnte man keine unendlichen Mengen erzeugen. Reguläre Sprachen sind außerdem unter Durchschnitt und Komplement abgeschlossen.

Definition 3.1 Für ein endliches Alphabet Σ ist die Klasse der \underline{sternfreien Sprachen} (SF)_{Σ} über Σ die kleinste Klasse mit

• alle endlichen Sprachen über Σ sind in (SF)_{Σ}

• sind L_{1}, L_{2}, L ∈ (SF)_{Σ}, so auch L_{1} ∪ L_{2}, L_{1} ∩ L_{2}, Σ^{∗}\L, L_{1} · L_{2} (d.h. Vereinigung, Schnitt, Komplement und Konkatenation).

□

Beispiel 3.2

1. Σ^{∗} ∈ (SF)_{Σ}, denn Σ^{∗} = \overline{∅}

2. Ist Δ ⊆ Σ und sind Δ und Σ endlich, so ist Δ^{∗} ∈ (SF)_{Σ}, denn

Δ^{∗} = Σ^{∗}\Σ^{∗}· (Σ\Δ) · Σ^{∗}
= \overline{\overline{∅}· (Σ ∩ \overline{Δ}) · \overline{∅}}

3. Für Σ = {a,b} ist a(ba)^{∗} ∈ (SF)_{Σ}:

a(ba)^{∗} = a · (Σ^{∗}\(a · Σ^{∗}∪ Σ^{∗}· b ∪ Σ^{∗}· a · a · Σ^{∗}∪ Σ^{∗}· b · b · Σ^{∗}))
= a · \overline{a · Σ^{∗}∪ Σ^{∗}· b ∪ Σ^{∗}· a · a · Σ^{∗}∪ Σ^{∗}· b · b · Σ^{∗}}
□

Kann man einer regulären Sprache (gegeben durch einen endlichen Automaten, regulären Ausdruck, etc.) ansehen, ob sie sternfrei ist? Konkreter: Wie zeigt man, daß zum Beispiel a(aa)^{∗} nicht sternfrei ist? Man kann dazu die Charakterisierung der sternfreien Sprachen mit Hilfe von endlichen Monoiden verwenden.

3.2 Aperiodische Monoide

In Kapitel 2 hatten wir gesehen, daß für ein Element m einer endlichen Halbgruppe die Menge {m, m^{2}, m^{3}, ...} ein Idempotentes enthält.

[figure: m; m^{2}; m^{i}; m^{i+2}; m^{i+1}; m^{i+k−1}; ...]

Bei aperiodischen Monoiden kann hier stets k = 1 gewählt werden. Definition 3.3 Ein endlicher Monoid M heißt \underline{aperiodisch}, falls es ein n ≥ 1 gibt mit m^{n+1} = m^{n} für alle m ∈ M.

□

Die Klasse der aperiodischen Monoide ist also eine M-Varietät, da sie schließlich durch (x^{n+1} = x^{n})_{n≥1} definiert ist. Beachte dazu: Ist m^{n+1} = m^{n}, so folgt für alle n′≥ n, daß m^{n′+1} = m^{n′}. Also folgt, wenn ein n gefunden ist, so gilt die Gleichung auch für alle Werte > n. Damit ist die Klasse der aperiodischen Monoide schließlich definiert. Ist m^{i} = m^{i+k} und sind m^{i}, m^{i+1} , ..., m^{i+k−1} paarweise verschieden, so ist {m^{i}, ..., m^{i+k−1} } eine zyklische Gruppe der Ordnung k. Das Einselement der Gruppe ist das Idempotente in {m^{i}, ..., m^{i+k−1} }, dieses ist im allgemeinen nicht das Einselement des Monoids.

Definition 3.4 Es sei (M,·,1) ein Monoid. Eine Teilmenge G ⊆ M heißt \underline{Gruppe in M}, falls G eine Unterhalbgruppe von M ist, die bezüglich der Monoidoperation von M eine Gruppe ist.

□

Das Einselement von G ist ein Idempotentes von M, kann aber verschieden von dem Einselement 1 von M sein. Bei aperiodischen Monoiden sind die zyklischen Gruppen {m^{i}, ..., m^{i+k−1} } stets trivial, das heißt sie haben Kardinalität 1. Dies gilt für alle Gruppen in aperiodischen Monoiden.

Satz 3.5 Ein endlicher Monoid M ist genau dann aperiodisch, wenn er nur triviale Gruppen enthält.

Beweis

“⇒” Es sei M aperiodisch und n so, daß m^{n+1} = m^{n} für alle m ∈ M gilt.

Angenommen G ⊆ M ist nicht-triviale Gruppe in M, das heißt |G| > 1. Es sei e ∈ G das Einselement von G und g ∈ G mit e ≠ g. Es gilt aber g^{n+1} = g^{n} und damit g = e, da man in Gruppen durch Multiplikation mit dem Inversen g^{−1} kürzen kann (hier wird n-mal mit g^{−1} multipliziert). Widerspruch Aus diesem Widerspruch folgt, daß es nur triviale Gruppen in M geben kann.

“⇐” Es sei m ∈ M. Wir betrachten wieder {m, m^{2}, ...}. Es sei k ≥ 1 minimal, so daß es ein i ≥ 1 gibt mit m^{i+k} = m^{i}. Da {m^{i}, ..., m^{i+k−1} } eine zyklische Gruppe ist, folgt k = 1 (da die Menge {m^{i}, ..., m^{i+k−1} } k Elemente enthält und es nur triviale Gruppen gibt). Es gibt also für jedes m ∈ M ein i_{m} ≥ 1 mit m^{i_{m}+1} = m^{i_{m}}. Offenbar folgt für alle j ≥ i_{m} auch m^{j+1} = m^{j}. Daher liefert max{i_{m}|m ∈ M} eine Zahl n mit

∀m ∈ M : m^{n+1} = m^{n}.
□

Satz 3.6 (Schützenberg)

\underbrace{L(Ap)}_{{Menge der Sprachen, \atop deren syntakt. Monoid} ; aperiodisch ist}= (SF)_{Σ}

das heißt für L ⊆ Σ^{∗} gilt

M_{L} ∈ Ap gdw L ∈ (SF)_{Σ}
□

Der Beweis, insbesondere “⇒”, ist sehr aufwendig. Vergleiche hierzu S. Eilenberg: Auto-

mata, Languages and Machines, Vol. B.

Korollar 3.7 Es sei L eine reguläre Sprache (gegeben durch endlichen Automaten, regulären Ausdruck etc.). Dann kann man effektiv entscheiden, ob L ∈ (SF)_{Σ} gilt oder nicht.

Beweis Konstruiere das syntaktische Monoid und überprüfe, ob es aperiodisch ist.

□

Beispiel 3.8 Es sei Σ = {a}. Dann ist a(aa)^{∗} ∉ (SF)_{Σ}.

Beweis Der minimale deterministische Automat für L = a(aa)^{∗} ist

[figure: 1; 2; a; a]

Übergangsmonoid:

δ_{ε} = \frac{1 2}{1 2} δ_{a} = \frac{1 2}{2 1} δ_{aa} = δ_{a}δ_{a} = δ_{ε}

Damit ist

M_{L} = \{ \underbrace{δ_{ε}}_{Einselement}, \underbrace{δ_{a}}_{δ_{a}δ_{a}=δ_{ε}} \}

eine zyklische Gruppe der Kardinalität 2. Somit ist M_{L} offenbar nicht aperiodisch. □

3.3 Formeln der Logik erster Stufe

Ziel dieses Abschnitts ist es, zu zeigen, daß die sternfreien Sprachen genau die durch Formeln der \underline{Logik erster Stufe} definierbaren Sprachen sind. Satz 3.9 Für L ⊆ Σ^{+} sind äquivalent

1. L ∈ (SF)_{Σ}

2. L = L(φ) für eine geschlossene Formel φ der Logik erster Stufe mit Gleichheit über den nichtlogischen Symbolen < und Q_{a} mit a ∈ Σ.

□

Beachte: Anstelle der Prädikate P_{1},...,P_{n} verwenden wir Œ direkt Q_{a} für a ∈ Σ. Der Beweis dieses Satzes ist recht aufwendig, deshalb führen wir ihn in den folgenden beiden Unterabschnitten.

3.3.1 Beweis von “1 ⇒ 2” von Satz 3.9

Sternfreie Sprachen entstehen aus endlichen Sprachen durch Anwendung Boolescher Operatoren und Konkatenation.

• Endliche Sprachen Offenbar genügt es, Einermengen {w} für w ∈ Σ^{+} zu betrachten. Für w = a_{1}...a_{n} ∈ Σ^{+} sei

φ_{w}:= ∃x_{1}...∃x_{n}  (Q_{a_{1}}(x_{1}) ∧ ...∧ Q_{a_{n}}(x_{n})
⋀ _{j=1}^{n−1} (x_{j} < x_{j+1} ∧ ¬∃z(x_{j} < z ∧ z < x_{j+1} ))
∧ ¬∃z(z < x_{1}∨ x_{n} < z))

3.3.2 Beweis von “ 2 ⇒ 1” von Satz 3.9 35

Dann ist L(φ_{w}) = {w}.

• Boolesche Operatoren entsprechen nach Satz 1.26 den logischen Junktoren ∧,∨,¬.

• Konkatenation entspricht im Prinzip dem Existenzquantor. Zum besseren Verständnis betrachten wir zunächst ein Beispiel:

L_{1} := a^{+} und L_{2} := b^{+} werden definiert durch φ_{1} = ∀xQ_{a}(x) und φ_{2} = ∀xQ_{b}(x). Die Sprache L_{1}· L_{2} wird definiert durch

φ = ∃z  (∀x(x ≤ z → Q_{a}(x))
∧ ∀x(z < x → Q_{b}(x))
∧ ∃z′(z < z′))

Der Quantor in φ_{1} wird also relativiert auf die Positionen ≤ z und der in φ_{2} auf die Positionen > z.

Allgemein wird die Relativierung φ^{≤z} wie folgt definiert:

– ist φ atomar, so gilt φ^{≤z} = φ

– (ψ_{1}∧ ψ_{2})^{≤z} = ψ_{1}^{≤z} ∧ ψ_{2}^{≤z}

– (ψ_{1}∨ ψ_{2})^{≤z} = ψ_{1}^{≤z} ∨ ψ_{2}^{≤z}

– (¬ψ)^{≤z} = ¬(ψ^{≤z})

– (∃xψ(x))^{≤z} = ∃x(x ≤ z ∧ ψ(x)^{≤z})

– (∀x ψ(x))^{≤z} = ∀x (x ≤ z → ψ(x)^{≤z})

Entsprechend ist φ^{>z} definiert. Dann gilt für L_{1} = L(φ_{1}) und L_{2} = L(φ_{2}), daß L_{1}·L_{2} = L(∃z(φ_{1}^{≤z} ∧ φ_{2}^{>z} ∧ ∃z′(z < z′)))

Damit ist der Beweis von “1 ⇒ 2” abgeschlossen.

3.3.2 Beweis von “ 2 ⇒ 1” von Satz 3.9

Um zu zeigen, daß jede geschlossene Formel der Logik erster Stufe eine Sternfreie Sprache definiert, betrachten wir die \underline{Quantorentiefe} der Formel, das heißt die maximale Schachtelungstiefe von Quantoren in der Formel. Offenbar enthält jede geschlossene Formel mindestens einen Quantor, da es keine nicht-variablen Terme gibt (weil die hier betrachtete Logik keine Konstanten-Symbole enthält). Da die Negation vorhanden ist, können wir Œ annehmen, daß alle Quantoren existentielle Quantoren sind. Da die Junktoren ∧, ∨, ¬ den Booleschen Operatoren entsprechen, genügt es, sich auf Formeln der Form ∃x φ(x) zu konzentrieren.

Induktionsverankerung Quantorentiefe 1 In diesem Fall enthält φ keinen Quantor und damit keine andere Variable als x. Das heißt φ ist Boolesche Kombination von Formeln

• Q_{a}(x) oder ¬Q_{a}(x)

• x < x oder ¬(x < x)

• x = x oder ¬(x = x)

Œ sei φ in Disjunktiver Normalform, das heißt als Disjunktion von Konjunktionen obiger atomarer Formeln, gegeben.

Diese kann noch weiter normalisiert werden:

• ersetze x < x und ¬(x = x) durch “false”, das heißt lösche das gesamte Disjunkt, in dem die Formel vorkommt

• ersetze ¬(x < x) und x = x durch “true”, das heißt entferne sie aus dem Disjunkt

Bleibt nach dieser Normalisierung nur “true” oder “false” übrig, so gilt L(∃xφ(x)) = Σ^{+} oder L(∃xφ(x)) = ∅. Diese beiden Sprachen sind aber sternfrei, das heißt in diesem Fall sind wir fertig. Damit kommen Œ nur noch Q_{a}(x) beziehungsweise ¬Q_{a}(x) vor. Man kann weiter normalisieren: Enthält ein Disjunkt Q_{a}(x)

• lösche es, falls es auch ¬Q_{a}(x) oder Q_{b}(x) für b ≠ a enthält

• sonst lösche alle ¬Q_{b}(x) für a ≠ b aus dem Disjunkt; diese enthalten dann keine zusätzliche Information

Damit haben wir nur noch Disjunkte der Formen

• Q_{a}(x)

• ¬Q_{a_{1}}(x) ∧ ...∧ ¬Q_{a_{k}}(x)

Wir betrachten nun jeweils die zugehörige Sternfreie Sprache:

• L(∃xQ_{a}(x)) = \overbrace{Σ^{∗}}^{\overline{∅}}· \overbrace{a}^{endlich}·\overbrace{Σ^{∗}}^{\overline{∅}} ⇒ sternfrei

• L(∃x: ¬Q_{a_{1}}(x) ∧ ...∧ ¬Q_{a_{k}}(x)) = \overbrace{Σ^{∗}}^{\overline{∅}}·\overbrace{Σ\\{a_{1},...,a_{k}\}}^{endlich}·\overbrace{Σ^{∗}}^{\overline{∅}} ⇒ sternfrei

Damit ist die Quantorentiefe 1 abgehandelt, das heißt der Induktionsanker ist komplett. Für den Induktionsschritt sei ∃x φ(x) von Quantorentiefe n + 1. Wir benötigen einige Notation und zwei Sätze, bevor wir den Induktionsschritt durchführen können.

Definition 3.10 Mit L_{k,n} bezeichnen wir die Formeln der Logik erster Stufe über den nicht-logischen Symbolen < und Q_{a} für a ∈ Σ, die k freie Variable und Quantorentiefe ≤ n haben. □

Zum Beispiel gehört φ = ∃x(y < x ∧ x < z ∧ Q_{a}(x)) zu L_{2,1}. Um diese Formel zu interpretieren, genügt ein Wort (z. B. baa) nicht. Man muß auch angeben, wie die freien Variablen interpretiert werden (hier also y und z, z.B. y durch 1 (erste Position im Wort baa) und z durch 3 (dritte Position im Wort baa))). Wir sagen (baa, 1, 3) erfüllt φ. Allgemein werden Formeln aus L_{k,n} durch Tupel (w,s⃗) interpretiert, wobei w ∈ Σ^{+} und s⃗= s_{1}...s_{k} mit s_{i} ∈ {1,...,|w|}. (w,s⃗) ⊧ φ ∈ L_{k,n}(“(w,s⃗)” efüllt φ) ist in der offensichtlichen Weise definiert. Für k = 0 läßt man im allgemeinen die leere Sequenz s⃗ weg.

Definition 3.11 Für n ≥ 0 und k ≥ 0 definieren wir

(w,s⃗) ≡_{k,n}(v,t⃗) gdwfür alle φ ∈ L_{k,n}gilt(w,s⃗) ⊧ φ gdw (v,t⃗) ⊧ φ
□

Offenbar ist ≡_{k,n}eine Äquivalenzrelation (dies erkennt man an dem gdw in der Definition). Für k = 0 schreiben wir ≡_{n} statt ≡_{0,n}. {ε} wird in diesem Fall zu einer eigenen ≡_{0,n}-Klasse. Um den Beweis von “2 ⇒ 1” abzuschließen benötigen wir zwei Sätze, die wir später in einem eigenen Unterabschnitt beweisen werden.

Satz 3.12 Für alle n ≥ 0 und k ≥ 0 gibt es eine endliche Teilmenge Γ_{k,n}von L_{k,n}, so daß gilt: jedes Element von L_{k,n}ist äquivalent zu einem Element von Γ_{k,n}. Äquivalent heißt: die Formeln werden erfüllt durch genau dieselben Tupel (w,s⃗).

□

Korollar 3.13 Für n ≥ 0, k ≥ 0 hat ≡_{k,n}nur endlich viele Äquivalenzklassen.

Beweis Die Klasse von (w,s⃗) ist eindeutig bestimmt durch eine Formelmenge

Γ := \{φ ∈ Γ_{k,n}| (w,s⃗) ⊧ φ\} ⊆ \underbrace{Γ_{k,n}}_{endlich}.

Da es nur endlich viele solche Teilmengen gibt, kann es nur endlich viele verschiedene Klassen geben.

□

Der Begriff der durch eine Formel akzeptierten Sprache wird auf den Fall k > 0 ausgedehnt: für φ ∈ L_{k,n}sei

L(φ) := {(w,s⃗) | (w,s⃗) ⊧ φ}.

Korollar 3.14 Für alle n ≥ 0, k ≥ 0 und alle ≡_{k,n}-Klassen W gibt es eine Formel φ_{W}∈ L_{k,n}mit L(φ_{W}) = W.

Beweis

\underbrace{[(w,s⃗)]_{≡_{k,n}}}_{{=W \atop =\{(u,t⃗) | (u,t⃗)≡_{k,n}(w,s⃗)\}}} = L( ⋀_{{φ∈Γ_{k,n} \atop (w,s⃗)⊧φ}} φ ∧ ⋀_{{ψ∈Γ_{k,n} \atop (w,s⃗)|̸=ψ}} ¬ψ)

□

Korollar 3.15 Für alle n ≥ 0, k ≥ 0 und alle φ ∈ L_{k,n} ist φ äquivalent zu einer endlichen Disjunktion von Formeln φ_{W} für gewisse ≡_{k,n}-Klassen W.

Beweis φ ist äquivalent zu

⋁_{{W =[(w,s⃗)]≡_{k,n} \atop (w,s⃗)⊧φ}} φ_{W}.

□

Satz 3.16 Sei n ≥ 0, u, v, u′, v′∈ Σ^{∗} und a ∈ Σ. Dann folgt aus u ≡_{n} u′und v ≡_{n} v′, daß (uav, |u| + 1) ≡_{1,n} (u′av′, |u′| + 1).

□

Der Beweis dieses Satzes folgt im nächsten Abschnitt. Wir können damit nun den Induktionsschritt abschließen. Sei also ∃x φ(x) von Quantorentiefe n + 1. Damit ist φ(x) ∈ L_{1,n}. O.B.d.A. sei φ(x) eine Formel φ_{W} für eine ≡_{1,n}-Klasse W. Dies ist keine Einschränkung, denn φ(x) ist äquivalent zu

⋁_{{W =[(w,s⃗)]≡_{k,n} \atop (w,s⃗)⊧φ}} φ_{W}(x).

Dies gilt mit Korollar 3.15. Damit ist ∃x φ(x) äquivalent zu

⋁_{{W =[(w,s⃗)]≡_{k,n} \atop (w,s⃗)⊧φ}} ∃x φ_{W}(x).

Disjunktion kann durch Vereinigung behandelt werden, daher betrachten wir nun nur noch Formeln der Form ∃x φ_{W}(x).

Lemma 3.17

L( ∃x \underbrace{φ_{W}(x)}_{W ist ≡_{1,n}−Klasse}) = ⋃_{{U=[u_{0}]≡_{0,n} \atop V =[v_{0}]≡_{0,n}} ; {a∈Σ \atop (u_{0}av_{0}, |u_{0}|+1)∈W}} U · a · V

Beweis

“⊆”

\begin{aligned}w ∈ L(∃x φ_{W}(x)) & gdw & w = uav ∧ (uav, |u| + 1) ⊧ φ_{W}(x) \\ & gdw & w = uav ∧ (uav, |u| + 1) ∈ W \end{aligned}

Wählt man U = [u]_{≡_{0,n}} und V = [v]_{≡_{0,n}} , dann ist w = uav ∈ [u]_{≡_{0,n}} ·a·[v]_{≡_{0,n}} , das heißt w = uav ist in der Rechten Seite der Formel des Lemmas enthalten.

“⊇” Aus (u_{0}av_{0}, |u_{0}| + 1) ∈ W = L(φ_{W}) folgt u_{0}av_{0} ∈ L(∃x φ_{W}(x)). Es bleibt zu zeigen, daß auch für alle u ≡_{0,n} u_{0} und v ≡_{0,n} v_{0} gilt: uav ∈ L(∃x φ_{W}(x)). Mit Satz 3.16 gilt aber:

(u_{0}av_{0}, |u_{0}| + 1) ≡_{1,n} (uav, |u| + 1),

was (uav, |u| + 1) ∈ W liefert, das heißt (uav, |u| + 1) ⊧ φ_{W}(x). Es folgt uav ⊧ ∃x φ_{W}(x).

□

Mit Korollar 3.14 sind die ≡_{0,n}-Klassen U und V aus dem Lemma von der Form U = L(φ_{U}) und V = L(φ_{V}) für φ_{U}, φ_{V} ∈ L_{0,n}. Induktion liefert U, V ∈ (SF)_{Σ} und damit

\underbrace{U}_{∈(SF)_{Σ}}· \underbrace{a}_{endlich}· \underbrace{V}_{∈(SF)_{Σ}} ∈ (SF)_{Σ}.

Das schließt den Beweis von “2 ⇒ 1” des Satzes 3.9 ab.

3.3.3 Beweis der Sätze 3.12 und 3.16

Satz 3.12 Für alle n ≥ 0, k ≥ 0 gibt es eine endliche Teilmenge Γ_{k,n}von L_{k,n}, so daß gilt: Jedes Element von L_{k,n}ist äquivalent zu einem Element von Γ_{k,n}. Beweis Es sei φ ∈ L_{k,n}. Ohne Einschränkung können wir davon ausgehen, daß φ Boolesche Kombination ist von

• Elementen aus L_{k,n−1}

• Formeln der Form ∃x ψ(x,y_{1},...,y_{k}) mit ψ(x,y_{1},...,y_{k}) ∈ L_{k+1,n−1} .

Wir verwenden daher Induktion über n:

n = 0 Es sei k ≥ 0 beliebig. Eine Formel φ(y_{1},...,y_{k}) ∈ L_{k,0}ist eine Boolesche Kombination von Formeln

Q_{a}(x) (a ∈ Σ), x < y, x = y  (3.1)

wobei x,y ∈ {y_{1},...,y_{k}}. Es gibt offenbar nur endlich viele atomare Formeln der Form (3.1) und daher (bis auf Äquivalenz) nur endlich viele Boolesche Kombinationen.

n − 1 → n φ ist Boolesche Kombination von Elementen aus L_{k,n−1} und Formeln ∃x ψ(x,y_{1},...,y_{k}) mit ψ(x,y_{1},...,y_{k}) ∈ L_{k+1,n−1} . Damit ist φ äquivalent zu einer Booleschen Kombination von Elementen aus Γ_{k,n−1} und Formeln ∃x γ(x,y_{1},...,y_{k}) mit γ(x,y_{1},...,y_{k}) ∈ Γ_{k+1,n−1} . Mit der Induktionsvoraussetzung wissen wir, daß diese endlichen Mengen Γ_{k,n−1} und Γ_{k+1,n−1} existieren.

□

Zum Beweis von Satz 3.16 benötigen wir eine spieltheoretische Charakterisierung der Relationen ≡_{k,n}.

Definition 3.18 (Ehrenfeucht-Fraissé Spiele) Es sei Σ ein endliches Alphabet. Wir betrachten zwei Spieler I und II, die auf Wörtern u,v ∈ Σ^{+} spielen. Ein Zug besteht darin, eine Position in u oder v zu wählen. Beginnend mit I wird abwechselnd gezogen. Zieht I in u, so muß II in v ziehen; zieht I in v, so muß II in u ziehen. Ein \underline{Spiel der Länge n} besteht aus n Zügen von I und den n Antwortzügen von II.

Es seien (i_{1},j_{1}), ..., (i_{n},j_{n}) die gezogenen Positionen eines solchen Spiels, wobei die i_{ν} die in u gezogene Position ist und j_{ν} die in v gezogene Position (unabhängig davon, wer gezogen hat). Spieler II hat \underline{gewonnen}, wenn für u = a_{1}...a_{p} und v = b_{1}...b_{q} gilt:

• a_{i_{ν}} = b_{j_{ν}} für ν = 1, ..., n an den gezogenen Positionen für den Zug ν steht dasselbe Symbol

• i_{ν} < i_{ν′} gdw j_{ν} < j_{ν′} die relative Lage der gezogenen Positionen in u und v ist gleich

Sonst hat II verloren und damit I gewonnen.

□

Die Definition des Gewinnens bedeutet, daß I versucht so zu ziehen, daß man dadurch zwischen u und v unterscheiden kann, während II versucht, das zu verhindern.

Beispiel 3.19 Seien n = 3 und Σ = {a}, das heißt nur die Ordnung zwischen den gezogenen Positionen ist relevant. Folgender Spielverlauf wäre denkbar:

1 2 3 4  5 6 7
u = a \overbrace{a}^{I,2} a \overbrace{a}^{II,1} a a
v = a \underbrace{a}_{II,2} a a \underbrace{a}_{I,1} a a

Überlegungen zum ersten Zug von II: Hätte II auf Position 6 gezogen, dann hätte I durch einen Zug auf Position 7 in v das Spiel gewonnen. Ein Zug auf Position 5 hätte dazu geführt, daß I durch Ziehen auf Position 6 und anschließend auf Position 7 gewonnen hätte. Überlegungen zum zweiten Zug von II: sowohl Position 2 als auch Position 3 in v sind geeignet, alle anderen Positionen würden einen Sieg von I zur Folge haben. Man sieht, daß II jeden möglichen dritten Zug von I geeignet beantworten kann und damit für n = 3 das Spiel gewinnt. Für n = 4 könnte I auf die Positionen 3 und 4 in v ziehen und damit gewinnen, da für den vierten Zug keine geeignete Antwort in u möglich ist.

□

Beispiel 3.20 Σ = {a,b}, n = 3

1  2  3 4
u = \overbrace{b}^{I,3} \overbrace{b}^{I,2} \overbrace{a}^{I,1} b
v = \underbrace{b}_{II,2} \underbrace{a}_{II,1} b b

II kann den dritten Zug von I nicht mehr beantworten, damit hat I gewonnen.

□

Definition 3.21 Es seien n ≥ 1 und u,v ∈ Σ^{+} . Wir sagen, daß II eine \underline{Gewinnstrategie} für Spiele der Länge n auf u und v hat, wenn II alle möglichen Züge von I stets so beantworten kann, daß II gewinnt.

□

Um Induktionsargumente einsetzen zu können, betrachten wir Spiele, die schon ein Stück angefangen haben: Es seien dazu u, v ∈ Σ^{+} , s⃗ = s_{1}...s_{k} ∈ {1, ..., |u|}^{k} und t⃗ = t_{1}...t_{k} ∈ {1, ...,|v|}^{k}. Dann beschreibt das Paar (u,s⃗) und (v,t⃗) ein Spiel, das schon k Züge angefangen ist. Ein Spiel der Länge n darauf ist eine Fortsetzung um n weitere Züge. Spieler II hat das \underline{Fortsetzungsspiel} gewonnen, wenn II das Gesamtspiel gewonnen hat.

Definition 3.22 Es seien (u,s⃗) und (v,t⃗) mit u, v ∈ Σ^{+} und s⃗∈ {1,...,|u|}^{k} und t⃗ ∈ {1, ..., |v|}^{k} gegeben. Wir definieren:

(u,s⃗) ∼_{k,n}(v,t⃗) gdw II hat für das Forsetzungsspiel der Länge n auf (u,s⃗)und (v,t⃗)eine Gewinnstrategie

Für k = 0 erweitern wir wieder wie in Definition 3.11 ∼_{0,n} auf Σ^{∗}, indem wir {ε} zu einer eigenen ∼_{0,n}-Äquivalenzklasse machen.

□

Lemma 3.23 ∼_{k,n}ist eine Äquivalenzrelation.

Beweis

• reflexiv: II simuliert genau die Züge von I (da für die Reflexivität ja beide Spieler auf gleichen Worten spielen)

• symmetrisch: klar, da (u,s⃗) und (v,t⃗) im Spiel symmetrisch verwendet werden

• transitiv: Es seien

\underbrace{(u,s⃗) ∼_{k,n}(v,t⃗)}_{Gewinnstrategie GS 1}

und

\underbrace{(v,t⃗) ∼_{k,n}(w,r⃗)}_{Gewinnstrategie GS 2}

Die Strategie für II auf (u,s⃗) und (w,r⃗) lautet dann wie folgt:

– zieht I in u, so reagiert II mit GS 1 in v und darauf mit GS 2 in w – ein Zug von I in w kann entsprechend behandelt werden

□

Für die Relation ∼_{k,n} kann man eine Aussage beweisen, die der von Satz 3.16 für ≡_{k,n} entspricht.

Lemma 3.24 Seien n ≥ 0, u, u′, v, v′ ∈ Σ^{∗} und a ∈ Σ. Dann folgt aus u ∼_{0,n} u′ und v ∼_{0,n} v′ auch (uav,|u| + 1) ∼_{1,n} (u′av′,|u′| + 1).

Beweis Betrachte den Fall u ≠ ε ≠ v. Es seien GS 1 die Strategie für u ∼_{0,n}u′und GS 2 die Strategie für v ∼_{0,n} v′. Zieht I in u (bzw. u′), so antwortet II mit GS 1 in u′ (bzw. u). Zieht I in v (bzw. v′), so antwortet II mit GS 2 in v′(bzw. v). Zieht I die Position |u| + 1 in uav (bzw. die Position |u′| + 1 in u′av′), so antwortet II mit |u′| + 1 in u′av′(bzw. |u| + 1 in uav). Offenbar liefert das eine Gewinnstrategie für II. Die Fälle u = ε = u′und v = ε = v′können entsprechend behandelt werden.

□

Um Satz 3.16 zu erhalten genügt es zu zeigen, daß ∼_{k,n}und ≡_{k,n}übereinstimmen. Zunächst geben wir ein intuitives Argument für die Übereinstimmung der beiden Relationen: Offenbar sind die Chancen für II um so größer, je ähnlicher die beiden Wörter u, v sind, auf denen gespielt wird. u ≡_{n} v heißt, daß man u und v nicht durch eine Formel der Quantorentiefe n unterscheiden kann. Der Zusammenhang zwischen der Quantorentiefe und der Anzahl der Züge ist auch einleuchtend: ∃x φ(x) sagt aus, daß es eine Position mit bestimmten Eigenschaften gibt. Durch einen Zug wird eine Position ausgewählt.

Lemma 3.25 Für alle n,k ≥ 0 gilt: ∼_{k,n} = ≡_{k,n}

Beweis Induktion über n Induktionsanker: n=0 Es seien (u,s⃗) und (v,t⃗) gegeben.

1. Angenommen (u,s⃗) ≡_{k,0}(v,t⃗). Œ seien {y_{1}, ..., y_{k}} die (erlaubten) freien Variablen. Für i = 1, ..., k entsprechen s_{i} und t_{i} der Variablen y_{i}. Für atomare Formeln der Formen y_{i} < y_{j}, y_{i} = y_{j} und Q_{a}(y_{i}) gilt wegen (u,s⃗) ≡_{k,0} (v,t⃗):

(∗)\{ \begin{matrix}(u,s⃗) ⊧ y_{i} < y_{j} & gdw & (v,t⃗) ⊧ y_{i} < y_{j} \\ (u,s⃗) ⊧ Q_{a}(y_{i}) & gdw & (v,t⃗) ⊧ Q_{a}(y_{i}) \\ (u,s⃗) ⊧ y_{i} = y_{j} & gdw & (v,t⃗) ⊧ y_{i} = y_{j} \end{matrix}

Das heißt aber (für u = a_{1}...a_{p}, v = b_{1}...b_{q})

(∗∗)\{ \begin{matrix}s_{i} < s_{j} & gdw & t_{i} < t_{j} \\ a_{s_{i}} = a & gdw & b_{t_{i}} = a \\ s_{i} = s_{j} & gdw & t_{i} = t_{j} \end{matrix}

Das bedeutet aber, daß II das Spiel mit n = 0 zusätzlichen Zügen gewonnen hat. Dies gilt mit den ersten beiden Zeilen von (∗∗).

2. Umgekehrt folgt aus (u,s⃗) ∼_{k,0} (v,t⃗), daß die ersten beiden Zeilen von (∗∗) erfüllt sind. Die dritte Zeile ergibt sich aus der ersten und der Tatsache, daß < eine totale Ordnung ist. Damit erhalten wir (∗), was ja äquivalent zu (∗∗) ist. Dies zeigt (u,s⃗) ≡_{k,0} (v,t⃗).

Beachte: Formeln der Quantorentiefe 0 sind Boolesche Kombinationen von atomaren Formeln. (∗) zeigt das Gewünschte nur für atomare Formeln.

Induktionsschritt: n → n + 1

1. Angenommen es gelte (u,s⃗) ∼_{k,n+1} (v,t⃗). Es sei φ(y_{1},...,y_{k}) ∈ L_{k,n+1} mit (u,s⃗) ⊧ φ gegeben. Es genügt zu zeigen, daß daraus (v,t⃗) ⊧ φ folgt. Da Boolesche Operatoren unproblematisch sind, genügt es, Formeln φ der Form

φ = ∃y_{k+1} : ψ(y_{1},...,y_{k},y_{k+1})

zu betrachten mit ψ ∈ L_{k+1,n}. Wegen (u,s⃗) ∼_{k,n+1} (v,t⃗) kann II jeden möglichen Zug von I so beantworten, daß II danach immernoch eine Gewinstrategie hat. Daher gibt es zu jedem s_{k+1} ∈ {1,...,|u|} ein t_{k+1} ∈ {1,...,|v|} mit

(u,s⃗s_{k+1}) ∼_{k+1,n} (v,t⃗t_{k+1}).

Induktion liefert, daß für alle s_{k+1} ein t_{k+1} existiert mit

(u,s⃗s_{k+1}) ≡_{k+1,n} (v,t⃗t_{k+1})  (3.2)

Wegen (u,s⃗) ⊧ ∃y_{k+1} : ψ(y_{1},...,y_{k},y_{k+1}) gibt es ein s_{k+1} ∈ {1,...,|u|} mit

(u,s⃗s_{k+1}) ⊧ ψ(y_{1},...,y_{k},y_{k+1})  (3.3)

Sei nun t_{k+1} so, daß (3.2) gilt. Wegen ψ ∈ L_{k+1,n} folgt aus (∗∗) auch

(v,t⃗t_{k+1}) ⊧ ψ(y_{1},...,y_{k},y_{k+1})

Daraus folgt offenbar

(v,t⃗) ⊧ \underbrace{∃y_{k+1} : ψ(y_{1},...,y_{k},y_{k+1})}_{φ}

Damit ist gezeigt, daß u und v äquivalent sind für Formeln aus L_{k,n+1}.

2. Angenommen (u,s⃗) ≁_{k,n+1} (v,t⃗).

Gesucht ist eine Formel φ ∈ L_{k,n+1}, die von einem der beiden Tupel erfüllt wird, aber nicht von dem anderen. Daraus folgt dann (u,s⃗) ≢_{k,n+1} (v,t⃗). Wegen (u,s⃗) ≁_{k,n+1} (v,t⃗) gibt es einen ersten Zug von I, den II nicht so beantworten kann, daß II danach eine Gewinnstrategie hat. Œ liege dieser erste Zug von I in u. (Der Fall, daß der erste Zug in v liegt, kann symmetrisch behandelt werden.) Das heißt es gibt ein s_{k+1} ∈ {1,...,|u|}, so daß für alle t_{k+1} ∈ {1,...,|v|} gilt:

(u,s⃗s_{k+1}) ≁_{k+1,n} (v,t⃗t_{k+1})

Induktion liefert

(u,s⃗s_{k+1}) ≢_{k+1,n} (v,t⃗t_{k+1})

Es sei dieses s_{k+1} fixiert. Für alle t_{k+1} gibt es daher eine Formel

ψ_{t_{k+1}}(y_{1},...,y_{k+1}) ∈ L_{k+1,n}

mit

(u,s⃗s_{k+1}) ⊧ ψ_{t_{k+1}} und  (3.4)
(v,t⃗t_{k+1}) |̸= ψ_{t_{k+1}}  (3.5)

Beachte: (u,s⃗) ⊧ ¬ψ gdw (u,s⃗) |̸= ψ.

Aus (3.4) folgt für φ_{t_{k+1}} := ∃y_{k+1} : ψ_{t_{k+1}} (u,s⃗) ⊧ φ_{t_{k+1}}.

Aus (3.5) kann man leider nicht folgern, daß (v,t⃗) |̸= φ_{t_{k+1}}. Wir wissen nur, daß t_{k+1} nicht für y_{k+1} in ψ_{t_{k+1}} eingesetzt werden kann. Über andere t’s ist aber nichts bekannt. Wir betrachten daher statt einem φ_{t_{k+1}} die Formel

φ:= ∃y_{k+1} : ⋀_{1≤t_{k+1} ≤|u|} ψ_{t_{k+1}}

Aus (3.4) folgt (u,s⃗) ⊧ φ. Aus (3.5) folgt, daß es zu jedem t_{k+1} ∈ {1,...,|v|} ein Konjunkt, nämlich ψ_{t_{k+1}} in φ gibt, das nicht erfüllt ist. Daraus folgt (v,t⃗) |̸= φ.

□

Beachte: Lemma 3.25 gilt entsprechend auch für unendliche Wörter. Um dann die Konjunktion

⋀_{t_{k+1} Position in v}ψ_{t_{k+1}}

endlich zu lassen, muß man Satz 3.12 verändern. (L_{k+1,n} ist äquivalent zu endlicher Teilmenge Γ_{k+1,n}.)

3.4 Die Theorie der totalen Ordnung

Aus der Sicht der Logik ist Satz 3.9 interessant, weil er ein Entscheidbarkeitsresultat liefert. Theorie der totalen Ordnung:

Total = { ∀x∀y∀z: x < y ∧ y < z → x < z
∀x: ¬(x < x)
∀x∀y: (x < y ∨ x = y ∨ y < x)}

Satz 3.26 Es sei φ eine geschlossene Formel der Logik erster Stufe mit Gleichheit, die höchstens die nichtlogischen Symbole <, P_{1},...,P_{k} (für einstellige Prädikate P_{i}) enthält. Dann ist es entscheidbar, ob Total ∪ {φ} ein endliches Modell hat oder nicht.

Beweis Wir haben gesehen, daß L(φ) eine sternfreie Sprache ist. Der Beweis von Satz 3.9 ist konstruktiv, das heißt man kann zu φ effektiv einen sternfreien Ausdruck (mit Booleschen Operatoren, Konkatenation aus endlichen Sprachen) bestimmen. Das liegt im wesentlichen daran, daß man Γ_{k,n}effektiv bestimmen kann. Damit sind die Relationen ≡_{k,n}entscheidbar. Daraus kann ein endlicher Automat für L(φ) konstruiert werden. Existenz eines endlichen Modells heißt: es gibt ein endliches Wort u ∈ L(φ). Das Leerheitsproblem (L(A) = ∅) ist aber für endliche Automaten entscheidbar.

□

Häufig möchte man wissen, ob eine solche Formel ein Modell hat, bei dem < als die gewöhnliche Ordnung auf den natürlichen Zahlen interpretiert wird. Um solche Probleme handhaben zu können, betrachten wir im folgenden unendliche Wörter und Automaten auf unendlichen Wörtern. Wir haben gesehen: nicht alle regulären Sprachen sind von der Form L(φ) für eine Formel φ der Logik erster Stufe; zum Beispiel ist L = a(aa)^{∗} nicht sternfrei. Alle regulären Sprachen sind definierbar, wenn man zusätzlich Quantifizierung über einstellige Prädikate zuläßt (vergleiche Beispiel 1.28). Wir werden diese Aussage für den Fall unendlicher Wörter beweisen. Der Beweis für endliche Wörter ist entsprechend.

46 3 Sternfreie Sprachen

Unendliche Wörter und Büchi-Automaten

Sei Σ ein endliches Alphabet. Ein \underline{endliches Wort} w ∈ Σ^{∗} der Länge k ist eine Folge w = a_{0}a_{1}...a_{k−1} von k Elementen aus Σ. Man kann daher w auffassen als eine Abbildung

w: {0, 1, ..., k − 1} → Σ

mit w(i) = a_{i}. Ein endliches Wort ist also eine Abbildung von einem \underline{Anfangssegment} der natürlichen Zahlen nach Σ. Wir werden im folgenden für die natürlichen Zahlen ω schreiben. ω steht für den Ordnungstyp der natürlichen Zahlen.

Definition 4.1

1. Ein \underline{unendliches Wort} über Σ ist eine Abbildung α: ω → Σ.

2. Mit Σ^{ω} bezeichnen wir die Menge aller unendlichen Wörter über Σ.

3. Mengen unendlicher Wörter heißen \underline{ω-Sprachen}.

□

Wir schreiben unendliche Wörter häufig als α = a_{0}a_{1}a_{2}a_{3}... , wobei α(i) = a_{i}.

Beispiel 4.2 Σ = {a, b}

α(i) = { a i gerade b i ungerade

wird geschrieben als α = ababab.... □

Wir betrachten einige Operationen für unendliche Wörter

• \underline{Segment}

für α: ω → Σ bezeichne

– α(m,n) das endliche Wort α(m)α(m + 1)...α(n) (für m ≤ n).

– α(m,∞) das unendliche Wort α(m)α(m + 1)α(m + 2)...

• \underline{Konkatenation} eines endlichen Wortes mit einem unendlichen Wort Sei w = a_{1}a_{2}...a_{m}∈ Σ^{∗} und α = α(0)α(1)α(2)... ∈ Σ^{ω}. Dann ist w · α das unendliche Wort a_{1}a_{2}...a_{m}α(0)α(1)α(2).... Beachte: Ein unendliches Wort auf der linken Seite macht keinen Sinn. Wie üblich kann Konkatenation auf Mengen erweitert werden.

• Unendliche Iteration Es sei L ⊆ Σ^{∗} eine Menge endlicher Wörter. Wir definieren

L^{ω} := {α ∈ Σ^{ω} | α = w_{0}w_{1}w_{2}... mitw_{i} ∈ L\{ε}}

Beispiel L = {ab}. Dann ist L^{ω} = {abababab...}. Wir schreiben in solchen Fällen häufig (ab)^{ω}.

• \underline{Limes}

Es sei L ⊆ Σ^{∗}. Wir definieren

lim L := {α ∈ Σ^{ω} | es gibt unendlich vielen mitα(0,n) ∈ L}

Beispiel 4.3 Σ = {a,b}

1. L = a^{∗}b. Es gilt limL = ∅. Erklärung:

[figure: α ∈ limL; 1. Anfangsstück in a^{∗}b; a.................ab; 2. Anfangsstück in a^{∗}b; a.................aaa.....b; Widerspruch]

2. L = ba^{∗}. Es gilt limL = {baa...} = ba^{ω}.

3. L = (a^{∗}bb^{∗})^{∗}. In diesem Fall gilt

limL = {α ∈ Σ^{ω} | nach jedem Vorkommen vona kommt irgendwann

noch einb inα}

□

Als Automaten zum Akzeptieren von Mengen unendlicher Wörter (ω-Sprachen) betrachten wir normale endliche Automaten. Der Unterschied liegt in der Akzeptanzbedingung.

Definition 4.4 Ein \underline{Büchi-Automat} ist ein (nicht-deterministischer) endlicher Automat A = (Q, Σ, I, Δ, F), das heißt

• Q ist eine nicht-leere endliche Menge,

• Σ ist ein endliches Alphabet,

• I ⊆ Q ist die Anfangszustandsmenge,

• Δ ⊆ (Q × Σ × Q) ist die Übergangsrelation,

• F ⊆ Q ist die Endzustandsmenge.

Da wir uns für unendliche Wörter interessieren, betrachten wir unendliche Pfade in A

q_{0} −→^{a_{1}} q_{1} −→^{a_{2}} q_{2} −→^{a_{3}} q_{3} −→^{a_{4}} ...

wobei (q_{i},a_{i+1} ,q_{i+1} ) ∈ Δ für i ≥ 0. Die Beschriftung dieses Pfads ist ein unendliches Wort a_{1}a_{2}a_{3}a_{4}.... Wann ist nun ein Pfad \underline{erfolgreich}?

• endlicher Pfad

Der Pfad q_{0} −→^{a_{1}} q_{1} −→^{a_{2}} q_{2} −→^{a_{3}} ... −→^{a_{n}} q_{n}

ist erfolgreich, wenn

1. q_{0} ∈ I

2. q_{n} ∈ F

• unendlicher Pfad Bei unendlichen Pfaden gibt es keinen letzten Zustand q_{n}. Deshalb fordern wir, daß die Menge F unendlich oft durchlaufen wird, das heißt der unendliche Pfad q_{0} −→^{a_{1}} q_{1} −→^{a_{2}} q_{2} −→^{a_{3}} ... heißt erfolgreich, falls

1. q_{0} ∈ I

2. Es gibt unendlich viele i mit q_{i} ∈ F

Die von A \underline{akzeptierte} ω-Sprache ist

L_{ω}(A) = {α ∈ Σ^{ω} | α ist Beschriftung eines erfolgreichen Pfads }

Solche Sprachen heißen \underline{Büchi-erkennbar}. □

Beispiel 4.5 Es sei Σ = {a, b, c}.

1. A_{1}:

[figure: ⟲; ⟲; 1; 2; b,c; a,c; b; a]
L_{ω}(A_{1}) = {α ∈ Σ^{ω} | nach jedema inα kommt irgendwann einb inα}

denn Wörter, die kein a enthalten, sind auf jeden Fall in L_{ω}(A_{1}). Jedes a führt in den Zustand 2 über. Der akzeptierende Zustand 1 wird erst wieder erreicht, wenn ein b kommt.

2.

L_{2} = {α ∈ Σ^{ω} |  zwischen zweia′sinα befindet sich eine

gerade Anzahl vonb′s undc′s}.

Es reicht, zwei aufeinanderfolgende a’s zu betrachten.

A_{2} :

[figure: ⟲; ⟲; 1; 2; 3; b,c; a; b,c; b,c; a]

L_{ω}(A_{2}) = L_{2}.

□

Um die von Büchi-Automaten akzeptierten Sprachen genauer zu untersuchen, verwenden wir die folgende Abkürzung. Seien A = (Q, Σ, I, Δ,F) ein Büchi-Automat und p, q ∈ Q. Wir definieren

L_{p,q} := {w ∈ Σ^{∗} | w ist Beschriftung eines endlichen Pfads in A vonp nachq}

Offenbar sind die Sprachen L_{p,q} regulär, denn sie werden von einem endlichen Automaten (mit I = {p} und F = {q}) akzeptiert.

Lemma 4.6

L_{ω}(A) = ⋃_{{i∈I \atop f∈F}} L_{i,f} · L_{f,f}^{ω}

Beweis

“⊆” Es sei α = a_{1}a_{2}a_{3}...∈ L_{ω}(A), das heißt es gibt einen unendlichen erfolgreichen Pfad q_{0} −→^{a_{1}} q_{1} −→^{a_{2}} q_{2} −→^{a_{3}} ... mit q_{0} ∈ I und unendlich vielen i mit q_{i} ∈ F. Da F endlich ist gibt es ein f ∈ F, das unendlich oft erreicht wird. Es gibt also eine unendliche Folge 0 ≤ i_{1} < i_{2} < i_{3} < ... mit q_{i_{ν}} = f. Somit gilt

a_{1}a_{2}...a_{i_{1}} ∈ L_{q_{0},f}
a_{i_{ν}+1} ...a_{i_{ν+1}} ∈ L_{f,f}

Damit ist α ∈ L_{q_{0},f} · L_{f,f}^{ω} .

“⊇” Es sei

α = w_{0}w_{1}w_{2}w_{3}... ∈ ⋃_{{i∈I \atop f∈F}} L_{i,f} · L_{f,f}^{ω} ,

das heißt für ein Paar (i,f) ist w_{0} ∈ L_{i,f} und w_{j} ∈ L_{f,f} für j ≥ 1. Damit ist

i −→^{w_{0}} f −→^{w_{1}} f −→^{w_{2}} f −→^{w_{3}} ...

ein erfolgreicher Pfad, also ist α = w_{0}w_{1}w_{2}w_{3}... ∈ L_{ω}(A).

□

Das nächste Lemma beschreibt Abschlußeigenschaften für Büchi-erkennbare Sprachen.

Lemma 4.7

1. Ist U ⊆ Σ^{∗} regulär, so ist U^{ω} Büchi-erkennbar.

2. Ist U ⊆ Σ^{∗} regulär und L Büchi-erkennbar, so ist U · L Büchi-erkennbar.

3. Sind L_{1} und L_{2} ⊆ Σ^{ω} Büchi-erkennbar, so sind auch L_{1} ∪ L_{2} und L_{1} ∩ L_{2} Büchierkennbar.

Beweis

1. Es gilt U^{ω} = {α ∈ Σ^{ω} | α = u_{1}u_{2}u_{3}..., u_{i} ∈ U\{ε}}. Mit U ist auch U\{ε} regulär. Man sieht leicht, daß es einen Automaten für U\{ε} gibt mit den Eigenschaften

• A = (Q, Σ, q_{0}, Δ, F), das heißt A hat genau einen Anfangszustand (der kein Endzustand ist, weil ε ∉ U\{ε}).

• Für alle a ∈ Σ, q ∈ Q gilt (q,a,q_{0}) ∉ Δ, das heißt q_{0} ist von anderen Zuständen aus nicht erreichbar.

Wir definieren nun A′:= (Q, Σ, q_{0}, Δ′, {q_{0}}), wobei

Δ′= Δ ∪ {(q,a,q_{0}) | ∃f ∈ F : (q,a,f) ∈ Δ}.

Man sieht leicht, daß L_{ω}(A′) = U^{ω} gilt. Dabei ist die Idee, daß jedes Erreichen des einzigen Endzustandes q_{0} den Beginn eines neuen Wortes u_{i} aus U bedeutet.

2. Seien A = (Q_{1}, Σ, I_{1}, Δ_{1}, F_{1}) mit L(A) = U und B = (Q_{2}, Σ, I_{2}, Δ_{2}, F_{2}) mit L_{ω}(B) = L. Ohne Einschränkung sei Q_{1}∩ Q_{2} = ∅. Wir definieren

C := (Q_{1}∪ Q_{2}, Σ, I_{1}, Δ′, F_{2}),

wobei Δ′:= Δ_{1} ∪ Δ_{2} ∪ {(q,a,q′) | ∃f ∈ F_{1} : ((q,a,f) ∈ Δ_{1} ∧ q′∈ I_{2})}. Man sieht leicht, daß L_{ω}(C) = U · L^{ω} gilt.

3. Der Beweis für den Abschluß der Büchi-erkennbaren Sprachen unter Vereinigung läuft analog zu dem für reguläre Sprachen. Für den Abschluß unter Schnitt seien A_{1} = (Q_{1}, Σ, I_{1}, Δ_{1}, F_{1}) mit L_{ω}(A_{1}) = L_{1} und A_{2} = (Q_{2}, Σ, I_{2}, Δ_{2}, F_{2}) mit L_{ω}(A_{2}) = L_{2}. Gesucht ist ein Büchi-Automat B mit L_{ω}(B) = L_{1}∩ L_{2}. Sei

B := (Q_{1}× Q_{2}× {0,1,2}, Σ, I_{1}× I_{2}× {0}, Δ, F)
mitΔ = { ((q_{1}, q_{2}, i), a, (q′_{1}, q′_{2}, j)) |
• (q_{1}, a, q′_{1}) ∈ Δ_{1} und(q_{2}, a, q′_{2}) ∈ Δ_{2}
• i = 0 undq′_{1} ∈ F_{1} ⇒ j = 1
• i = 1 undq′_{2} ∈ F_{2} ⇒ j = 2
• i = 2 ⇒ j = 0
• sonsti = j }

Man beginnt also mit einer 0 in der dritten Komponente. Wenn man das erste Mal ein f_{1} ∈ F_{1} durchläuft, wird die dritte Komponente 1. Wenn man daraufhin das nächstemal ein f_{2} ∈ F_{2} durchläuft, so wird die dritte Komponente 2 und im nächsten Schritt wieder zu 0. Durchläuft man unendlich oft Elemente aus F_{1} in der ersten Komponente und unendlich oft Elemente aus F_{2} in der zweiten Komponente, so erreicht man unendlich oft einen Zustand mit dritter Komponente 2. Daher definieren wir F := Q_{1}× Q_{2}× {2}.

□

Satz 4.8 (Büchi, 1962)

1. Eine ω-Sprache L ⊆ Σ^{ω} ist Büchi-erkennbar genau dann, wenn es reguläre Sprachen U_{1}, ..., U_{n}, V_{1}, ..., V_{n} ⊆ Σ^{∗} gibt mit

L = ⋃_{i=1}^{n} U_{i}· V_{i}^{ω}.

2. Man kann ohne Einschränkung davon ausgehen, daß V_{i}· V_{i} = V_{i} gilt.

Beweis

“⇒”  1. mit Lemma 4.6 ist L = ⋃_{{q_{0}∈I \atop f∈F}} L_{q_{0},f} · L_{f,f}^{ω} 2. L_{f,f} · L_{f,f} = L_{f,f} “⇐”  1. Diese Richtung folgt mit Lemma 4.7 (V_{i}^{ω} ist Büchi-erkennbar, U_{i}V_{i}^{ω} ist Büchi-erkennbar und Büchi-erkennbare Sprachen sind bezüglich Verei- nigung abgeschlossen). □

Wegen dieses engen Zusammenhangs zwischen Büchi-erkennbaren Sprachen und regulären Sprachen heißen Büchi-erkennbare Sprachen auch \underline{ω-regulär}. Sind U_{i}, V_{i} durch reguläre Ausdrücke gegeben, so heißt die Darstellung

L = ⋃_{i=1}^{n} U_{i}V_{i}^{ω}

\underline{ω-regulärer Ausdruck} für L.

Beispiel 4.9 Sei A_{2} der endliche Automat aus Beispiel 4.5

[figure: ⟲; ⟲; 1; 2; 3; b,c; a; b,c; b,c; a]

L_{1,1} = (b ∪ c)^{∗}
L_{1,2} = (b ∪ c)^{∗}aL_{2,2}
L_{2,2} = (a ∪ (b ∪ c)(b ∪ c))^{∗}
L_{ω}(A_{2}) = L_{1,1}· L_{1,1}^{ω} ∪ L_{1,2}· L_{2,2}^{ω}
= L_{1,1}^{ω} ∪ L_{1,2}· L_{2,2}^{ω}
= ((b ∪ c)^{∗})^{ω} ∪ (b ∪ c)^{∗}· a · L_{2,2}· L_{2,2}^{ω}
= (b ∪ c)^{ω} ∪ (b ∪ c)^{∗}· a · (a ∪ (b ∪ c)(b ∪ c))^{ω}
□

Eine weitere Konsequenz aus Lemma 4.6 ist, daß man für einen Büchi-Automaten entscheiden kann, ob er eine nicht-leere Sprache akzeptiert: Man muß ein i ∈ I und ein f ∈ F finden mit L_{i,f} ≠ ∅ und L_{f,f} \{ε} ≠ ∅. Die von dem Automaten akzeptierte Sprache ist nicht-leer genau dann, wenn ein solches Paar i, f existiert. Da L_{i,f} und L_{f,f} \{ε} reguläre Sprachen sind, die von dem gegebenen Automaten akzeptiert werden (bei geeigneter Wahl der Anfangsund Endzustände), ist entscheidbar, ob es i, f mit dieser Eigenschaft gibt.

Satz 4.10

1. Das Leerheitsproblem für Büchi-Automaten ist entscheidbar.

2. Ist L eine nicht-leere Büchi-erkennbare ω-Sprache, so enthält L ein schließlich periodisches Wort, das heißt ein Wort der Form uvvv..., u ∈ Σ^{∗}, v ∈ Σ^{+} .

Beweis

1. Die erste Aussage wurde bereits durch die obige Argumentation gezeigt.

2. Ist L ≠ ∅, so gibt es i, f im Automaten mit L_{i,f} ≠ ∅ und L_{f,f} \{ε} ≠ ∅. Seien u ∈ L_{i,f} und v ∈ L_{f,f} \{ε} beliebig. Offenbar ist uvvv... ∈ L.

□ Für reguläre Sprachen kann man das Äquivalenzproblem (L(A_{1}) = L(A_{2})?) auf das Leerheitsproblem reduzieren: L_{1} = L_{2} gdw (L_{1}∩ \overline{L_{2}}) ∪ (L_{2}∩ \overline{L_{1}}) = ∅. Dies ist möglich, weil die regulären Sprachen unter Vereinigung, Schnitt und Komplement abgeschlossen sind. Bei ω-regulären Sprachen fehlt uns für ein analoges Vorgehen noch der Abschluß unter Komplementbildung. Für reguläre Sprachen wurde der Abschluß unter Komplement in zwei Schritten nachvollzogen:

1. überführe den Automaten in einen deterministischen endlichen Automaten

2. betrachte als neue Endzustandmenge Q\F, das heißt die Menge der Zustände, die zuvor keine Endzustände waren.

Bei ω-regulären Sprachen funktionieren sowohl 1. als auch 2. nicht.

Beispiel 4.11 für eine ω-reguläre Sprache, die nicht von einem deterministischen Büchi-Automaten akzeptiert wird Sei Σ = {a, b}. Der folgende nicht-deterministische Automat akzeptiert die ω-reguläre Sprache L = (a ∪ b)^{∗}b^{ω}.

[figure: ⟲; ⟲; 1; 2; a,b; b; b]

Behauptung: Diese Sprache kann nicht von einem deterministischen Büchi-Automaten akzeptiert werden. Beweis: Angenommen A = (Q, Σ, q_{0}, δ, F) ist ein deterministischer Büchi-Automat mit L_{ω}(A) = L. δ: Q × Σ → Q ist also eine Funktion. Da ab^{ω} ∈ L gilt, gibt es ein k_{1} > 0 und f_{1} ∈ F mit

q_{0} −→^{ab^{k_{1}}} f_{1}

Da ab^{k_{1}}ab^{ω} ∈ L und da A deterministisch ist gibt es ein k_{2} > 0 und f_{2} ∈ F mit

q_{0} −→^{ab^{k_{1}}} f_{1} −→^{ab^{k_{2}}} f_{2}

Iteriert man dieses Argument, so erhält man k_{1}, k_{2}, k_{3}, ... > 0 und f_{1}, f_{2}, f_{3}, ... ∈ F mit

q_{0} −→^{ab^{k_{1}}} f_{1} −→^{ab^{k_{2}}} f_{2} −→^{ab^{k_{3}}} f_{3} −→^{ab^{k_{4}}} ...

Damit ist ab^{k_{1}}ab^{k_{2}}ab^{k_{3}}... ∈ L_{ω}(A), da es einen unendlichen erfolgreichen Pfad in A gibt mit dieser Beschriftung. Aber ab^{k_{1}}ab^{k_{2}}ab^{k_{3}}... ∉ L, denn dieses Wort enthält unendlich viele a’s. Widerspruch

□

Beispiel 4.12 Auch bei deterministischen Büchi-Automaten liefert Vertauschen von Endzuständen und nicht-Endzuständen nicht den Automaten für die Komplementsprache.

Betrachtet man zum Beispiel den deterministischen Büchi-Automaten A_{1} aus Beispiel 4.5

[figure: ⟲; ⟲; 1; 2; b,c; a,c; b; a]
L_{ω}(A_{1}) = {α ∈ Σ^{ω} | nach jedema inα kommt irgendwann einb inα}

Dann gilt für den Komplement-Automaten \overline{A_{1}}

[figure: ⟲; ⟲; 1; 2; b,c; a,c; b; a]

L_{ω}(A_{1}) ∩ L_{ω}(\overline{A_{1}}) ≠ ∅, da zum Beispiel (ab)^{ω} in beiden Sprachen enthalten ist.

□

Wie Beispiel 4.11 zeigt, ist die Klasse der von Büchi-Automaten akzeptierten Sprachen kleiner als die Klasse der ω-regulären Sprachen.

Satz 4.13 Für L ⊆ Σ^{ω} sind äquivalent

1. L wird von einem deterministischen Büchi-Automaten akzeptiert

2. L = limU für eine reguläre Sprache U ⊆ Σ^{∗}

Beweis Es sei A = (Q, Σ, q_{0}, δ, F) ein deterministischer endlicher Automat. Dann gilt

Behauptung: Für α ∈ Σ^{ω} sind äquivalent

1. α ∈ L_{ω}(A)

2. α ∈ limL(A), das heißt unendlich viele Anfangsstücke von α sind in L(A)

denn (Beweis der Behauptung): “1 ⇒ 2”

Es sei α ∈ L_{ω}(A), dann folgt daraus, daß es f_{1}, f_{2}, f_{3}, ... ∈ F und
u_{1}, u_{2}, u_{3}, ... ∈ Σ^{+} mit α = u_{1}u_{2}u_{3}... und

q_{0} −→^{u_{1}} f_{1} −→^{u_{2}} f_{2} −→^{u_{3}} f_{3} −→^{u_{4}} ...

gibt. Damit folgt u_{1}, u_{1}u_{2}, u_{1}u_{2}u_{3}, ...∈ L(A). Also liegen unendlich viele Anfangsstücke von α in L(A).

“2 ⇒ 1”

Es seien u_{1}, u_{1}u_{2}, u_{1}u_{2}u_{3}, ... mit u_{i} ∈ Σ^{+} für i ∈ IN die unendlich vielen Anfangsstücke von α mit u_{1}...u_{i} ∈ L(A). Da A deterministisch ist, heißt dies, daß es f_{1}, f_{2}, f_{3}, ... ∈ F gibt mit

q_{0} −→^{u_{1}} f_{1} −→^{u_{2}} f_{2} −→^{u_{3}} f_{3} −→^{u_{4}} ...

Es folgt α = u_{1}u_{2}u_{3}... ∈ L_{ω}(A), da es einen unendlichen erfolgreichen Pfad mit der Beschriftung α in A gibt.

Beachte: Bei nicht-deterministischen Automaten könnte es die folgende Situation geben (vergleiche auch Beispiel 4.11):

q_{0}−→^{u_{1}} f_{1}

q_{0} −→^{u_{1}} q_{1} ∉ F −→^{u_{2}} f_{2}

Damit ist die Behauptung gezeigt und es ergibt sich der obige Satz.

□

Korollar 4.14 Die Klasse der von \underline{deterministischen Büchi-Automaten} akzeptierten Sprachen ist nicht abgeschlossen bezüglich Komplementbildung.

Beweis In Beispiel 4.11 haben wir gesehen, daß L = (a ∪ b)^{∗}b^{ω} nicht von einem deterministischen Büchi-Automaten akzeptiert wird. Man sieht leicht, daß

\overline{L}= \{a,b\}^{ω}\L

die ω-Sprache ist, welche alle ω-Wörter α mit der Eigenschaft “ α enthält unendlich viele a’s ” enthält. Daher ist

\overline{L}= lim(b^{∗}a)^{∗}.

Diese Sprache wird aber von einem deterministischen Büchi-Automaten akzeptiert, da \overline{L}= limU ist für eine reguläre Sprache U.

□

Die Klasse der ω-regulären Sprachen ist unter Komplement abgeschlossen. Dies ist schwieriger zu zeigen als für reguläre Sprachen.

Hauptsatz 4.15 Ist L ⊆ Σ^{ω} ω-regulär, so auch \overline{L}= Σ^{ω}\L.

□

Um diesen Satz zu beweisen stellen wir L und \overline{L} als endliche Vereinigung von ω-Sprachen U, V dar. Diese Sprachen werden die Klassen einer Kongruenzrelation ∼_{A} von endlichem Index sein. Es sei dazu A = (Q, Σ, I, Δ, F) ein Büchi-Automat mit L = L_{ω}(A). Wir schreiben p F ; w^{−→} q um auszudrücken, daß es in A einen Pfad von p nach q gibt mit der Beschriftung w, der mindestens einen Zustand aus F enthält. Die Mengen

L_{p,q}^{F} := \{w | p \begin{matrix}F \\ −→ \\ w \end{matrix} q\}

sind offenbar regulär, da sie sich als Vereinigung regulärer Sprachen darstellen lassen:

L_{p,q}^{F} = ⋃_{f∈F} L_{p,f} · L_{f,q}

Definition 4.16 ∼_{A} ist auf Σ^{∗} wie folgt definiert:

u ∼_{A} v gdw ∀ p,q ∈ Q:

1) p _{\overrightarrow{u}} q gdw p _{\overrightarrow{v}} q

2) p \begin{matrix}F \\ −→ \\ u \end{matrix} q gdw p \begin{matrix}F \\ −→ \\ v \end{matrix} q

□

Lemma 4.17 ∼_{A} ist eine Kongruenzrelation, die endlichen Index hat (das heißt sie hat endlich viele ∼_{A}- Kongruenzklassen).

Beweis

1. ∼_{A} ist Kongruenzrelation Offenbar ist ∼_{A} Äquivalenzrelation (dies sieht man an dem gdw auf der rechten Seite der Definition). Kongruenz: u ∼_{A} v ⇒ ∀x,y ∈ Σ^{∗} : xuy ∼_{A} xvy Es gelte u ∼_{A} v. Angenommen es gilt p \begin{matrix}F \\ −→ \\ xuy \end{matrix} q, es gibt also p′und q′mit p _{\overrightarrow{x}} p′ _{\overrightarrow{u}} q′ _{\overrightarrow{y}} q

1. Fall p \begin{matrix}F \\ −→ \\ x \end{matrix} p′, das heißt f ∈ F kommt in p _{\overrightarrow{x}} p′vor.

Wegen u ∼_{A} v folgt aus p′ _{\overrightarrow{u}} q′auch p′ _{\overrightarrow{v}} q′. Damit gibt es einen Pfad p \begin{matrix}F \\ −→ \\ x \end{matrix} p′ _{\overrightarrow{v}} q′ _{\overrightarrow{y}} q,

das heißt p \begin{matrix}F \\ −→ \\ xvy \end{matrix} q.

2. Fall q′ \begin{matrix}F \\ −→ \\ y \end{matrix} q (analog zum 1. Fall)

3. Fall p′ \begin{matrix}F \\ −→ \\ u \end{matrix} q′

Wegen u ∼_{A} v folgt p′ \begin{matrix}F \\ −→ \\ v \end{matrix} q′. Damit gibt es p _{\overrightarrow{x}} p′ \begin{matrix}F \\ −→ \\ v \end{matrix} q′ _{\overrightarrow{y}} q, das heißt p \begin{matrix}F \\ −→ \\ xvy \end{matrix} q.

Die anderen Fälle ( p \begin{matrix}F \\ −→ \\ xvy \end{matrix} q ⇒ p \begin{matrix}F \\ −→ \\ xuy \end{matrix} q, p _{\overrightarrow{xuy}} q ⇔ p _{\overrightarrow{xvy}} q) können entsprechend behandelt werden.

2. ∼_{A} hat endlichen Index Die ∼_{A}-Klasse eines Wortes w ist charakterisiert durch das folgende Paar von Mengen:

(\{(p,q) | p _{\overrightarrow{w}} q\}, \{(p,q) | p \begin{matrix}F \\ −→ \\ w \end{matrix} q\})

Es gibt daher maximal 2^{|Q×Q|} · 2^{|Q×Q|} verschiedene Klassen.

□

Wie sieht nun die ∼_{A}-Klasse [w] eines Wortes w aus? Lemma 4.18

1.

[w] = ⋂_{{p,q∈Q \atop w∈Lp,q}} L_{p,q}∩ ⋂_{{p,q∈Q \atop w∉Lp,q}} \overline{L_{p,q}}∩ ⋂_{{p,q∈Q \atop w∈L{F \atop p,q}}} L_{p,q}^{F}∩ ⋂_{{p,q∈Q \atop w∉L{F \atop p,q}}} \overline{L_{p,q}^{F}}

2. Insbesondere ist daher [w] ⊆ Σ^{∗} eine reguläre Sprache. Beweis

1. “⊆” Sei u ∈ [w], das heißt u ∼_{A} w. Ist w ∈ L_{p,q} (\overline{L_{p,q}}, L_{p,q}^{F}, \overline{L_{p,q}^{F}}), so folgt wegen

u ∼_{A} w (das heißt p _{\overrightarrow{u}} q ⇔ p _{\overrightarrow{w}} q), daß u ∈ L_{p,q} (\overline{L_{p,q}}, L_{p,q}^{F}, \overline{L_{p,q}^{F}}) “⊇” Sei u aus dem Durchschnitt auf der rechten Seite. Es ist zu zeigen, daß u ∼_{A} w

gilt.

– Aus p _{\overrightarrow{w}} q folgt w ∈ L_{p,q} (⇒ L_{p,q} liegt im Schnitt) und damit u ∈ L_{p,q}, das

heißt p _{\overrightarrow{u}} q.

– Aus p _{\begin{matrix}↛ \\ w \end{matrix}} q folgt w ∈ \overline{L_{p,q}} und damit ist auch u ∈ \overline{L_{p,q}}, das heißt p _{\begin{matrix}↛ \\ u \end{matrix}} q.

– Für \begin{matrix}F \\ → \\ w \end{matrix} entsprechend.

2. folgt unmittelbar aus 1., da L_{p,q} und L_{p,q}^{F} regulär sind und reguläre Sprachen unter

Schnitt abgeschlossen sind.

□

Hauptsatz 4.15 ergibt sich sehr leicht aus dem folgenden Satz: Satz 4.19 Es sei A ein Büchi-Automat.

1. Für jedes Paar U, V von ∼_{A}-Klassen gilt:

(a) U · V^{ω} ∩ L_{ω}(A) ≠ ∅ ⇒ U · V^{ω} ⊆ L_{ω}(A)

(b) U · V^{ω} ∩ \overline{L_{ω}(A)}≠ ∅ ⇒ U · V^{ω} ⊆ \overline{L_{ω}(A)}

2. Für jedes α ∈ Σ^{ω} existieren ∼_{A}-Klassen U, V mit α ∈ U · V^{ω}.

□

Wir überlegen zunächst, warum hieraus folgt, daß \overline{L_{ω}(A)}ω-regulär ist. Es folgt aus 1. und 2. des Satzes, daß

•

L_{ω}(A) = ⋃_{{U,V ∼_{A}−Klassen \atop U·V^{ω} ⊆Lω (A)}} U · V^{ω}

denn

“⊇” eine Vereinigung über Teilmengen von L_{ω}(A) wird immer eine Teilmenge von L_{ω}(A) sein. “⊆” Mit 2. des Satzes existiert zu jedem α ∈ L_{ω}(A) ein Paar U, V von ∼_{A}-Klassen mit α ∈ U ·V^{ω}. Mit 1. gilt dann U ·V^{ω} ⊆ L_{ω}(A) und damit liegt U ·V^{ω} dann komplett in der Vereinigung.

•

\overline{L_{ω}(A)}= \overbrace{⋃_{{U,V ∼_{A}−Klassen \atop U·V^{ω} ⊆\overline{Lω (A)}}}}^{endlich, da ∼_{A} endl. Index hat}U · V^{ω}

Da alle ∼_{A}-Klassen regulär sind, ist mit Satz 4.8 \overline{L_{ω}(A)}ω-regulär. Wir verwenden zum Beweis von Satz 4.19 ein kombinatorisches Resultat, das auch in anderen Bereichen nützlich ist. Dazu zunächst eine Definition.

Definition 4.20 Für eine Menge M bezeichne [M]^{2} die Menge aller zweielementigen Teilmengen von M. Es sei nun

[M]^{2} = A_{1} ∪^{·} A_{2} ∪^{·} ... ∪^{·} A_{n}

eine Zerlegung von [M]^{2} in endlich viele disjunkte Klassen. Eine Teilmenge X von M heißt \underline{homogen} für die Partition, falls es ein i gibt mit [X]^{2} ⊆ A_{i}.

□

Beispiel

[IN]^{2} = A ∪^{·} B,

wobei

A = {{i, j} | i ≠ j undi ≡ j(2)}
B = {{i, j} | i ≠ j undi ≢ j(2)}

i ≡ j(2) heißt i ist kongruent zu j modulo 2. Die Mengen G = {i ∈ IN| i gerade} und U = {i ∈ IN| i ungerade} sind beide homogen, da [G]^{2} ⊆ A und [U]^{2} ⊆ A.

Satz 4.21 (Ramsey) Es sei [IN]^{2} = A_{1} ∪^{·} ... ∪^{·} A_{n} eine disjunkte Zerlegung von [IN]^{2}. Dann gibt es eine \underline{unendliche} Teilmenge X ⊆ IN, die homogen für diese Zerlegung ist.

□

Der Beweis findet sich zum Beispiel in J. G. Rosenstein: “Linear Orderings”, Academic Press, 1982, Seiten 111, 112.

Beweis von Satz 4.19

1. Es sei α ∈ UV^{ω} ∩ L_{ω}(A), Das heißt

(a) α = uv_{1}v_{2}v_{3}..., mit u ∈ U und v_{i} ∈ V \{ε}

(b) Es gibt einen erfolgreichen unendlichen Pfad

q_{0} −→^{u} q_{1} −→^{v_{1}} q_{2} −→^{v_{2}} q_{3} −→^{v_{3}} ...

mit q_{0} ∈ I. Da dieser Pfad erfolgreich ist werden unendlich oft Zustände aus F erreicht, das heißt es gibt unendlich viele i ≥ 1, so daß sogar

q_{i} \begin{matrix}F \\ −→ \\ v_{i} \end{matrix} q_{i+1}

Für den Beweis von Teil (a) sei nun β ∈ UV^{ω}. Wir müssen β ∈ L_{ω}(A) zeigen. Es gilt β = u′v′_{1}v′_{2}v′_{3}... mit u′∈ U, v′_{i}∈ V. U, V sind ∼_{A}-Klassen. Daher gilt u ∼_{A} u′ und v_{i} ∼_{A} v′_{i}. Es folgt daraus, daß es einen Pfad

q_{0} −→^{u′} q_{1} −→^{v′_{1}} q_{2} −→^{v′_{2}} q_{3} −→^{v′_{3}} ...

gibt, auf dem für unendlich viele i gilt

q_{i} \begin{matrix}F \\ −→ \\ v_{i} \end{matrix} q_{i+1}

Damit ist der Pfad erfolgreich, das heißt β = u′v′_{1}v′_{2}v′_{3}... ∈ L_{ω}(A). Teil (b) folgt unmittelbar: Es sei α ∈ \overline{L_{ω}(A)}∩UV^{ω}. Angenommen β ∈ L_{ω}(A)∩UV^{ω}. Mit Teil (a) folgt nun UV^{ω} ⊆ L_{ω}(A), also α ∈ L_{ω}(A). Dies ist ein Widerspruch.

2. Es sei α ∈ Σ^{ω}. Zusammen mit ∼_{A} liefert α eine \underline{Zerlegung von [IN]^{2}}. Es seien U_{1}, U_{2}, ..., U_{n} die (endlich vielen) ∼_{A}-Klassen.

A_{ν} := {{i,j} | i < j undα(i + 1,j) ∈ U_{ν}}

wobei ν = 1, ..., n. Die Klassen einer Kongruenzrelation liefern eine disjunkte Zerlegung

[IN]^{2} = A_{1} ∪^{·} ... ∪^{·} A_{n}

Mit Satz 4.21 (Ramsey) gibt es eine unendliche Menge X ⊆ IN für diese Zerlegung, die homogen ist. Es gibt also ein ν, 1 ≤ ν ≤ n, so daß [X]^{2} ⊆ A_{ν}, das heißt für i, j ∈ X mit i < j gilt α(i + 1,j) ∈ U_{ν}. Da X unendlich ist gibt es eine unendliche Folge i_{1}, i_{2}, i_{3}, ... von Elementen von X mit i_{j} + 1 < i_{j+1} . Damit gilt

α(i_{j} + 1,i_{j+1} ) ∈ U_{ν}\{ε}

Es sei U die ∼_{A}-Klasse von α(0,i_{1}). Dann ist

α = α(0,i_{1})α(i_{1}+ 1,i_{2})α(i_{2}+ 1,i_{3})... ∈ UU_{ν}^{ω}

□

Damit ist der Beweis abgeschlossen, daß die Klasse der Büchi-erkennbaren Sprachen unter Komplement abgeschlossen ist.

Korollar 4.22 Zu einem Büchi-Automaten A kann man effektiv einen Büchi-Automaten B konstruieren mit

L_{ω}(B) = \overline{L_{ω}(A)}.

Beweis

1. Die ∼_{A}-Klassen (bzw. endliche Automaten dafür) können effektiv konstruiert werden. Lemma 4.18 zeigt, wie man sie aus den Sprachen L_{p,q} und L_{p,q}^{F} erhält.

2. Für ein Paar U, V von ∼_{A}-Klassen ist mit Satz 4.10 entscheidbar, ob

U · V^{ω} ∩ L_{ω}(A) = ∅.

3. Da

\overline{L_{ω}(A)}= ⋃_{{U,V ∼_{A}−Klassen \atop UV^{ω} ∩Lω (A)=∅}} U · V^{ω}

kann man den Büchi-Automaten für die Vereinigung aus den Büchi-Automaten für die U · V^{ω} erhalten.

□

Korollar 4.23 Das Äquivalenzproblem für Büchi-Automaten ist entscheidbar.

Beweis

L_{ω}(A_{1}) = L_{ω}(A_{2}) gdw (L_{ω}(A_{1})\L_{ω}(A_{2}) ∪ (L_{ω}(A_{2})\L_{ω}(A_{1})) = ∅
□

Wir wissen, daß \underline{deterministische Büchi-Automaten} nicht alle \underline{ω-regulären} Sprachen erkennen können. Wir betrachten nun ein modifiziertes Automatenmodell, in dem bereits die deterministischen Automaten alle ω-regulären Sprachen erkennen.

Definition 4.24 Ein \underline{Muller-Automat} ist ein \underline{deterministischer} endlicher Automat

A = (Q, Σ, q_{0}, δ, F),

wobei

• Q, Σ, q_{0}, δ sind wie bei deterministischen Büchi-Automaten definiert

• F ⊆ 2^{Q}, das heißt F ist eine Menge von Mengen von Endzuständen.

Ein \underline{unendlicher Pfad}

p_{0} −→^{a_{1}} p_{1} −→^{a_{2}} p_{2} −→^{a_{3}} ...

in einem Muller-Automaten heißt \underline{erfolgreich}, falls gilt

• er beginnt mit dem Anfangszustand, das heißt p_{0} = q_{0}.

• {p ∈ Q | es gibt unendlich vielei mitp = p_{i}} ∈ F, das heißt die Menge der Zustände, die auf dem Pfad unendlich oft vorkommen, liegt in F.

L_{ω}(A) := {α ∈ Σ^{ω} | α beschriftet erfolgreichen Pfad in A} □

Beispiel 4.25 Es sei L = (a ∪ b)^{∗}b^{ω}. In Beispiel 4.11 haben wir gesehen, daß es keinen deterministischen Büchi-Automaten für L gibt. Der folgende \underline{deterministische Muller-Automat} akzeptiert L:

[figure: ⟲; ⟲; 1; 2; a; b; a; b]

mit F = {{2}}. Damit 2 unendlich oft durchlaufen wird, 1 aber nicht unendlich oft, darf ab einer Stelle im Wort nur noch b vorkommen. Beachte: Ein Büchi-Automat mit F = {2} akzeptiert zum Beispiel auch (ab)^{ω}.

□

Satz 4.26 Für eine ω-Sprache L sind äquivalent:

1. L ist ω-regulär, das heißt L wird von einem nicht-deterministischen Büchi-Automaten akzeptiert

2. L wird von einem (deterministischen) Muller-Automaten akzeptiert Beweis “2 ⇒ 1”

Es sei A = (Q, Σ, q_{0}, δ, F) ein deterministischer Muller-Automat, dann gilt

L = L_{ω}(A) = ⋃_{F ⊆F} ( ⋂_{q∈F} limL_{q_{0},q}∩ ⋂_{q∈Q\F} \overline{limL_{q_{0},q}})

limL_{q_{0},q} enthält die ω-Wörter α, die einen unendlichen Pfad beschriften, der q unendlich oft enthält. Beachte: A ist deterministisch.

“1 ⇒ 2”

Der Beweis dieser Richtung ist mindestens so aufwendig wie der Beweis von Satz 4.15. Wir lassen diesen Beweis daher weg.

□

Satz 4.27 Ist L ⊆ Σ^{ω} von einem deterministischen Muller-Automaten akzeptiert, so auch \overline{L}:= Σ^{ω}\L.

Beweis Es sei L := L_{ω}(A) für einen deterministischen Muller-Automaten A = (Q, Σ, q_{0}, δ, F). Man sieht leicht, daß B = (Q, Σ, q_{0}, δ, 2^{Q}\F) die Sprache Σ^{ω}\L akzeptiert.

□

64 4 Unendliche Wörter und Büchi-Automaten

Unendliche Wörter und logische Formeln

Ziel dieses Abschnitts ist es, eine Klasse von Formeln anzugeben, welche genau die ωregulären Sprachen beschreibt. Wie im Fall regulärer Sprachen endlicher Wörter genügen die Formeln der Logik erster Stufe nicht, um diese Sprachklasse zu beschreiben. Man benötigt zusätzlich Quantifizierung über einstellige Prädikate. Definition 5.1 Formeln der \underline{Monadischen Logik zweiter Stufe eines Nachfolgers} (S1S: \underline{s}econdorder logic of \underline{1} \underline{s}uccessor) sind aufgebaut mit Hilfe von

• n einstelligen Prädikatensymbolen P_{1}, ..., P_{n},

• einem einstelligen Funktionssymbol s,

• einem Konstantensymbol \underline{0},

• einem zweistelligen Prädikatensymbol <,

• den Booleschen Operatoren ∧, ∨, ¬,

• den Quantoren erster Stufe ∃x, ∀x, wobei x für Elemente des Interpretationsbereichs steht,

• den Quantoren zweiter Stufe ∃X, ∀X, wobei X für Teilmengen des Interpretationsbe-

reichs steht. Als Interpretationsbereich betrachten wir die natürlichen Zahlen ω, wobei

• \underline{0} als 0,

• s als Nachfolgerfunktion m ↦ m + 1,

• < als die übliche Ordnung auf ω interpretiert werden. Wie im endlichen Fall sei Σ = {0, 1}^{n}. Eine gegebene Interpretation P_{1}^{I}, ...,P_{n}^{I} der Symbole P_{1}, ..., P_{n}entspricht einem ω-Wort α(0)α(1)α(2)...∈ Σ^{ω}, wobei α(m) = (b_{m1}, b_{m2}, ..., b_{mn}) mit b_{mi}= \{ {1 falls m∈P_{i}^{I} \atop 0 falls m∉P_{i}^{I}} . Für eine geschlossene S1S-Formel φ schreiben wir wieder α ⊧ φ, wenn die Interpretation, welche dem α entspricht, die Formel φ wahr macht. Die von φ akzeptierte Sprache ist L_{ω}(φ) = {α ∈ Σ^{ω} | α ⊧ φ}.

□

Beispiel 5.2 Es sei n = 1, das heißt Σ = {0, 1}.

1.

φ = P_{1}(\underline{0})∧
∀x P_{1}(x) → ¬P_{1}(s(x))∧
∀x ¬P_{1}(x) → P_{1}(s(x))
L_{ω}(φ) = {101010...} = (10)^{ω}

2.

L_{1} = {α ∈ Σ^{ω} | nach jeder 1 inα kommt noch eine0} Für φ = ∀x (P_{1}(x) → ∃y (x < y ∧ ¬P_{1}(y))) gilt L_{ω}(φ) = L_{1}.

3.

L_{2} = {α ∈ Σ^{ω} | zwischen zwei Vorkommen von 1 inα befindet sich

eine gerade Anzahl von Vorkommen von 0 }

φ = ∀x ∀y (x < y∧

P_{1}(x)∧ P_{1}(y)∧ ∀z (x < z ∧ z < y → ¬P_{1}(z)) → ∃X ∃Y (∀z ¬(X(z) ∧ Y (z))∧ X(s(x))∧ ∀z (X(z) → Y (s(z)))∧ ∀z (Y (z) → X(s(z)))∧ ∀z (s(z) = y → Y (z)))

□

Wie im endlichen Fall verwenden wir die Abkürzung Q_{a}(x) für die Formel, die ausdrückt, daß an Position x das Symbol a ∈ Σ steht.

Lemma 5.3 Sowohl \underline{0} als auch < kann in S1S mit Hilfe der übrigen Symbole ausgedrückt werden.

Beweis

1. x = \underline{0} ist äquivalent zu ¬∃y (y < x)

2. x < y entspricht ∃X (¬X(x) ∧ X(y) ∧ ∀z (X(z) → X(s(z))))

□

Satz 5.4 Für eine ω-Sprache L sind äquivalent:

1. L ist ω-regulär

2. L = L_{ω}(φ) für eine geschlossene S1S-Formel φ

□

Beweis “1 ⇒ 2” Es sei A = (Q, Σ, I, Δ, F) ein Büchi-Automat mit L = L_{ω}(A). Wir werden die Existenz eines erfolgreichen Pfads in A mit Hilfe einer S1S-Formel bechreiben. Es sei Q = {q_{0}, q_{1}, ..., q_{m}} und ohne Einschränkung sei I = {q_{0}, q_{1}, ..., q_{k}} für ein k ≤ m. Wir verwenden Variablen Y_{0}, Y_{1}, ..., Y_{m} zweiter Stufe, wobei Y_{i}(x) als “der x-te Zustand im Pfad ist q_{i}” gelesen werden soll.

∃Y_{0}...∃Y_{m}

(∀x ⋀ _{0≤i<j≤m} ¬(Y_{i}(x) ∧ Y_{j}(x))  die Mengen sind disjunkt
∧(Y_{0}(\underline{0}) ∨ ...∨ Y_{k}(\underline{0}))  der Pfad beginnt mit einem Anfangszustand
∧∀x⋁ _{(q_{i},a,q_{j})∈Δ} Y_{i}(x) ∧ Q_{a}(x) ∧ Y_{j}(s(x)) an Pos. s(x) steht ein bzgl. Δ erlaubter Nachfolgezust.
∧⋁ _{q_{i}∈F} ∀x ∃y (x < y ∧ Y_{i}(y)))  einer der Endzustände wird unendlich oft durchlaufen

Nach Konstruktion erfüllt α ∈ Σ^{ω} diese Formel genau dann, wenn α Beschriftung eines erfolgreichen Pfads ist. “2 ⇒ 1” Wir bringen für diese Richtung zunächst S1S-Formeln in eine \underline{Normalform}:

1. Es dürfen nur noch Variablen X_{i} zweiter Ordnung auftreten und keine Variablen x erster Ordnung.

2. Atomare Formeln haben die Gestalt

• X_{i} ⊆ X_{j} (mit Semantik ∀x X_{i}(x) → X_{j}(x))

• Succ(X_{i}) = X_{j} (mit Semantik X_{i} = {m}, X_{j} = {n} und n = m + 1)

Dabei sind X_{i}, X_{j} Variablen zweiter Stufe oder Prädikate P_{1}, ..., P_{n}.

Formeln, welche aus diesen atomaren Formeln mit Booleschen Operatoren und Quantoren zweiter Stufe aufgebaut sind, heißen \underline{S1S_{0}-Formeln}. Behauptung: Jede S1S-Formel kann in eine äquivalente S1S_{0}-Formel überführt werden. Beweis (der Behauptung):

i) Wir haben in Lemma 5.3 gesehen, daß \underline{0} und < eliminiert werden können.

ii) Geschachtelte Anwendungen der Nachfolgerfunktion können wie folgt eliminiert werden:

x = \underbrace{s(s(s(...s}_{m−mal}(y)...)))

ist äquivalent zu

∃y_{1}...∃y_{m−1} (y_{1} = s(x) ∧ y_{2} = s(y_{1}) ∧ ...∧ y = s(y_{m−1}))

iii) Wir haben nun ohne Einschränkung nur noch atomare Formeln der Gestalt

x = y, s(x) = y, P_{i}(x), X(x).

Wir verwenden folgende Abkürzungen:

– “X = Y ” für “X ⊆ Y ∧ Y ⊆ X”

– “X ≠ Y ” für “¬(X = Y)”

– “Einer(X)” für \begin{aligned}“∃Y & (Y ⊆ X) ∧ (Y ≠ X)∧ \\ & ∀Z (Z ⊆ X → Z = X ∨ Z = Y)” \end{aligned}

iv) Variablen erster Stufe werden wie im folgenden Beispiel eliminiert:

\begin{matrix}∀x & ∃y & (s(x) = y & ∧ & Z(y)) \\ ∀X (Einer(X) → & ∃Y (Einer(Y) ∧ & Succ(X) = Y & ∧ & Y ⊆ Z)) \end{matrix}

Wir können nun davon ausgehen, daß die S1S-Formel φ in S1S_{0}-Form gegeben ist. Wir zeigen durch Induktion über den Aufbau von S1S_{0}-Formeln φ, daß L_{ω}(φ) ω-regulär ist. Wir betrachten hier auch offene Formeln mit freien Variablen zweiter Stufe, wobei diese Variablen bei der Definition der akzeptierten Sprache wie einstellige Prädikatensymbole behandelt werden. Beispiel: Die Formel ∃Y (X ⊆ Y ∧ P_{1} ⊆ Y) liefert eine ω-Sprache über Σ = {0,1}^{2}, da P_{1} und X “frei” vorkommen. Induktionsanker (Konstruktion von Büchi-Automaten für atomare Formeln) Atomare Formeln sind von der Gestalt X ⊆ Y oder Succ(X) = Y. Diese definieren Sprachen über Σ = {0,1}^{2}, da zwei “freie Variablen” vorkommen. Ohne Einschränkung sei in Zeichen des Alphabets die erste Komponente X und die zweite Komponente Y.

1.

L_{ω}(X ⊆ Y) = {α = α_{0}α_{1}α_{2}... |  für (b_{i,1}, b_{i,2}) = α_{i} ∈ Σ gilt

\underbrace{b_{i,1} = 1}_{i∈X} ⇒ \underbrace{b_{i,2} = 1}_{i∈Y}\}

Die Sprache L_{ω}(X ⊆ Y) wird also akzeptiert von dem Büchi-Automaten

[figure: ⟲; (0,0), (0,1), (1,1)]

2.

L_{ω}(Succ(X) = Y) = {α = α_{0}α_{1}α_{2}... |  für α_{i} = (b_{i,1}, b_{i,2}) gilt :

es gibt eink mit

• \underbrace{b_{k,1} = 1}_{k∈X}∧\underbrace{b_{k+1,2} = 1}_{k+1∈Y}

• b_{j,1} = 0 für j ≠ k

• b_{j,2} = 0 für j ≠ k + 1} Die Sprache L_{ω}(Succ(X) = Y) wird akzeptiert von dem Büchi-Automaten

[figure: ⟲; ⟲; (0,0); (0,0); (0,1); (1,0)]

Induktionsschritt (Die Annahme sei gezeigt für φ) Wir beschränken uns auf Disjunktion, Negation und Existenzquantoren, da sich Konjunktion und Allquantoren damit darstellen lassen.

1. L_{ω}(¬φ) = Σ^{ω}\L_{ω}(φ)

Die Induktionsvoraussetzung liefert, daß L_{ω}(φ) ω-regulär ist. Mit Satz 4.15^{1} ist daher auch \overline{L_{ω}(φ)} = Σ^{ω}\L_{ω}(φ) ω-regulär.

2. φ = φ_{1}∨ φ_{2} Die Disjunktion entspricht im Prinzip der Vereinigung. Allerdings können bei φ = φ_{1} ∨ φ_{2} die in φ_{1} und φ_{2} vorkommenden freien Variablen und Prädikatensymbole verschieden sein. Beispiel φ(X_{1},X_{2},X_{3}) = φ_{1}(X_{1},X_{2}) ∨ φ_{2}(X_{2},X_{3}) Wir erweitern φ_{1} und φ_{2} um die fehlenden Variablen, indem wir trivial-wahre Formeln anfügen, die diese enthalten, zum Beispiel φ̂_{1}(X_{1},X_{2},X_{3}) = φ_{1}(X_{1},X_{2}) ∧ X_{3} = X_{3} φ̂_{2}(X_{1},X_{2},X_{3}) = φ_{2}(X_{2},X_{3}) ∧ X_{1} = X_{1} Ist A_{1} ein Automat für φ_{1}(X_{1},X_{2}), so erhält man den Automaten Â_{1} für φ̂_{1}(X_{1},X_{2},X_{3}) wie folgt: Anstelle von Σ = {0,1}^{2} verwendet man Σ̂ = {0,1}^{3}. In Â_{1} gibt es den Übergang

q −→^{(b_{1},b_{2},b_{3})}q′

genau dann, wenn

q −→^{(b_{1},b_{2})}q′

ein Übergang in A_{1} ist. Entsprechend erhält man aus dem Automaten A_{2} für φ_{2} einen Automaten Â_{2} für φ̂_{2}.

L_{ω}(φ(X_{1},X_{2},X_{3})) = L_{ω}(φ̂_{1}(X_{1},X_{2},X_{3})) ∪ L_{ω}(φ̂_{2}(X_{1},X_{2},X_{3}))

= \underbrace{L_{ω}(Â_{1}) ∪ L_{ω}(Â_{2})}

ω−regulär, da Â1 und Â2 Büchi−Automaten sind und ω−reguläre Sprachen bezüglich Vereinigung abgeschlossen sind

3. φ(X_{1},...,X_{n}) = ∃Y ψ(Y,X_{1},...,X_{n}) Ist A ein Automat für ψ(Y,X_{1},...,X_{n}), so erhält man einen Automaten für φ(X_{1},...,X_{n}) wie folgt: Ersetze jeden Übergang

q −→^{(b_{0},b_{1},...,b_{n})}q′

in A durch einem Übergang

q −→^{(b_{1},...,b_{n})}q′

□

1Satz 4.15 wurde bewiesen, um ihn an dieser Stelle anwenden zu können

Damit ist der Beweis von Satz 5.4 abgeschlossen.

Beispiel 5.5 Dies ist ein Beispiel für die Anwendung von Teil 2 des Beweises von Satz 5.4.

φ = ∃Y (X ⊆ Y ∨ Succ(Y) = Z)

ist eine S1S_{0}-Formel mit zwei freien Variablen, X und Y.

A_{1} ist ein Automat für X ⊆ Y, mit 1. Komponente X und 2. Komponente Y: [figure: ⟲; (0,0), (0,1), (1,1)] Â_{1} ist ein Automat für X ⊆ Y mit einer zusätzlichen Stelle für Z:

[figure: ⟲; (0,0,0), (0,1,0), (1,1,0); (0,0,1), (0,1,1), (1,1,1)]

A_{2} ist ein Automat für Succ(Y) = Z, mit 1. Komponente Y und 2. Komponente Z:

[figure: ⟲; ⟲; (0,0); (0,0); (0,1); (1,0)]

Â_{2} ist ein Automat für Succ(Y) = Z mit einer zusätzlichen Stelle für X als 1. Komponente:

[figure: ⟲; ⟲; (0,0,0), (1,0,0); (0,0,0), (1,0,0); (0,0,1); (1,0,1); (0,1,0); (1,1,0)]

Der Automat Â := Â_{1} ∪^{·} Â_{2} ist ein Automat für X ⊆ Y ∨ Succ(Y) = Z. Ein Bild dieses Automaten erhält man, indem man die Graphiken für Â_{1} und Â_{2} nebeneinander zeichnet. Beachte: Dieser Automat hat zwei Anfangszustände.

[figure: ⟲; ⟲; ⟲; (0,0,0), (1,0,0); (0,0,0), (1,0,0); (1,0,1), (0,0,1); (1,1,0), (0,1,0); (0,0,0), (0,1,0), (1,1,0); (0,0,1), (0,1,1), (1,1,1)]

Den Automaten A für die durch φ beschriebene Sprache erhält man aus Â durch Streichen der zweiten Komponente innerhalb der Beschriftungen der Transitionen – dies ist genau die Komponente für Y. A :

[figure: ⟲; ⟲; ⟲; (0,0), (1,0); (0,0), (1,0); (0,1), (1,1); (1,0), (0,0); (0,0), (0,1); (1,0), (1,1)]
□

Der Beweis zeigt insbesondere, wie man zu einer S1S-Formel φ effektiv einen Büchi-Automaten A konstruieren kann mit L_{ω}(φ) = L_{ω}(A). Es folgt, daß man von einer (geschlossenen^{2}) S1S-Formel φ entscheiden kann, ob sie in der Interpretation (ω, <, + 1, 0) gültig ist oder nicht, denn es gilt ja

φ ist gültig gdw ¬φ hat kein Modell gdw L_{ω}(¬φ) = ∅

Damit ist das Gültigkeitsproblem auf das Leerheitsproblem reduziert, denn es gilt L_{ω}(¬φ) = L_{ω}(A) für einen Büchi-Automaten A, der effektiv konstruiert werden kann. Das Leerheitsproblem für Büchi-Automaten ist mit Satz 4.10 entscheidbar.

Korollar 5.6 Gültigkeit in S1S ist entscheidbar.^{3} □

Der Beweis von Satz 5.4 läßt sich leicht so modifizieren, daß er auch für reguläre Sprachen endlicher Wörter funktioniert.

Korollar 5.7 Für eine Sprache L ⊆ Σ^{∗} sind äquivalent:

1. L ist regulär

2. L\{ε} = L(φ) für eine geschlossene S1S-Formel φ. Beachte: Die Interpretation (L(φ))für S1S-Formeln muß für endliche Wörter angepaßt werden.

□

Wie in Abschnitt 1.3 eingeführt, faßt man hier endliche Wörter als endliche, total geordnete Interpretationen auf. Im Beweis von “1 ⇒ 2” muß als Anpassung an die nun endlichen Wörter im wesentlichen die Akzeptanzbedingung geändert werden:

⋁_{q_{i}∈F} ∀x ∃y (x < y ∧ Y_{i}(y))

2bei offenen Formeln werden freie Variablen als Prädikatensymbole aufgefaßt

3Entscheidbarkeitsaussagen waren der Grund, warum Büchi die Büchi-Automaten entwickelte

wird ersetzt durch

⋁_{q_{i}∈F} ∀x (\underbrace{Max(x)}_{{Abkürzung \atop fürs(x)=x}}→ Y_{i}(x))

Im Beweis von “2 ⇒ 1” wendet man die Abschlußeigenschaften regulärer Sprachen (statt der für ω-reguläre Sprachen) an. Beim Induktionsanfang muß man die spezielle Semantik von s beachten und mit der Akzeptanzbedingung für endliche Wörter arbeiten.

Korollar 5.8 Für eine S1S-Formel φ ist es entscheidbar, ob sie in allen \underline{endlichen} S1S-Interpretationen gilt.

□

Büchi hat auch die sogenannte schwache Logik WS1S^{4} betrachtet, bei der die Quantoren ∃X und ∀X zweiter Stufe nur über endliche Teilmengen von ω quantifizieren. Man kann WS1S in S1S ausdrücken, denn der Quantor “∃X φ(X)” in WS1S wird in S1S zu “∃X (∃y ∀X (X(x) → x < y) ∧ φ(X))”. Damit ist gezeigt, daß Gültigkeit in WS1S entscheidbar ist. Umgekehrt kann man zeigen, daß WS1S genauso ausdrucksstark ist wie S1S: zu jeder ω-regulären Sprache L gibt es eine WS1S-Formel φ mit L_{ω}(φ) = L. Wir verwenden die Entscheidbarkeit von WS1S, um die Entscheidbarkeit der Presburger Arithmetik zu zeigen.

Definition 5.9 (Presburger Arithmetik) Man betrachtet hier Formeln der Logik erster Stufe, die als nicht-logische Symbole eine Konstante “\underline{0}” und ein zweistelliges Funktionssymbol “+” enthalten dürfen. Als Interpretation verwendet man die natürlichen Zahlen, wobei “\underline{0}” als 0 und “+” als Addition interpretiert wird.

□

Satz 5.10 Die Presburger Arithmetik ist entscheidbar, das heißt für eine Formel der Logik erster Stufe, die als nicht-logische Symbole nur “\underline{0}” und “+” enthält, ist es entscheidbar, ob sie in den natürlichen Zahlen gilt.

Beweis Man stellt die natürlichen Zahlen in Binärcodierung dar und interpretiert die 0-1-Folgen als (endliche) Teilmengen von ω. Ist n = 2^{i_{1}} + 2^{i_{2}} + ...+ 2^{i_{k}} mit i_{1} < i_{2} < ... < i_{k}, so wird n durch die Menge {i_{1},i_{2},...,i_{k}} ⊆ ω codiert. Beispiel: 13 in Binärdarstellung ist 1101, also wird 13 durch {0,2,3} codiert. 20 in Binärdarstellung ist 10100, also wird 20 codiert durch {2,4}.

4W steht für engl. weak

Wir zeigen nun, wie man die Addition natürlicher Zahlen in WS1S ausdrücken kann. Es gibt eine WS1S Formel φ_{+} (X,Y,Z) mit der folgenden Eigenschaft: Ist K ⊆ ω Codierung von k, N Codierung von n und M Codierung von m, so gilt

φ_{+} (K,N,M) gdw k + n = m.

Beispiel: 13+20=33, bzw. ausführlich

10100 ˆ=  {2,4} =: X
01101 ˆ= {0,2,3} =: Y
Übertrag 111000 ˆ= {3,4,5} =: R
100001 ˆ=  {0,5} =: Z

Wir benötigen eine Hilfsvariable R zweiter Stufe für den Übertrag:

• x gehört zu Z ( ˆ= 1 an Position x in der Summe) gdw eine oder alle drei Mengen X, Y, R das x enthalten

• x + 1 gehört zu R ( ˆ= 1 an Position x + 1 im Übertrag) gdw x gehört zu mindestens zwei der Mengen X, Y, Z

Nun können wir φ_{+} angeben:

φ_{+} (X,Y,Z) := ∃R (¬R(\underline{0})∧
∀x (R(s(x)) ↔ ((X(x) ∧ Y (x))∨
(X(x) ∧ R(x))∨
(Y (x) ∧ R(x))))
∀x (Z(x) ↔  ((X(x) ∧ Y (x) ∧ R(x))∨
(X(x) ∧ ¬Y (x) ∧ ¬R(x))∨
(¬X(x) ∧ Y (x) ∧ ¬R(x))∨
(¬X(x) ∧ ¬Y (x) ∧ R(x)))))

Man kann damit beliebige Presburger Formeln in WS1S-Formeln übersetzen. Beispiel: ∀x (x + \underline{0} = x) wird übersetzt in ∃Z (∀x (¬Z(x)) ∧ ∀X φ_{+} (X,Z,X)).

□

Wir haben WS1S anstelle von S1S verwendet, da natürliche Zahlen \underline{endlichen} Teilmengen von ω entsprechen. Bei endlichen Wörtern konnte die Klasse von Sprachen, welche durch Formeln der Logik erster Stufe akzeptiert werden, mit Satz 3.9 folgendermaßen charakterisiert werden: Für L ⊆ Σ^{∗} sind äquivalent:

1. L ist sternfrei

2. L\{ε} = L(φ) für eine geschlossene Formel der Logik erster Stufe über den nichtlogischen Symbolen <, Q_{a} (a ∈ Σ).

Bei ω-Sprachen gibt es einen entsprechenden Zusammenhang.

Definition 5.11 Eine ω-Sprache L ⊆ Σ^{ω} heißt \underline{sternfrei} gdw L = ⋃ _{i=1}^{n} U_{i}V_{i}^{ω} für sternfreie Sprachen U_{i}, V_{i} ⊆ Σ^{∗}.

□

Satz 5.12 Für eine ω-Sprache L ⊆ Σ^{ω} sind äquivalent:

1. L ist sternfrei

2. L = L_{ω}(φ) für eine geschlossene S1S-Formel φ, welche keine Quantifizierung über einstellige Prädikate enthält.

□

Wir erwähnen dieses und die folgenden Resultate ohne Beweis. Die Beweise oder Hinweise auf Literatur, in der die Beweise geführt werden, finden sich in

W. Thomas: Automata on Infinite Objects, J. van Leeuwen (Hrsg.) Handbook of Theoretical Computer Science, Vol. B, Elsevier 1990.

Man kann sternfreie ω-Sprachen mit Hilfe endlicher Monoide charakterisieren.

Definition 5.13 Es sei L ⊆ Σ^{ω} eine ω-Sprache. Die Kongruenzrelation ≈_{L} auf Σ^{∗} ist definiert durch

u ≈_{L} v gdw ∀x,y,z ∈ Σ^{∗} :
(xuyz^{ω} ∈ L gdw xvyz^{ω} ∈ L) ∧
(x(yuz)^{ω} ∈ L gdw x(yvz)^{ω} ∈ L)
□

Für ω-reguläre Sprachen L hat ≈_{L} stets endlichen Index. Im Gegensatz zum Fall endlicher Wörter gilt die Umkehrung aber nicht, das heißt es gibt nicht-reguläre ω-Sprachen L, für die ≈_{L} auch endlichen Index hat. Für eine Charakterisierung der ω-regulären Sprachen benötigt man daher eine zusätzliche Bedingung.

Definition 5.14 Es sei L ⊆ Σ^{ω} und ∼ eine (beliebige) Kongruenzrelation auf Σ^{∗}. Die Relation ∼ \underline{saturiert} L genau dann, wenn es endlich viele ∼-Klassen U_{1}, U_{2}, ..., U_{m} und V_{1}, V_{2}, ..., V_{m} gibt mit

L = ⋃_{i=1}^{m} U_{i}V_{i}^{ω}.

□

Satz 5.15 Für eine ω-Sprache L ⊆ Σ^{ω} sind äquivalent

1. L ist ω-regulär

2. ≈_{L} hat endlichen Index und saturiert L

□

Die sternfreien ω-Sprachen entsprechen nun wieder den aperiodischen Monoiden.

Satz 5.16 Für eine \underline{ω-reguläre} Sprache L sind äquivalent

1. L ist sternfrei

2. Σ^{∗}/ ≈_{L} ist aperiodischer endlicher Monoid

□

Satz 5.12 und Satz 5.16 ermöglichen es wieder, für eine gegebene ω-reguläre Sprache zu überprüfen, ob sie durch eine Formel der Logik erster Stufe akzeptiert wird.

Beispiel 5.17

Σ = {a,b,c}, L = {α ∈ Σ^{ω} |  zwischen zwei a′s befindet sich

eine gerade Anzahl b′s und c′s }

Wir zeigen: Σ^{∗}/ ≈_{L} ist nicht aperiodisch, das heißt L kann nicht von einer Formel der Logik erster Stufe akzeptiert werden. Wir wissen: die M-Varietät der aperiodischen Monoide ist schließlich definiert durch (x^{n+1} = x^{n})_{n≥1} . x := [b]_{≈_{L}} ∈ Σ^{∗}/ ≈_{L} erfüllt x^{n+1} = x^{n} für kein n, denn ohne Einschränkung sei n gerade (der Fall n ungerade läuft analog) und n + 1 somit ungerade. Aus x^{n+1} = x^{n} würde folgen b^{n} ≈_{L} b^{n+1} . Es ist aber ab^{n}aa^{ω} ∈ L (da n gerade ist) und ab^{n+1} aa^{ω} ∉ L (da n + 1 ungerade ist). Es folgt b^{n} ≉_{L} b^{n+1} . Widerspruch

□

Wir betrachten nun eine weitere Logik, für die man Entscheidbarkeit mit Hilfe von Büchi-Automaten zeigen kann. Diese Logik soll das \underline{Ein-/Ausgabeverhalten eines}\underline{deterministischen Programms p} beschreiben.

• p führt Konfigurationen in Folgekonfigurationen über. Deterministisch heißt, daß es zu einer Konfiguration k höchstens eine Folgekonfiguration gibt.

• Nicht-Terminierung von p entspricht der Tatsache, daß es keine Folgekonfiguration gibt.

• p kann mehrmals hintereinander ausgeführt werden und es kann iteriert werden.

Wir gehen davon aus, daß endlich viele atomare Eigenschaften A_{1}, ..., A_{n} von Konfigurationen gegeben sind. Man will eine Logik, in der man Aussagen wie die folgenden beschreiben kann:

a1) Gilt A_{1} in k, so gilt A_{2} in der Folgekonfiguration.

a2) Gilt A_{1} in k, so existiert keine Folgekonfiguration, das heißt p terminiert nicht.

a3) Beginnend mit der Konfiguration k, in der A_{1} gilt, kann man durch endlich oftes Anwenden von p eine Konfiguration erreichen, in der A_{2} gilt.

Definition 5.18 Formeln der Logik \underline{1DPDL} (Propositionale Dynamische Logik eines deterministischen Programms) sind wie folgt aufgebaut:

1.

Programmformeln

• p und ε sind Programmformeln.

• Sind π_{1} und π_{2} Programmformeln, so auch π_{1};π_{2} (Hintereinanderausführung), π_{1}∪ π_{2} (nicht-deterministische Alternative) und π_{1}^{∗} (Iteration).

2.

Konfigurationsformeln

• A_{1}, ..., A_{n} sind Konfigurationsformeln.

• Sind φ_{1}, φ_{2} Konfigurationsformeln und ist π Programmformel, so sind φ_{1}∧ φ_{2}, φ_{1}∨ φ_{2}, ¬φ_{1}, < π > φ_{1} und [π]φ_{1} Konfigurationsformeln.

\underline{Programmformeln} beschreiben Programme, die man aus den atomaren Programmen p aufbauen kann. Zum Beispiel ist p∪(p;p) ein nicht-deterministisches Programm, bei dem man p einmal oder zweimal ausführt.

< π > φ_{1} : es gibt eine π-Folgekonfiguration, in der φ_{1} gilt.
[π]φ_{1} :  in allen π-Folgekonfigurationen gilt φ_{1}

(beachte: es kann mehrere Folgekonfigurationen geben).

□

Beispiel 5.19 Die Aussagen a1, a2 und a3 können wie folgt beschrieben werden:

a1) A_{1} → < p > A_{2}

a2) A_{1} → [p](A_{1}∧ ¬A_{1})

a3) A_{1} → < p^{∗} > A_{2}

□

Die Semantik von 1DPDL wird durch die folgende Definition festgelegt.

Definition 5.20 Eine Interpretation I besteht aus einer nicht-leeren Menge Δ^{I} von Konfigurationen und einer Interpretationsfunktion ·^{I}, die

1. dem atomaren Programm p eine funktionale Relation p^{I} ⊆ Δ^{I} × Δ^{I} zuordnet. Funktional heißt: ∀k,k_{1},k_{2} : (k,k_{1}) ∈ p^{I} ∧ (k,k_{2}) ∈ p^{I} → k_{1} = k_{2}

2. jeder atomaren Eigenschaft A_{i} eine Menge A_{i}^{I} ⊆ Δ^{I} zuordnet, das heißt die Menge der Konfigurationen, in denen A_{i} gilt

Die Interpretationsfunktion kann auf Programm- und Konfigurationsformeln erweitert werden. Dies geschieht durch Induktion über den Formelaufbau. Die Interpretation der atomaren Formeln p, A_{1}, ..., A_{n} ist bereits definiert.

5 Unendliche Wörter und logische Formeln 77

Programmformeln:

• ε^{I} := {(k,k) | k ∈ Δ^{I}}

• (π_{1};π_{2})^{I} := π_{1}^{I}∘ π_{2}^{I} = {(k_{1},k_{2}) | ∃k: (k_{1},k) ∈ π_{1}^{I}∧ (k,k_{2}) ∈ π_{2}^{I}}

• (π_{1}∪ π_{2})^{I} := π_{1}^{I}∪ π_{2}^{I}

• (π_{1}^{∗})^{I} := ⋃ _{i≥0} (π_{1}^{I})^{i}, wobei (π_{1}^{I})^{0} = ε^{I} und (π_{1}^{I})^{i+1} = (π_{1}^{I})^{i}∘ π_{1}^{I} Jeder Programmformel π wird also eine Relation π^{I} ⊆ Δ^{I}×Δ^{I} zugeordnet. \underline{Konfigurationsformeln:}

• (φ_{1}∧ φ_{2})^{I} := φ_{1}^{I}∩ φ_{2}^{I}

• (φ_{1}∨ φ_{2})^{I} := φ_{1}^{I}∪ φ_{2}^{I}

• (¬φ_{1})^{I} := Δ^{I}\φ_{1}^{I}

• (< π > φ_{1})^{I} := {k ∈ Δ^{I} | ∃k′∈ Δ^{I} : (k,k′) ∈ π^{I} ∧ k′∈ φ_{1}^{I}}

• ([π]φ_{1})^{I} := {k ∈ Δ^{I} | ∀k′∈ Δ^{I} : (k,k′) ∈ π^{I} → k′∈ φ_{1}^{I}}

□

Beispiel 5.21

I : k_{1} ∈ A_{1}^{I} −→^{p^{I}} k_{2} ∈ (¬A_{1})^{I} −→^{p^{I}} k_{3} ∈ A_{1}^{I} −→^{p^{I}} k_{4} ∈ (¬A_{1})^{I} −→^{p^{I}} ...
φ : A_{1}∧ [p^{∗}]((A_{1} →< p > ¬A_{1}) ∧ (¬A_{1} →< p > A_{1}))
φ^{I} : {k_{1}, k_{3}, ...}
□

Definition 5.22

1. Die Konfigurationsformel φ heißt \underline{erfüllbar}, falls es eine Interpretation I gibt und ein k ∈ Δ^{I} mit k ∈ φ^{I}. Das I heißt dann \underline{Modell} von φ.

2. Die Konfigurationsformel φ heißt \underline{gültig}, falls für alle Interpretationen I gilt, daß

φ^{I} = \underbrace{Δ^{I}}_{{Menge aller \atop Konfigurationsformeln}}.

3. φ und ψ sind \underline{äquivalent} genau dann, wenn φ ↔ ψ gültig ist, das heißt für alle Inter-

pretationen I gilt φ^{I} = ψ^{I}.

□

Offenbar ist φ gültig genau dann, wenn ¬φ unerfüllbar ist. Um Erfüllbarkeit zu entscheiden, ordnen wir jeder Konfigurationsformel φ einen Büchi-Automaten A_{φ} zu, für den gilt: L_{ω}(A_{φ}) ≠ ∅ gdw φ ist erfüllbar.

Bei S1S wurde das Alphabet bestimmt durch die vorhandenen einstelligen Prädikatsymbole ( ˆ= atomaren Eigenschaften). Für 1DPDL ist es günstiger, alle “Unterformeln” der gegebenen Formel zu betrachten. Zunächst stellen wir Programmformeln als reguläre Sprachen endlicher Wörter über dem Alphabet {p} dar:

L(p) = {p}
L(ε) = {ε}
L(π_{1};π_{2}) = L(π_{1}) · L(π_{2})
L(π_{1}∪ π_{2}) = L(π_{1}) ∪ L(π_{2})
L(π_{1}^{∗}) = L(π_{1})^{∗}

Es gilt für jede Interpretation I:

(k,k′) ∈ π^{I} gdw ∃m ≥ 0 ∃k_{0},...,k_{m}∈ Δ^{I} :
p^{m}∈ L(π) ∧
k_{0} = k ∧
k_{m}= k′∧
(k_{i},k_{i+1} ) ∈ p^{I} für 0 ≤ i < m

Es sei B = (Q,{p}, . ,Δ,F) ein endlicher Automat, bei dem die Anfangszustandsmenge noch nicht festgelegt ist. Für jedes q ∈ Q bezeichne B_{q} den Automaten, der uas B entsteht, wenn man q zum Anfangszustand macht.

Lemma 5.23 Es sei φ_{0} eine Konfigurationsformel, die die Programmformeln π_{1},...,π_{r} enthält. Dann gibt es einen endlichen Automaten B = (Q,{p}, . ,Δ,F), dessen Göße linear zu der Größe von φ_{0} ist, so daß gilt: Für alle i, 1 ≤ i ≤ r, gibt es q_{i} ∈ Q mit L(π_{i}) = L(B_{q_{i}}).

□

Die Programmformel π_{i} wird damit eindeutig durch den Zustand q_{i} beschrieben. Wir werden daher im folgenden davon ausgehen, daß in φ_{0} anstelle der π_{i} die Zustände q_{i} von B stehen.

Beispiel 5.24 φ_{0} = [p^{∗}] < p > A_{1}, das heißt π_{1} = p^{∗} und π_{2} = p.

B:

[figure: q_{1}; q_{2}; q_{3}; ⟲; p; p]

L(p^{∗}) = L(B_{q_{1}}), L(p) = L(B_{q_{2}}) φ_{0} kann daher als φ̂_{0} = [q_{1}] < q_{2} > A_{1} geschrieben werden.

□

Es sei φ_{0} eine Konfigurationsformel, B der zugehörige Automat und φ̂_{0} sei die Formel, die aus φ_{0} entsteht, indem man jede Programmformel durch den entsprechenden Zustand ersetzt. Wir gehen ohne Einschränkung davon aus, daß φ_{0} und φ̂_{0} in \underline{Negationsnormalform} (NNF) gegeben sind, das heißt Negation kommt nur unmittelbar vor atomaren Eigenschaften vor. Man schiebt dazu mit Hilfe von äquivalenzerhaltenden Regeln die Negationen nach innen:

¬¬φ → φ
¬(φ ∨ ψ) → ¬φ ∧ ¬ψ
¬(φ ∧ ψ) → ¬φ ∨ ¬ψ
¬ < π > φ → [π]¬φ
¬[π]φ → < π > ¬φ

Definition 5.25 Der \underline{Fischer-Ladner-Abschluß} von φ_{0} ist die kleinste Menge F L(φ_{0}) von Konfigurationsformeln, für die gilt:

• φ̂_{0} ∈ F L(φ_{0})

• φ_{1}∧ φ_{2} ∈ F L(φ_{0}) → φ_{1},φ_{2} ∈ F L(φ_{0})

• φ_{1}∨ φ_{2} ∈ F L(φ_{0}) → φ_{1},φ_{2} ∈ F L(φ_{0})

• ¬A_{i} ∈ F L(φ_{0}) ↔ A_{i} ∈ F L(φ_{0})

• [q]φ ∈ F L(φ_{0}) → φ ∈ F L(φ_{0}) und [q′]φ ∈ F L(φ_{0}) für alle q′∈ Q mit (q,p,q′) ∈ Δ

• < q > φ ∈ F L(φ_{0}) → φ ∈ F L(φ_{0}) und < q′> φ ∈ F L(φ_{0}) für alle q′∈ Q mit (q,p,q′) ∈ Δ

□

Beachte: |F L(φ_{0})| ist linear zu der Größe von φ_{0}.

Beispiel 5.24 (Fortsetzung) φ̂_{0} = [q_{1}] < q_{2} > A_{1} ist in NNF. F L(φ_{0}) = {φ̂_{0}, < q_{2} > A_{1}, ¬A_{1}, A_{1}, < q_{3} > A_{1}}

□

Es sei nun φ_{0} Konfigurationsformel in NNF und I ein Modell von φ_{0} mit k_{0} ∈ φ_{0}^{I}. Beginnend mit k_{0} wenden wir das Programm p iteriert an. Es können zwei Fälle eintreten:

1. p terminiert stets, das heißt es gibt eine unendliche Folge k_{0},k_{1},k_{2},...∈ Δ^{I} mit (k_{i},k_{i+1} ) ∈ p^{I} für alle i ≥ 0

2. p terminiert irgendwann nicht, das heißt es gibt eine endliche Folge k_{0},...,k_{m}∈ Δ^{I} mit (k_{i},k_{i+1} )∈ p^{I} für 0 ≤ i < m und (k_{m},k)∉ p^{I} für alle k ∈ Δ^{I}

Für k ∈ Δ^{I} sei S(k) := {φ ∈ F L(φ_{0}) | k ∈ φ^{I}}. Beachte: S(k) ≠ ∅, da für atomare Eigenschaften A_{i} in φ_{0} gilt: A_{i} ∈ S(k) oder ¬A_{i} ∈ S(k). Im ersten Fall erhalten wir ein unendliches Wort α(k_{0}) = S(k_{0})S(k_{1})S(k_{2})... über dem Alphabet Σ := 2^{F L(φ_{0})}. Im zweiten Fall verlängern wir das endliche Wort S(k_{0})...S(k_{m}) zu einem unendlichen Wort α(k_{0}) ∈ Σ^{ω} durch Anfügen von ∅∅∅.... Man erhält so ein Wort aus Σ^{ω}, das Eigenschaften hat, die sehr stark von der Struktur von φ_{0} abhängen.

Definition 5.26 Das Wort α = α_{0}α_{1}α_{2}... ∈ Σ^{ω} ist ein \underline{Hintikka-Wort} für φ_{0}, falls gilt:

1. φ̂_{0} ∈ α_{0}

und für alle m ≥ 0

2. α_{m}= ∅ oder A_{i} ∈ α_{m} gdw ¬A_{i} ∉ α_{m} für alle atomaren Eigenschaften A_{i} ∈ F L(φ_{0})

3. φ ∧ ψ ∈ α_{m} gdw φ ∈ α_{m} und ψ ∈ α_{m}

4. φ ∨ ψ ∈ α_{m} gdw φ ∈ α_{m} oder ψ ∈ α_{m}

5. [q]φ ∈ α_{m}, dann gelten

5.1 falls ε ∈ L(B_{q}), so φ ∈ α_{m}

5.2 α_{m+1} = ∅ oder für alle q′mit (q,p,q′) ∈ Δ gilt [q′]φ ∈ α_{m+1}

6. < q > φ ∈ α_{m}, dann gibt es ein r ≥ 0 mit p^{r} ∈ L(B_{q}) und φ ∈ α_{m+r}

7. Ist α_{m}= ∅, so auch α_{m+1} = ∅

□

Satz 5.27 φ_{0} ist erfüllbar genau dann, wenn es ein Hitikka-Wort für φ_{0} gibt.

Beweisskizze “⇒”

Es sei I ein Modell für φ_{0} und k_{0} so, daß k_{0} ∈ φ_{0}^{I}. Dann ist α(k_{0}) ein Hintikka-Wort für φ_{0}. Beweis: siehe Übungsaufgaben.

“⇐”

Es sei α = α_{0}α_{1}α_{2}... ein Hitikka-Wort fïr φ_{0}. Wir definieren ein Modell I wie folgt:

Δ^{I} = {k_{0},k_{1},k_{2},...}
p^{I} = {(k_{i},k_{i+1} ) | α_{i+1} ≠ ∅}
A_{j}^{I} = {k_{i} | A_{j} ∈ α_{i}}

Man zeigt durch Induktion über den Formelaufbau:

Für allei ≥ 0 und alleφ ∈ F L(φ_{0}) gilt : φ ∈ α_{i} → k_{i} ∈ φ^{I}

Wegen φ̂_{0} ∈ α_{0} folgt daraus k_{0} ∈ φ̂_{0}^{I}, das heißt k_{0} ∈ φ_{0}^{I}.

□

Gesucht ist nun ein Büchi-Automat, der genau die Hintikka-Wörter für φ_{0} akzeptiert. Der \underline{lokale Automat} A_{L}(φ_{0}) akzeptiert eine etwas größere Menge von Wörtern. Hier ist die globale Bedingung 6. in Definition 5.26 ersetzt durch die lokale Bedingung

6’. < q > φ ∈ α_{m}, dann gilt:

6’.1 ε ∈ L(B_{q}) und φ ∈ α_{m}

oder 6’.2 es gibt ein q′∈ Q mit (q,p,q′) ∈ Δ und < q′> φ ∈ α_{m+1}

Definition 5.28 A_{L}(φ_{0}) := (Q_{L}, Σ, I_{L}, Δ_{L}, F_{L}) mit

• Q_{L} = {α_{i} ∈ 2^{F L(φ_{0})} | α_{i} erfüllt 2., 3. und 4. von Definition 5.26 }

• I_{L} = {α_{i} ∈ Q_{L} | φ̂_{0} ∈ α_{i}}

• Δ_{L} = {(α_{m},σ,α_{m+1}) | α_{m}= σ undα_{i}, α_{i+1} erfüllen 5., 6′. und 7.}

• F_{L} = Q_{L}

□

Offenbar akzeptiert A_{L}(φ_{0}) genau die Wörter α_{0}α_{1}α_{2}... ∈ Σ^{ω}, welche 1. bis 5. und 7. von Definition 5.26 sowie 6’. erfüllen.

Beispiel 5.29 Aus α ∈ L_{ω}(A_{L}(φ_{0})) folgt noch nicht, daß α ein Hintikka-Wort für φ_{0} ist: φ_{0} =< p^{∗} > (A_{1}∧ ¬A_{1}) B:

[figure: ⟲; p; q_{1}]

φ̂_{0} =< q_{1} > (A_{1}∧ ¬A_{1}) Es gilt für α_{0} = {φ̂_{0},A_{1}}, daß α_{0}^{ω} ∈ L_{ω}(A_{L}(φ_{0})). Das Wort α_{0}^{ω} erfüllt zwar 6’., nicht aber 6. Das Problem ist, daß bei 6’. stets die Alternative 6’.2 gewählt wird. Damit 6. erfült ist, muß nach endlicher Zeit einmal 6’.1 gewählt werden.

□

Definition 5.30 A_{H}(φ_{0}) := (Q_{H}, Σ, I_{H}, Δ_{H}, F_{H}) mit

• Q_{H} = Q_{L}× 2^{F L_{<>} (φ_{0})}, wobei F L_{<>} (φ_{0}) := {< q > φ | < q > φ ∈ F L(φ_{0})}

• Σ = 2^{F L(φ_{0})}

• I_{H} = I_{L}× {∅}

• F_{H} = Q_{L}× {∅}

• ((α_{m},s),σ,(α_{m+1},t)) ∈ Δ_{H} gdw

entweder ∗ s = ∅ ∗ (α_{m},σ,α_{m+1}) ∈ Δ_{L}

∗ t enthält für jedes < q > φ ∈ σ mit ( ε ∉ L(B_{q}) oder φ ∉ σ ein ¡q’¿φ ∈ α_{m+1}
mit (q,p,q′) ∈ Δ
oder ∗ s ≠ ∅
∗ (α_{m},σ,α_{m+1}) ∈ Δ_{L}
∗ t enthält für jedes < q > φ ∈ s mit ( ε ∉ L(B_{q}) oder φ ∉ σ ein ¡q’¿φ ∈ α_{m+1}
mit (q,p,q′) ∈ Δ

Beachte: Nach Definition von Δ_{L} enthält α_{m+1} stets ein geeignetes < q′> φ, da 6’ durch Δ_{L} erfüllt ist.

□

Satz 5.31 A_{H}(φ_{0}) akzeptiert genau die Hintikka-Wörter für φ_{0}.

□

Satz 5.32 Erfüllbarkeit in 1DPDL ist in exponentieller Zeit entscheidbar.

Beweis Der Automat A_{H}(φ_{0}) ist exponentiell in der Größe von φ_{0} (Teilmengen von F L(φ_{0})). Das Leerheitsproblem für Büchi-Automaten ist in linearer Zeit entscheidbar.

□

Beachte: Anders als bei S1S wurde hier der sehr aufwendige (das heißt schlimmer als exponentielle) Abschluß unter Komplement nicht verwendet. Häufig möchte man nicht nur ein atomares Programm zur Verfügung haben, sondern endlich viele atomare Programme p_{1}, p_{2}, ..., p_{n}. Dann reicht die Betrachtung von Wörtern nicht mehr aus. Modelle liefern dann \underline{Hintikka-Bäume}.

Automaten auf endlichen Bäumen

Wir betrachten Bäume mit beschrifteten Knoten, bei denen die Anzahl der Nachfolgeknoten durch die Stelligkeit der Knotenbeschriftung bestimmt ist.

Beispiel 6.1 Σ = {+, ·, −, x, y} ist die Menge der Knotenbeschriftungen, wobei + und · zweistellig, − einstellig und x und y nullstellig seien. Dann ist

[figure: +; ε; 0; 1; ·; −; x; y; x; 00; 01; 10]

ein \underline{endlicher Σ-} \underline{beschrifteter Baum}. Man kann Knoten dieses Baumes eindeutig durch Wörter aus {0, 1}^{∗} ansprechen. t entspricht einer partiellen Funktion t : {0, 1}^{∗} → Σ mit dem Definitionsbereich dom(t) = {ε, 0, 1, 00, 01, 10}. Zum Beispiel ist t(0) = ·.

□

Definition 6.2 Es sei Σ ein Alphabet und ν: Σ → ω eine Funktion, die jedem a ∈ Σ eine Stelligkeit ν(a) zuordnet (\underline{Alphabet mit Stelligkeitsfunktion}). Für n ∈ ω sei Σ_{n}:= \{a ∈ Σ | ν(a) = n\}. Ein \underline{Σ-Baum} ist eine partielle Funktion t : ω^{∗} → Σ, deren Definitionsbereich dom(t) erfüllt:

1. ε ∈ dom(t), das heißt jeder Baum ist nicht-leer

2. Für alle u ∈ ω^{∗}, i ∈ ω gilt:

ui ∈ dom(t) gdw u ∈ dom(t) und i < ν(t(u))

[figure: a; u; u0; u(n − 1); ν(a) = n]

Ein \underline{Blatt} u von t ist ein Knoten u ∈ dom(t) mit ν(t(u)) = 0, das heißt u hat keine Nachfolgerknoten. Der Baum t ist \underline{endlich}, falls dom(t) endlich ist. Mit T_{Σ} bezeichnet man die Menge aller endlichen Σ-Bäume. Es sei ≺ die \underline{Präfixrelation}auf ω^{∗}, das heißt u ≺ v gdw ∃u′∈ ω^{+} : uu′= v.

□

Wegen 2. von Definition 6.2 gilt für jeden Baum t, daß dom(t) unter Präfixbildung abgeschlossen ist, das heißt ist v ∈ dom(t) und u ≺ v, so ist u ∈ dom(t).

Definition 6.3

1. Ein \underline{Pfad} durch t ist eine maximale, bezüglich ≺ total geordnete Teilmenge von dom(t).

2. Der Unterbaum von t an der Stelle u ∈ dom(t) ist der Baum t_{u} mit

• dom(t_{u}) = {v | uv ∈ dom(t)}

• t_{u}(v) = t(uv)

□

Beispiel 6.1 (Fortsetzung)

[figure: +; ε; 0; 1; ·; −; x; y; x; 00; 01; 10]

In diesem Baum existieren die Pfade {ε, 0, 00}, {ε, 0, 01} und {ε, 1, 10}. {ε, 0, 00, 01} ist kein Pfad, denn er wäre nicht total geordnet; {ε, 00} wäre nicht maximal.

[figure: t_{0} :; t_{1} :; ε; ε; ·; −; x; y; x; 0; 1; 0]

□

Ein Wort w ∈ Σ^{∗}für ein endliches Alphabet Σ kann als endlicher Baum über Σ̂ = Σ ∪ {x} angesehen werden, wobei ν(a) = 1 für a ∈ Σ und ν(x) = 0 definiert wird. Mit Σ = {a, b} entspricht abb dann dem Baum

[figure: x; a; b; b]

Wir betrachten nun den Automaten

[figure: ⟲; q_{0}; q_{1}; b; a]

Ein Pfad im Automaten mit Beschriftung abb kann in dem Baum durch eine Zusatzbeschriftung der Knoten mit Zuständen des Automaten beschrieben werden:

[figure: x; a; b; b; q_{0}; q_{1}; q_{1}; q_{1}]
□

Definition 6.4 Ein \underline{BW-Baumautomat} (Blatt zur Wurzel) A := (Q, Σ, I, Δ, F) besteht aus

• einer endlichen Zustandsmenge Q

• einem endlichen Alphabet Σ mit Stelligkeitsfunktion (das heißt Σ = Σ_{0}∪Σ_{1}∪Σ_{2}∪...)

• einer Anfangszuweisung I : Σ_{0} → 2^{Q}

• einer Übergangszuweisung Δ, die für n > 0 jedem a ∈ Σ_{n} eine Funktion Δ_{a}: Q^{n}→ 2^{Q} zuweist

• einer Endzustandsmenge F

Ein \underline{Lauf} dieses Baumautomaten auf einem Baum t ∈ T_{Σ} ist eine Abbildung l : dom(t) → Q mit

• l(u) ∈ Δ_{a}(l(u0),...,l(u(n − 1))) für t(u) = a ∈ Σ_{n}.

Der Lauf l ist \underline{erfolgreich}, falls

• l(u) ∈ I(t(u)) für alle Blätter u

• l(ε) ∈ F

Die von A \underline{akzeptierte} Baumsprache ist

L(A) := {t ∈ T_{Σ} | es gibt erfolgreichen Lauf von A auf t}

A heißt \underline{deterministisch}, wenn für alle a ∈ Σ_{0} gilt: |I(a)| = 1 und für alle n > 0 und a ∈ Σ_{n},q_{1},...,q_{n} ∈ Q gilt |Δ_{a}(q_{1},...,q_{n})| = 1. Wir schreiben dann I und Δ_{a} als Funktionen I : Σ_{0} → Q und Δ_{a} : Q^{n} → Q.

□

Beispiel 6.5 Σ = Σ_{0}∪ Σ_{1}∪ Σ_{2} mit Σ_{0} = {x,y}, Σ_{1} = {−} und Σ_{2} = {+,·}. A := (Q, Σ, I, Δ, F) mit

• Q = {0,1,2}

• I(x) = 1, I(y) = 2

• Δ_{−} (q) = 3 − q mod 3 Δ_{+} (q,q′) = q + q′mod 3 Δ_{·}(q,q′) = q · q′mod 3

• F = {1}

[figure: +; 1; 2; 2; ·; −; x; y; x; 1; 2; 1]

ist ein erfolgreicher Lauf. L(A) besteht aus den arithmetischen Ausdrücken, deren Auswertung mit x = 1 und y = 2 mod 3 als Resultat 1 liefert.

□

Wie bei Automaten für Wörter kann man einen nicht-deterministischen BW-Automaten durch \underline{Potenzmengenkonstruktion} in einen äquivalenten deterministischen BW-Automaten überführen.

Satz 6.6 Für eine Baumsprache L ⊆ T_{Σ} sind äquivalent:

1. L wird von einem deterministischen BW-Automaten akzeptiert

2. L wird von einem BW-Automaten akzeptiert

□

Anstatt von den Blättern zur Wurzel kann man auch von der Wurzel zu den Blättern gehen.

Definition 6.7 Ein \underline{WB-Automat} (Wurzel zum Blatt) A = (Q, Σ, I, Δ, F) besteht aus

• einer endlichen Zustandsmenge Q

• einem Alphabet Σ mit Stelligkeitsfunktion

• einer Menge I ⊆ Q von Anfangszuständen

• einer Übergangszuweisung, die jedem a ∈ Σ für n > 0 eine Funktion Δ_{a} : Q → 2^{(Q^{n})} zuweist

[figure: a; q; q_{1}; q_{n}; ...]

• einer Endzuweisung F : Σ_{0} → 2^{Q}

Ein \underline{Lauf} von A auf t ∈ T_{Σ} ist eine Abbildung l : dom(t) → Q mit (l(u0),...,l(u(n−1))) ∈ Δ_{a}(l(u)) für t(u) = a ∈ Σ_{n}. Der Lauf l ist \underline{erfolgreich}, falls l(ε) ∈ I und l(u) ∈ F (t(u)) für alle Blätter u.

L(A) = {t ∈ T_{Σ} | es gibt einen erfolgreichen Lauf von A auf t}.

A heißt \underline{deterministisch}, wenn |I| = 1 und |Δ_{a}(q)| = 1 für alle n > 0, a ∈ Σ_{n}, q ∈ Q.

□

Satz 6.8 Für eine Baumsprache L ⊆ T_{Σ} sind äquivalent:

1. L wird von einem BW-Automaten akzeptiert

2. L wird von einem WB-Automaten akzeptiert Beweis “1 ⇒ 2”

Es sei A = (Q,Σ,I,Δ,F) ein BW-Automat. Wir betrachten den WB-Automaten B = (Q,Σ,F,Δ′,I) mit Δ′_{a} : q ↦ {(q_{1},...,q_{n}) | q ∈ Δ_{a}(q_{1},...,q_{n})}

[figure: a; q; q_{1}; q_{n}; ...; WB; BW]

Man sieht leicht, daß jeder Lauf von A auf t auch ein Lauf von B auf t ist und umgekehrt.

“2 ⇒ 1”  entsprechend
□

Beispiel 6.9 Es sei A der BW-Automat aus Beispiel 6.5. Der zugehörige WB-Automat B = (Q, Σ, I′, Δ′, F′) ist gegeben durch:

• Q = {0,1,2}

• Σ = {+,·,−,x,y}

• I′= {1}

• Δ′_{−} (q) = {q′| Δ_{−} (q′) = q} = {q′| 3 − q′mod 3 = q} Δ′_{+} (q) = {(q′,q′′) | q = q′+ q′′mod 3} Δ′_{·}(q) = {(q′,q′′) | q = q′· q′′mod 3}

• F′(x) = {1}, F′(y) = {2}

[figure: +; 1; 2; 2; ·; −; x; y; x; 1; 2; 1]

ist ein erfolgreicher Lauf, der dem aus Beispiel 6.5 entspricht. Beachte: Obwohl A deterministisch war, ist B nicht-deterministisch: Δ′_{+} (1) = {(q′,q′′) | 1 = q′+ q′′mod 3} = {(0,1),(1,0),(2,2)} □ Beispiel 6.10

Nicht jede von einem nicht-deterministischen WB-Automaten akzeptierte Sprache kann auch von einem deterministischen WB-Automaten akzeptiert werden.

Es sei Σ = \{ \underbrace{x, y}_{0−stellig}, \underbrace{f}_{2−stellig}\} und L = \{ [figure: f; x; y; f; y; x] \}

1. L wird akzeptiert von dem nicht-deterministischen WB-Automaten A = ({q_{0}, q_{1}, q_{x}, q_{y}}, Σ, {q_{0}, q_{1}}, Δ, F) mit

• Δ_{f} (q_{0}) = {(q_{x}, q_{y})} Δ_{f} (q_{1}) = {(q_{y}, q_{x})} Δ_{f} (q_{x}) = Δ_{f} (q_{y}) = ∅

• F (x) = {q_{x}} F (y) = {q_{y}}

[figure: f; q_{0}; q_{x}; q_{y}; x; y]

2. Angenommen B = (Q′, Σ, {i}, Δ′, F′) ist ein deterministischer WB-Automat, der L

akzeptiert. Dann gilt für (q′,q′′) = Δ′_{f}(i) wegen [figure: f; q_{0}; q′; q′′; x; y] ∈ L, daß q′∈ F (x).

Wegen [figure: f; q_{0}; q′; q′′; y; x]∈ L folgt q′′∈ F (x).

Daher akzeptiert B auch [figure: f; q_{0}; q′; q′′; x; x]∉ L.

□

Wir haben gesehen: deterministische und nicht-deterministische BW-Automaten sowie nichtdeterministische WB-Automaten akzeptieren dieselbe Sprachklasse. Deterministische WB-Automaten akzeptieren eine kleinere Klasse von Baumsprachen.

Definition 6.11 Eine Baumsprache L ⊆ T_{Σ} heißt \underline{erkennbar} , wenn sie von einem BW-Automaten akzeptiert wird.

□

Beispiel 6.12 Nicht jede Baumsprache ist erkennbar. Es sei Σ ein Alphabet mit Stelligkeitsfunktion, für das gilt |Σ_{0}| > 0 und |Σ_{2}| > 0. Offenbar folgt daraus, daß T_{Σ} unendlich ist. L:= {f(t,t) | t ∈ T_{Σ}} = {t′∈ T_{Σ} | t′(Σ) = f, t′_{0}= t′_{1}} Dabei ist f(t,t) der Baum, der f als Wurzel hat und nur zwei identische Unterbäume t. Behauptung: L ist nicht erkennbar. Beweis: Angenommen A = (Q,Σ,I,Δ,F) ist ein ohne Einschränkung deterministischer BW-Automat für L. Für jeden Baum t ∈ T_{Σ} sei q_{t} der (eindeutig bestimmte) Zustand aus Q mit der Eigenschaft, daß bei dem Lauf l auf t mit I(t(u)) = l(u) für alle Blätter u q_{t} die Wurzel beschriftet. Da Q endlich und T_{Σ} unendlich ist gibt es t, t′∈ T_{Σ} mit t ≠ t′, aber q_{t} = q_{t′}. Wir betrachten einen Lauf von A auf Δ_{f} (q_{t},q_{t}) ∈ L und Δ_{f} (q_{t},q_{t′}) ∉ L. Wegen q_{t} = q_{t′}ist Δ_{f} (q_{t},q_{t}) = Δ_{f} (q_{t},q_{t′}) ∈ F, das heißt Δ_{f} (q_{t},q_{t′}) wird von A akzeptiert. Widerspruch

□

Bei Wörtern können erkennbare Sprachen durch reguläre Ausdrücke beschrieben werden. Bei erkennbaren Baumsprachen ist eine ähnliche Charakterisierung möglich. Dazu muß man geeignete Operationen auf Baumsprachen einführen. Zur Erinnerung (bei Wörtern galt folgendes):

• ∅ ∈ Reg_{Σ}, a ∈ Reg_{Σ} für alle a ∈ Σ

• L_{1}, L_{2} ∈ Reg_{Σ} ⇒ L_{1}∪ L_{2}, L_{1}· L_{2}, L_{1}^{∗} ∈ Reg_{Σ}

Satz 6.13

1. Die leere Baumsprache ist erkennbar

2. Für a ∈ Σ_{0} ist der Baum mit Wurzel a erkennbar

Beweis

1. Verwende zum Beispiel einen BW-Automaten mit F = ∅

2. Q = {0,1}, I(a) = 1, I(b) = 0 für b ∈ Σ_{0}\{a}, Δ_{f} (q_{1},...,q_{n}) = ∅ für alle f ∈ Σ_{0} mit n > 0, I = {1}

□

Satz 6.14 Die Klasse der erkennbaren Baumsprachen ist abgeschlossen unter Vereinigung, Komplement und Durchschnitt.

Beweis Der Beweis läuft wie bei Wörtern. Man braucht nur Abschluß unter Vereinigung und Komplement zu zeigen, da Durchschnitt sich daraus ergibt.

• Vereinigung: vereinige zwei BW-Automaten mit disjunkten Zustandsmengen zu einem nicht-deterministischen BW-Automaten

• Komplement: verwende einen deterministischen BW-Automaten und mache Endzustände zu nicht-Endzuständen und umgekehrt

□

Anstelle von Wortkonkatenation wird Baumkonkatenation verwendet. Der Baum mit Wurzel f und den Unterbäumen t_{1}, ..., t_{n} wird als f(t_{1},...,t_{n}) geschrieben.

Definition 6.15 Es sei Σ ein Alphabet mit Stelligkeitsfunktion und \overline{x}= (x_{1},...,x_{k}) ein k-Tupel verschiedener Elemente von Σ_{0}.

1. Für t ∈ T_{Σ} und L_{1},...,L_{k} ⊆ T_{Σ} wird t ·\overline{x}(L_{1},...,L_{k}) induktiv definiert:

• t ∈ Σ_{0} :

– t = x_{i} : t ·\overline{x}(L_{1},...,L_{k}) = L_{i}
– t ≠ x_{i} für alle i: t ·\overline{x}(L_{1},...,L_{k}) = \{t\}

• t = f(t_{1},...,t_{n}) für f ∈ Σ_{n}, n > 0: t ·\overline{x}(L_{1},...,L_{k}) = \{f(t′_{1},...,t′_{n}) | t′_{i}∈ t_{i}·\overline{x}(L_{1},...,L_{k})\}

2. für L,L_{1},...,L_{k} ⊆ T_{Σ} ist L ·\overline{x}(L_{1},...,L_{k}) := \{t ·\overline{x}(L_{1},...,L_{k}) | t ∈ L\}

Ein Baum in L ·\overline{x}(L_{1},...,L_{k}) entsteht aus einem Baum t ∈ L dadurch, daß man jedes Blatt mit Beschriftung x_{i} durch ein Element von L_{i} ersetzt. □

Beispiel {f(x,x)} ·^{x}{a,b} = {f(a,a),f(b,b),f(a,b),f(b,a)} Beachte: Verschiedene Vorkommen von x_{i} können durch verschiedene Elemente von L_{i} ersetzt werden. Insgesamt ist {f(x,x)} ·^{x}T_{Σ} = {f(t,t′) | t,t′∈ T_{Σ}} ≠ {f(t,t) | t ∈ T_{Σ}} □

Satz 6.16 Sind L, L_{1}, ..., L_{k} erkennbare Baumsprachen, so ist auch L ·\overline{x}(L_{1},...,L_{k}) erkennbar.

Beweis Es sei A = (Q,Σ,I,Δ,F) ein WB-Automat für L und A_{i} = (Q^{(i)},Σ,I^{(i)},Δ^{(i)},F^{(i)}) sei WB-Automat für L_{i} mit i = 1,...,k. Ohne Einschränkung sind Q, Q^{(1)}, ..., Q^{(k)} paarweise disjunkt. Wir betrachten B = (Q ∪ Q^{(1)}∪ ...∪ Q^{(k)},Σ,I,Δ′,F′) mit

• für a ∈ Σ_{n} mit n > 0:

92 6 Automaten auf endlichen Bäumen

– für q ∈ Q^{(j)} mit j = 1,...,k:
Δ′_{a}(q) := Δ_{a}^{(j)}(q)
– für q ∈ Q:

Δ′_{a}(q) := Δ_{a}(q) ∪ ⋃_{{j mit \atop q∈F (x_{j})}}\{Δ_{a}^{(j)}(i) | i ∈ I^{(j)}\}

• für a ∈ Σ_{0}:

– a ∉ {x_{1},...,x_{k}}:

F′(a) := F (a)∪  F^{(1)}(a) ∪ ...∪ F^{(k)}(a)∪
{q ∈ Q | q ∈ F (x_{j}) für ein j mit 1 ≤ j ≤ k
und F^{(j)}(a) ∩ I^{(j)} ≠ ∅}

– a ∈ {x_{1},...,x_{k}}:

F′(a) := F^{(1)}(a)∪ ...∪ F^{(k)}(a)∪
{q ∈ Q | q ∈ F (x_{j}) für ein j mit 1 ≤ j ≤ k
und F^{(j)}(a) ∩ I^{(j)} ≠ ∅}

Man sieht leicht, daß B ein WB-Automat für L ·\overline{x}(L_{1},...,L_{k}) ist.

□

Wir werden Baumkonkatenation später in zwei Spezialfällen verwenden:

1. Anwenden eines f ∈ Σ_{n} (n > 0) auf Baumsprachen L_{1},...,L_{n}: f(L_{1},...,L_{n}) := {f(x_{1},...,x_{n})} ·^{(x_{1},...,x_{n})}(L_{1},...,L_{n})

2. \overline{x}= x, das heißt \overline{x}ist ein Tupel der Dimension 1: L ·^{x}L′ Der Sternoperator kann auf Baumsprachen wie folgt verallgemeinert werden: Definition 6.17 Es sei L ⊆ T_{Σ} und x ∈ Σ_{0}. Wir definieren

• L^{0,x}:= {x}

• L^{n+1,x} := L^{n,x}∪ L ·^{x}L^{n,x}

• L^{∗,x}:= ⋃ _{n≥0} L^{n,x}

□

Satz 6.18 Ist L eine erkennbare Baumsprache, so auch L^{∗,x}.

6 Automaten auf endlichen Bäumen 93

Beweis Es sei A = (Q,Σ,I,Δ,F) ein WB-Automat für L. Definiere B = (Q ∪ {î},Σ,I′,Δ′,F′) mit î∉ Q

• I′= I ∪ {î}

• für a ∈ Σ_{n}, n > 0

Δ′_{a}(q) = Δ_{a}(q) ∪ \{ \begin{matrix}∅ & q ∉ F (x) \\ ⋃ _{i∈I} Δ_{a}(i) & q ∈ F (x) \end{matrix}

• für a ∈ Σ_{0}:

– a ≠ x: F′(a) = F (a) ∪ {q ∈ Q | q ∈ F (x) ∩ F (a) ∩ I ≠ ∅}

– a = x: F′(x) = F (x) ∪ \underbrace{\{î\}}_{{sorgt dafür, daß \atop x akzeptiert wird}}

□

Definition 6.19 Es sei Σ ein Alphabet mit Stelligkeitsfunktion und Z eine Menge nullstelliger Symbole mit Z ∩ Σ = ∅ und Σ̂ = Σ ∪ Z. \underline{Reg(T_{Σ},Z)}ist die kleinste Klasse von Baumsprachen über Σ̂ mit

1. ∅ ∈ Reg(T_{Σ},Z)

2. {x} ∈ Reg(T_{Σ},Z) für alle x ∈ Σ_{0}∪ Z

3. L_{1},L_{2} ∈ Reg(T_{Σ},Z) ⇒ L_{1}∪ L_{2} ∈ Reg(T_{Σ},Z)

4. L_{1},L_{2} ∈ Reg(T_{Σ},Z), z ∈ Z ⇒ L_{1}·^{z}L_{2} ∈ Reg(T_{Σ},Z)

5. L ∈ Reg(T_{Σ},Z), z ∈ Z ⇒ L^{∗,z} ∈ Reg(T_{Σ},Z)

6. n > 0, f ∈ Σ_{n}, L_{1},...,L_{n} ∈ Reg(T_{Σ},Z) ⇒ f(L_{1},...,L_{n}) ∈ Reg(T_{Σ},Z) Eine Sprache L ⊆ T_{Σ} heißt \underline{regulär}, falls es ein Hilfsalphabet Z von nullstelligen Symbolen gibt mit L ∈ Reg(T_{Σ},Z).

□

Satz 6.20 Für L ⊆ T_{Σ} sind äquivalent:

1. L regulär

2. L ist erkennbar Beweis “1 ⇒ 2” ergibt sich unmittelbar aus den bereits gezeigten Abschlußeigenschaften erkennbarer Baumsprachen.

“2 ⇒ 1”

Es sei A = (Q,Σ,I,Δ,F) ein WB-Automat mit L = L(A). Ohne Einschränkung sei Q = {1,...,k} und Q ∩ Σ = ∅. Wir definieren Z := Q, wobei jedes q ∈ Q Stelligkeit 0 erhält. Es sei A′= (Q,Σ ∪ Z,I,Δ,F′) mit F′(q) = {q} für alle q ∈ Z, F′(q) = F (q) sonst. Für K ⊆ Q, 0 ≤ h ≤ k und i ∈ Q sei L(K,h,i) die Menge aller Bäume t ∈ T_{Σ∪K}, für die es einen Lauf l von A′auf t gibt mit

• l(ε) = i

• l(u) ≤ h für alle u ≠ ε, die nicht Blätter sind

• l(u) ∈ F′(t(u)) für alle Blätter u

L(K,h,i) enthält Bäume, die zusätzlich Blätter haben können, welche mit q ∈ K beschriftet sind. Ein Lauf des Automaten A′muß i an der Wurzel liefern, an den Blättern u mit Zustand aus F′(t(u)) enden (bei t(u) = q ∈ K also mit q) und er darf nur Zwischenzustände ≤ h verwenden. Offenbar gilt L(A) = ⋃ _{i∈I} L(∅,k,i). Es genügt daher zu zeigen, daß alle L(K,h,i) in Reg(T_{Σ},Z) sind. Induktion über h: h = 0 Es darf keine Zwischenzustände geben, das heißt in L(K,0,i) gibt es keine Bäume, welche Knoten u haben, die ≠ ε und keine Blätter sind. Damit ist L(K,h,i) endlich. Man zeigt leicht, daß alle endlichen Teilmengen von T_{Σ∪Z} in Reg(T_{Σ},Z) sind. h > 0 Es gilt

(∗) L(K,h + 1,i) = L(K,h,i) ∪
L(K ∪ {h + 1},h,i) ·^{h+1}
L(K ∪ {h + 1},h,h + 1)^{∗,h+1} ·^{h+1}
L(K,h,h + 1)

Der Beweis von (∗) erfolgt in der Übung. Nach Induktion und wegen der Definition von Reg(T_{Σ},Z) liefert (∗), daß L(K,h + 1,i) ∈ Reg(T_{Σ},Z) ist.

□

Für den Abschluß unter Alphabetsumbenennung seien Σ^{(1)} und Σ^{(2)} Alphabete mit Stelligkeitsfunktion. φ: Σ^{(1)} → Σ^{(2)} für die gilt: φ(Σ_{n}^{(1)}) ⊆ Σ_{n}^{(2)}. Sei t : dom(t) → Σ^{(1)} aus T_{Σ^{(1)}}. Dann ist φ(t) : dom(t) → Σ^{(2)} definiert durch φ(t)(u) := φ(t(u)).

Satz 6.21 Ist L ⊆ T_{Σ^{(1)}} erkennbar, so auch φ(L) := {φ(t) | t ∈ L}.

Beweis Es sei A = (Q,Σ^{(1)},I,Δ,F) ein BW-Automat für L. Wir definieren A′= (Q, Σ^{(2)}, I′, Δ′, F), wobei

• für a ∈ Σ_{0}^{(2)}:

I′(a) = ⋃_{{a′∈Σ{(1) \atop 0} \atop φ(a′)=a}} I(a′)

• für a ∈ Σ_{n}^{(2)}, n > 0:

Δ′_{a}(q_{1},...,q_{n}) = ⋃_{{a′∈Σ{(1) \atop n} \atop φ(a′)=a}} Δ_{a′}(q_{1},...,q_{n})

Man zeigt leicht, daß L(A′) = φ(L).

□

Satz 6.22 Für reguläre Baumsprachen sind das Äquivalenzproblem und das Leerheitsproblem entscheidbar.

Beweis Da reguläre Baumsprachen unter den Booleschen Operationen abgeschlossen sind genügt es, das Leerheitsproblem zu betrachten. Es sei A = (Q,Σ,I,Δ,F) ein BW-Automat mit |Q| = k Zuständen. Behauptung: L(A) ≠ ∅ genau dann, wenn es einen Baum t der Tiefe ≤ k gibt mit t ∈ L(A). Da es für ein endliches Alphabet Σ nur endlich viele Bäume aus T_{Σ} der Tiefe ≤ k gibt, kann man alle diese Bäume testen. Beweis der Behauptung:

“⇐”  trivial

“⇒”

Es sei t ein Baum minimaler Größe in L(A). Angenommen t hat eine Tiefe > k. Betrachte einen erfolgreichen Lauf von A auf t. Es gibt auf diesem Pfad der Länge > k zwei verschiedene Stellen u, u′mit l(u) = l(u′). Ersetzt man in t den Unterbaum t_{u} durch t_{u′}, so hat man auf dem so erhaltenen Baum immernoch einen erfolgreichen Lauf. Der neue Baum ist aber kleiner als t. Dies ist ein Widerspruch zu der Voraussetzung, daß t minimale Größe hat.

□

96 6 Automaten auf endlichen Bäumen

Automaten auf unendlichen Bäumen

Der Einfachheit halber betrachten wir nur binäre unendliche Bäume, das heißt das Alphabet Σ enthält nur zweistellige Symbole (Σ = Σ_{2}). Alle Resultate lassen sich aber auf den allgemeinen Fall übertragen. Mit \underline{T_{Σ}^{ω}} bezeichnen wir die Menge der unendlichen Bäume über dem Alphabet Σ. Eine Menge L ⊆ T_{Σ}^{ω} heißt \underline{ω-Baumsprache} und t ∈ T_{Σ}^{ω} heißt \underline{ω-Baum} . Man kann ω-Baumsprachen aus Baumsprachen durch unendliche Iteration erhalten. Definition 7.1 Sei Z = {z_{1},...,z_{k}} eine Menge nullstelliger Symbole und Σ ein Alphabet binärer Symbole. U,U_{1},...,U_{k} ⊆ T_{Σ∪Z} seien Baumsprachen über Σ ∪ Z. Die ω-Baumsprache

U ·^{(z_{1},...,z_{k})}(U_{1},...,U_{k})^{ω,(z_{1},...,z_{k})}

besteht aus allen ω-Bäumen t ∈ T_{Σ}^{ω}, für die es eine Folge t_{0},t_{1},t_{2},... von Bäumen aus T_{Σ∪Z} gibt mit

1. t_{0} ∈ U

2. für alle i ≥ 0 ist t_{i+1} ∈ {t_{i}} ·^{(z_{1},...,z_{k})}(U_{1},...,U_{k})

3. t ist Limes dieser Folge, das heißt für alle u ∈ {0,1}^{∗} gibt es ein m ≥ 0 mit

• u ∈ dom(t_{m}) und u ist kein Blatt von t_{m} (d.h. t_{m}(u) ∈ Σ)

• t(u) = t_{m}(u)

□

Beispiel 7.2 Z = {z_{1},z_{2}}, U = {f(z_{1},z_{2})}, U_{1} = {h(z_{1},z_{1})}, U_{2} = {g(z_{2},z_{2})} Da t_{0} ∈ U gelten muß, ist t_{0} = f(z_{1},z_{2}). t_{1} = f(h(z_{1},z_{1}),g(z_{2},z_{2})) (ersetze z_{1} durch U_{1} und z_{2} durch U_{2})

t_{2} = f(h(h(z_{1},z_{1}),h(z_{1},z_{1})),g(g(z_{2},z_{2}),g(z_{2},z_{2})))

Es gibt hier nur eine mögliche Folge, deren Limes t = f(h(h(h(...),h(...)),h(h(...),h(...))),g(g(g(...),g(...)),g(g(...),g(...)))) ist. □

Da unendliche Bäume keine Blätter enthalten, betrachten wir Automaten, deren Lauf an der Wurzel eines Baums beginnt.

Definition 7.3

1. Ein \underline{Büchi-Baumautomat} über dem Alphabet Σ (mit Σ = Σ_{2}) ist von der Form A = (Q,Σ,I,Δ,F), wobei Q,I,Δ wie bei WB-Automaten definiert sind und F ⊆ Q eine Menge von Endzuständen ist.

2. Ein \underline{Rabin-Baumautomat} über dem Alphabet Σ (mit Σ = Σ_{2}) ist von der Form A = (Q,Σ,I,Δ,Ω), wobei Q,I,Δ wie bei Büchi-Baumautomaten definiert sind und Ω = {(F_{1},G_{1}),...,(F_{n},G_{n})} mit F_{i},G_{i} ⊆ Q für i = 1,...,n.

Ein \underline{Lauf} l eines (Büchi- oder Rabin-) Baumautomaten auf einem Baum t ∈ T_{Σ}^{ω} ist wie im endlichen Fall definiert, das heißt l : dom(t) = {0,1}^{∗} → Q mit (l(u0),l(u1)) ∈ Δ_{f} (l(u)), falls t(u) = f. Ein Lauf ist also ein unendlicher binärer Baum über dem Alphabet Q, wobei jedes q ∈ Q zweistellig ist.

[figure: q; u; q_{1}; q_{2}; u_{0}; u_{1}; ⋮]

Ein Lauf l eines Büchi-Baumautomaten heißt \underline{erfolgreich}, falls l(ε) ∈ I und jeder Pfad in l enthält unendlich oft einen Zustand aus F. Ein Lauf l eines Rabin-Baumautomaten heißt \underline{erfolgreich}, falls l(ε) ∈ I und für jeden Pfad in l gibt es ein i (1 ≤ i ≤ n) mit:

• der Pfad enthält unendlich oft einen Zustand aus F_{i}

• der Pfad enthält keinen Zustand aus G_{i} unendlich oft

□

Es wird hier also die Akzeptanzbedingung für Büchi- bzw. Rabin-Baumautomaten auf unendlichen Wörtern auf die Pfade im Baum angewendet. Beachte: Jeder Pfad in t ∈ T_{Σ}^{ω} liefert ein Wort aus Σ^{ω}. L_{ω}(A) = {t ∈ T_{Σ}^{ω} | es gibt einen erfolgreichen Lauf von A auf t} ist die von dem Automaten A \underline{erkannte Sprache}. L ⊆ T_{Σ}^{ω} heißt \underline{Büchi-erkennbar} (\underline{Rabin-erkennbar}) falls L von einem Büchi-Baumautomaten (Rabin-Baumautomaten) erkannt wird.

Satz 7.4 Jede Büchi-erkennbare Sprache ist auch Rabin-erkennbar.

Beweis Es sei A = (Q,Σ,I,Δ,F) ein Büchi-Baumautomat. Wir definieren den Rabin-Automaten A′= (Q,Σ,I,Δ,{F,∅}). Offenbar git L_{ω}(A) = L_{ω}(A′). □

Die folgenden Beispiele sollen den Unterschied zwischen Büchi- und Rabin-Automaten zeigen.

Beispiel 7.5 Σ = {a,b} und L_{1} = {t ∈ T_{Σ}^{ω} | es gibt einen Pfad in t, der unendlich viele a’s enthält }. Der folgende nicht-deterministische Büchi-Baumautomat für L_{1}“rät” einen geeigneten Pfad und nimmt immer, wenn er a liest, einen Endzustand f an. Bei den nicht geratenen Pfaden wird ein anderer Endzustand reproduziert (der unendlich oft vorkommt). A_{1} = ({i,f,□},Σ,{i},Δ_{1},{f,□}) mit

Δ_{1a:} i ↦ {(f,□),(□,f)}
f ↦ {(f,□),(□,f)}
□ ↦ {(□,□)}
Δ_{1b:} i ↦ {(i,□),(□,i)}
f ↦ {(i,□),(□,i)}
□ ↦ {(□,□)}

Der geratene Pfad ist derjenige, welcher mit Zuständen aus {i,f} beschriftet ist. Er enthält unendlich viele a’s genau dann, wenn der Lauf dort unendlich viele f’s enthält. Alle anderen Pfade enthalten unendlich oft □.

[figure: i; a; f; b; b; □; i; b; b; □; a; □; a; □; i; a; b; □; b; □; b; □; b; f; a; □] □

Beispiel 7.6 Σ = {a,b} und L_{2} = {t ∈ T_{Σ}^{ω} | jeder Pfad in t enthält nur endlich viele a’s }, das heißt L_{2} = T_{Σ}^{ω}\L_{1}.

Der Rabin-Automat für L_{2} ist A_{2} = ({i,f},Σ,{i},Δ_{2},Ω_{2}) mit

Δ_{2a} i ↦ {(f,f)}
f ↦ {(f,f)}
Δ_{2b} i ↦ {(i,i)}
f ↦ {(i,i)}

und Ω_{2} = {({i,f},{f})}. Die Idee ist, daß i bedeutet, ein a wurde gelesen, f bedeutet ein b wurde gelesen. Ω_{2} enthält nur ein Element, nämlich ({i,f},{f}), das heißt damit ein Baum akzeptiert wird müssen unendlich oft Zustände aus {i,f} erreicht werden (was keine Einschränkung ist, da i und f die einzigen Zustände des Automaten sind) und der Zustand f (zweite Komponente des Tupels) darf nicht unendlich oft erreicht werden. Gibt es einen Pfad mit unendlich vielen a’s, so hat der zugehörige Lauf einen Pfad mit unendlich vielen f’s, ist also nicht erfolgreich. □

Satz 7.7 Die Sprache L = {t ∈ T_{Σ}^{ω} | jeder Pfad in t enthält nur endlich viele a’s } über dem Alphabet Σ = {a,b} ist Rabin erkennbar, aber nicht Büchi-erkennbar. Beweis Rabin-erkennbar wurde bereits in Beispiel 7.6 gezeigt. Angenommen A = (Q,Σ,I,Δ,F) ist ein Büchi-Baumautomat für L. Es sei n so, daß n > |Q|. Der Baum t^{(n)} sei wie folgt definiert:

U = {ε} ∪
{1^{m_{1}}0 | m_{1} > 0} ∪
{1^{m_{1}}01^{m_{2}} | m_{1},m_{2} > 0} ∪
⋮
{1^{m_{1}}01^{m_{2}}0...1^{m_{n}}0 | m_{1},...,m_{n} > 0}

\begin{aligned}t^{(n)} : & \{0,1\}^{n} & → & Σ \\ & u & ↦ & \{ \begin{matrix}a & u ∈ U \\ b & u ∉ U \end{matrix} \end{aligned}

[figure: a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; a; 0; 1; ε; 1; 1; 1]

Dieser Baum enthält unendlich viele a’s, aber jeder Pfad enthält nur endlich viele a’s: um ein a zu erreichen, muß man in dem Baum (irgendwann einmal) nach links gehen. Spätestens nach n-maligem nach links gehen hat man das letzte a auf diesem Pfad erreicht. Also gilt t^{(n)} ∈ L. Wir konstruieren nun einen Pfad in t^{(n)} wie folgt:

• es sei m_{1} > 0 minimal mit l(1^{m_{1}}) = f_{1} ∈ F. Ein solches f_{1} existiert, da auf dem unendlichen Pfad {ε,1,11,111,...} sogar unendlich viele Endzustände vorkommen.

• es seien m_{1},...,m_{i} > 0 für ein i < n bereits definiert. Sei m_{i+1} > 0 minimal mit l(1^{m_{1}}01^{m_{2}}0...1^{m_{i}}01^{m_{i+1}}) = f_{i+1} ∈ F.

Dies definiert m_{1},...,m_{n} > 0 mit t^{(n)}:

[figure: a; a; a; a; b; b; b; ε; 1^{m_{1}}; 1^{m_{2}}; 1^{m_{n}}; f_{1} ∈ F; f_{2} ∈ F; f_{n} ∈ F; 0; 0; 0]

Da |Q| < n angenommen war, gibt es i < j mit f_{i} = f_{j}.

Wir haben die folgende Situation:

[figure: a; u; f_{i}; uv; f_{i} = f_{j}]

Setzt man daher in t^{(n)} an der Stelle uv den Baum t_{u}^{(n)} ein, so erhält man einen Baum, für den es ebenfalls einen erfolgreichen Pfad gibt. Iteriert man dieses Vorgehen unendlich oft, so erhält man einen Baum, der von A akzeptiert wird, aber einen Pfad enthält, auf dem a unendlich oft vorkommt (nämlich jeweils zwischen den Positionen u,uv,uvv,uvvv,...). □

Korollar 7.8 Die Klasse der Büchi-erkennbaren ω-Baumsprachen ist nicht unter Komplement abgeschlossen. Beweis Σ = {a,b}. L_{1} = {t ∈ T_{Σ}^{ω} | es gibt einen Pfad in t, der unendlich oft a’s enthält }, L_{2} = {t ∈ T_{Σ}^{ω} | jeder Pfad in t enthält nur endlich viele a’s }. L_{1} ist Büchi-erkennbar (vergleiche Beispiel 7.5), L_{2} = T_{Σ}^{ω}\L_{1} ist nicht Büchi-erkennbar (vergleiche Satz 7.7). □

Satz 7.9 (Rabin) Die Klasse der Rabin-erkennbaren ω-Baumsprachen ist unter Komplement abgeschlossen.

□

Der Beweis dieses Satzes ist sehr aufwendig. Es gibt verschiedene Beweisansätze (siehe

zum Beispiel Thomas: Handbook of Theoretical Computer Science für Literaturhinweise.)

Spieltheoretische Ansätze haben sich auch hier als sehr hilfreich erwiesen. Wieso ist dieses Problem schwieriger als bei Wörtern? Dies liegt an der Quantifizierung über Pfade in der Akzeptanzbedingung: Für alle Pfade ist die Akzeptanzbedingung erfüllt. Negiert man das, so erhält man “Es gibt einen Pfad, für den die Akzeptanzbedingung nicht erfüllt ist.” Man muß nicht nur (wie bei Wörtern) von “nicht erfüllt” wieder zu “erfüllt” kommen, sondern auch von “existiert Pfad” wieder zu “alle Pfade”.

Satz 7.10 Das Leerheitsproblem ist für Büchi-erkennbare ω-Baumsprachen entscheidbar.

Den Beweis zu diesem Satz werden wir später führen. Es sei A = (Q,Σ,I,Δ,F) ein Büchi-Baumautomat, wobei F = {f_{1},...,f_{n}}. Es sei l: {0,1}^{∗} → Q ein erfolgreicher Lauf von A auf dem Baum t ∈ T_{Σ}^{ω}. Der Baum t soll zerlegt werden in endliche Teilbäume, welche von Automaten auf endlichen Bäumen akzeptiert werden. Es sei u ∈ {0,1}^{∗} beliebig. Wir interessieren uns dafür, wo in l nach u das erste Mal wieder Endzustände auftreten.

D_{u}:= {w ∈ {0,1}^{∗} | l(uv) ∉ F für alle ε < v ≤ w}

Offenbar stellt D_{u} einen endlich verzweigten Baum dar, in dem es keinen unendlichen Pfad gibt. Dies gilt, da l erfolgreich ist, und daher, um unendlich oft einen Endzustand zu erreichen, auch nach der Stelle u noch Endzustände unendlich oft erreicht werden müssen. Also ist D_{u} endlich. Es sei jetzt D_{u}^{+} := D_{u}∪ {wσ | σ ∈ {0,1},w ∈ D_{u},wσ ∉ D_{u}} Nach der Definition von D_{u} gilt jetzt für alle wσ ∈ D_{u}^{+} \D_{u}: l(wσ) ∈ F. Beispiel Betrachte den Lauf des Büchi-Automaten aus Beispiel 7.5

[figure: i; b; i; b; a; □; i; a; b; □; b; □; b; □; f; b; a; □; b; □; b; □]

Zur Erinnerung: f und □ sind Endzustände. Es gilt:

\begin{aligned}D_{ε} & = & \{ε,0,00\} \\ D_{ε}^{+} \D_{ε} & = & \{1,01,000,001\} \\ D_{1} & = & \{ε\} \\ D_{1}^{+} \D_{1} & = & \{00,1\} \end{aligned}

Für u ∈ {0,1}^{∗} definieren wir den endlichen Baum t̂_{u}: D_{u}^{+} → Σ∪F (in dem die Endzustände zusätzlich als Blätter eingeführt werden):

• für w ∈ D_{u}: t̂_{u}(w) = t(uw)

• für w ∈ D_{u}^{+} \D_{u}: t̂_{u}(w) = l(uw)

t̂_{u}∈ T_{Σ∪F} , f ∈ F ist 0-stellig.

Beispiel

[figure: t̂_{ε}:; b; b; □; a; □; f; □; t̂_{1}:; a; □; □]

Für jedes q ∈ Q des Büchi-Automaten A betrachten wir nun den WB-Automaten A_{q} = (Q,Σ ∪ F,{q},Δ,F̂), wobei Δ wie in A definiert ist und für f ∈ F : F̂(f) = {f}. Es sei nun L_{q} = L(A_{q}) (dies ist eine endliche Sprache eines endlichen Baumes). Es gilt: Ist l(u) = q, so ist t̂_{u}∈ L_{q}. Das folgende Bild zeigt beispielhaft einen erfolgreichen Lauf von A_{i} auf t̂_{ε}:

[figure: b; i; b; i; □; □; a; i; □; □; f; f; □; □]

Dies zeigt, daß

t ∈ L̂:= ( ⋃_{i∈I} L_{i}) ·^{(f_{1},...,f_{m})} (L_{f_{1}},...,L_{f_{m}})^{ω,(f_{1},...,f_{m})}

Umgekehrt ist jedes Element von L̂auch in L_{ω}(A), das heißt

L̂= L_{ω}(A).

Satz 7.11 Für eine Sprache L ⊆ T_{Σ}^{ω} sind äquivalent

1. L ist Büchi-erkennbar

2. Es gibt erkennbare Sprachen L_{0},L_{1},... L_{m}⊆ T_{Σ∪F} für ein Alphabet F = {f_{1},...,f_{m}} von 0-stelligen Symbolen, so daß gilt

L = L_{0}·^{(f_{1},...,f_{m})} (L_{1},...,L_{m})^{ω,(f_{1},...,f_{m})}

Beweis

1 ⇒ 2 wurde bereits gezeigt

2 ⇒ 1 Konstruiere aus WB-Automaten für L_{0},...,L_{m} einen Büchi-Automaten für L.

□

Beweis von Satz 7.10 Es sei A = (Q,Σ,I,Δ,F) ein Büchi-Automat für L. Die Sprachen L_{q} seien wie oben definiert: L_{q} = L(A_{q}). Wir eliminieren jetzt sukzessive Zustände, die nicht in einem erfolgreichen Lauf auftreten können.

1. Eliminationsschritt Der Automat A_{1} = (Q_{1},Σ,I_{1},Δ_{1},F_{1}) entsteht aus A durch Entfernen aller Zustände q ∈ Q mit L_{q} = ∅. Da L_{q} erkennbare Baumsprache ist, kann man L_{q} = ∅ ? nach Satz 6.22 entscheiden:

• Q_{1} = Q\{q ∈ Q | L_{q} = ∅}

• Δ_{1a} = Q_{1} → 2^{Q_{1}×Q_{1}} : q ↦ Δ_{a}(q) ∩ Q_{1}× Q_{1}

• F_{1} = F ∩ Q_{1}

Behauptung: L_{ω}(A_{1}) = L_{ω}(A)

denn Ist L_{q} = ∅, so kann q nicht in einem erfolgreichen Lauf l vorkommen. Wir hatten nämlich gesehen, daß dann für l(u) = q gilt: ˆ (t)_{u}∈ L_{q}.

Dadurch kann sich die Sprache L_{q} ändern:

[figure: q; f; f]

In A : L_{q} ≠ ∅, aber L_{f} = ∅. In A_{1} kann L_{q} = ∅ sein!

2. Iteriert man dieses Vorgehen, so erhält man nach spätestens |Q| Schritten einen Automaten A_{n} mit L_{ω}(A_{n}) = L_{ω}(A) und L_{q} ≠ ∅ in A_{n} für alle q ∈ Q_{n} (beachte: Q_{n} = ∅ ist möglich).

3. L_{ω}(A_{n}) ≠ ∅ gdw I_{n} ≠ ∅ Wir wissen:

L_{ω}(A_{n}) = ( ⋃_{i∈I_{n}} L_{i}) ·^{(f_{1},...,f_{m})} (L_{f_{1}},...,L_{f_{m}})^{ω,(f_{1},...,f_{m})}

wobei F_{n} = {f_{1},...,f_{m}}.

Der Ausdruck auf der rechten Seite ist offensichtlich leer, wenn I_{n} = ∅. Ist umgekehrt I_{n} ≠ ∅, so folgt F_{n} ≠ ∅ (da sonst L_{q} = ∅ für alle q ∈ Q_{n}).

Damit enthält der Ausdruck auf der rechten Seite einen unendlichen Baum:

Sei t_{0} ∈ L_{i} (für ein i ∈ I_{n}), t_{1} ∈ L_{f_{1}}, ..., t_{m}∈ L_{f_{m}}. Dann ist

{t_{0}} ·^{(f_{1},...,f_{m})} ({t_{1}},...,{t_{m}})^{ω,(f_{1},...,f_{m})} ∈ L_{ω}(A_{n})
□

Beispiel Betrachte den Automaten aus Beispiel 7.5.

[figure: a; f; □; ∈ L_{i}; b; □; □; ∈ L_{□}; a; f; □; ∈ L_{f}]

Der unendliche Baum, den wir erhalten, sieht nun folgendermaßen aus:

[figure: a; a; b; a; b; b; b; a; b; b; b; a; b; ∈ {a(f,□)} ·^{(f,□)} ({a(f,□)},{b(□,□)})^{ω,(f,□)}]

Satz 7.12 Das Leerheitsproblem für Rabin-erkennbare ω-Baumsprachen ist entscheidbar.

□

Beweisidee Es sei A = (Q,Σ,I,Δ,Ω) ein Rabin-Baumautomat. Ein Zustand q ∈ Q heißt \underline{passiv}, falls für alle a ∈ Σ und (q_{1},q_{2}) ∈ Δ_{a}(q) gilt: q_{1} = q = q_{2} (anschaulich: ist man einmal in diesem Zustand, bleibt man auch darin). q ∈ Q heißt \underline{aktiv}, falls gilt:

1. q ist nicht passiv und

2. q ist nicht Anfangszustand, der nicht mehr erreichbar ist (das heißt (q_{1},q_{2}) ∈ Δ_{a}(q) ⇒ q ∉ {q_{1},q_{2}}).

Entscheidbarkeit des Leerheitsproblems wird jetzt durch Induktion über die Anzahl der aktiven Zustände gezeigt. Induktionsanfang: keine aktiven Zustände Ein erfolgreicher Lauf, der mit Zustand i ∈ I beginnt, sieht jetzt wie folgt aus:

1. Fall: i ist passiv (i reproduziert sich)

[figure: i; i; i; i; i; i; i]

Damit dieser Lauf erfolgreich ist, muß gelten:

• i ∈ I

• es gibt ein a ∈ Σ mit (i,i) ∈ Δ_{a}(i)

• es gibt (F,G) ∈ Ω mit i ∈ F und i ∉ G

Man kann feststellen, ob es ein solches i gibt.

2. Fall: i ist Anfangszustand, der nicht mehr erreicht wird

[figure: i; q_{1}; q_{2}; q_{1}; q_{1}; q_{2}; q_{2}]

Da es nach Voraussetzung keine aktiven Zustände gibt, sind q_{1},q_{2} passiv, das heißt sie reproduzieren sich. Man kann jetzt entsprechend zum 1. Fall leicht feststellen, ob es einen erfolgreichen Lauf geben kann.

Induktionsschritt: Der Induktionsschritt ist recht kompliziert, vergleiche Thomas: Handbook of Theoretical

Computer Science.

Baumautomaten und logische Formeln

S1S wird durch die Einführung von zwei Nachfolgerfunktionen verallgemeinert. Als Interpretation betrachtet man statt INden unendlichen binären Baum. Definition 8.1

1. Formeln von \underline{S2S} sind wie S1S-Formeln aufgebaut. Der Unterschied besteht darin, daß statt der Nachfolgerfunktion s nun zwei Funktionen s_{0} und s_{1} und statt \underline{0} die Konstante ε verwendet wird.

2. Als Interpretationsbereich verwenden wir {0,1}^{∗} (Träger des unendlichen binären Baums), wobei

• \underline{ε}als ε interpretiert wird

• s_{0} : u ↦ u0 s_{1} : u ↦ u1

• < als Präfixordnung auf {0,1}^{∗} interpretiert wird, das heißt u < v gdw ∃w ∈ {0,1}^{+} mit uw = v

• P_{1},...,P_{n} als Teilmengen von {0,1}^{∗} interpretiert werden

3. WS2S entsteht aus S2S dadurch, daß Quantoren zweiter Stufe nur über endlichen Teilmengen von {0,1}^{∗} quantifizieren dürfen.

□

S2S-Formeln können dazu verwendet werden, ω-Baumsprachen zu definieren. Wie bei S1S ist das Alphabet Σ = {0,1}^{n}, wobei n die Anzahl der einstelligen Prädikatsymbole ist. Jedes Element von Σ erhält die Stelligkeit 2. Eine S2S-Interpretation I kann als ω-Baum t_{I} ∈ T_{Σ}^{ω} aufgefaßt werden:

t_{I}(u) = (b_{1},...,b_{n}) mitb_{i} = \{ {1 n ∈ P_{i}^{I} \atop 0 n ∉ P_{i}^{I}}

Definition 8.2 Sei φ eine geschlossene S2S-Formel.

L_{ω}(φ) := {t_{I} ∈ T_{Σ}^{ω} | I ⊧ φ}
□

Beispiele für S2S-Formeln:

• Kette(X) gdw ∀x∀y (X(x) ∧ X(y) → x < y ∨ x = y ∨ y < x)

beschreibt eine Teilmenge X von {0,1}^{∗}, in der je zwei Elemente präfixvergleichbar sind

• Pfad(X) gdw Kette(X) ∧ ∀Y (X ⊆ Y ∧ Kette(Y) → X = Y) Pfade sind maximale Ketten

• UnendlicheKette(X) gdw Kette(X) ∧ ∀x (X(x) → ∃y (x < y ∧ X(y)))

• Endlich(X) gdw ¬∃Y (Y ⊆ X ∧ UnendlicheKette(Y))

Mit Hilfe des Lemmas von König kann man zeigen: Ist X unendliche Teilmenge von {0,1}^{∗}, so enthält das X eine unendliche Kette Die folgende Formel zeigt, daß man WS2S in S2S ausdrücken kann. Die Umkehrung gilt hier nicht.

Z = Präfixabschluß(Y) ⇔ ∀z (Z(x) ↔ ∃y (Y (y) ∧ z ≤ y))

Beispiel 8.3 Es sei n = 1, das heißt Σ = {0,1}.

1. L_{1} = {t ∈ T_{Σ}^{ω} | es gibt einen Pfad in t, der unendlich viele 1en enthält} L_{1} = L_{ω}(φ_{1}), wobei

φ_{1} = ∃Y (Pfad(Y) ∧
∀x (Y (x) → ∃y (Y (y) ∧ x < y ∧ P_{1}(y))))

2. L_{2} = T_{Σ}^{ω}\L_{1} L_{2} = L_{ω}(¬φ_{1})

□

Satz 8.4 Für eine ω-Baumsprache L ⊆ T_{Σ}^{ω} sind äquivalent:

1. L ist Rabin-erkennbar

2. L = L_{ω}(φ) für eine geschlossene S2S-Formel φ

□

Beweis (sehr ähnlich zum Beweis von Satz 5.4) “1 ⇒ 2”

Sei A = (Q,Σ,I,Δ,Ω) ein Rabin-Automat mit Q = {q_{1},...,q_{m}}. Für jedes q_{i} führen wir eine Variable zweiter Ordnung Y_{i} ein. Die Idee dabei ist, daß Y_{i}(x) gilt genau dann, wenn q_{i} an Position x im Lauf steht. Die Existenz eines erfolgreichen Laufs wird dann durch folgende Formel beschrieben: ∃Y_{1}...∃Y_{m}: (¬(Y_{i}(x) ∧ Y_{j}(x)) ∧ ⋁ _{q_{i}∈I} Y_{i}(\underline{ε}) ∧

∀x (⋁ _{{a∈Σ \atop (q_{i},q_{j})∈Δa(q_{k})}}  Y_{k}(x) ∧
Q_{a}(x) ∧
Y_{i}(s_{0}(x)) ∧
Y_{j}(s_{1}(x))) ∧
∀Z (Pfad(Z) → ⋁ _{(F,G)∈Ω} (⋁ _{q_{i}∈F} ∀x (Z(x) →
∃y (x < y ∧ Z(y) ∧ Y_{i}(y))) ∧
⋀ _{q_{i}∈G} ∃x∀y (x < y ∧ Z(y) →
¬Y_{i}(y)))))

“2 ⇒ 1”

Wie für S1S reduziert man S2S-Formeln auf S2S_{0}-Formeln. Man verwendet Induktion über den Aufbau von S2S_{0}-Formeln. Wichtig ist hier wieder der Abschluß der Rabin-erkennbaren Sprachen unter Booleschen Operationen und Alphabetumbenennung.

□

Korollar 8.5 Gültigkeit in S2S ist entscheidbar.

□

Es gibt einen interessanten Zusammenhang zwischen Büchi-erkennbaren ω-Baumsprachen und WS2S.

Satz 8.6

1. L ⊆ T_{Σ}^{ω} ist Büchi-erkennbar genau dann, wenn L = L_{ω}(φ) für eine S2S-Formel φ der Gestalt ∃Y_{1}...∃Y_{m} ψ(Y_{1},...,Y_{m}), wobei ψ eine WS2S-Formel ist.

2. L ⊆ T_{Σ}^{ω} kann durch eine WS2S-Formel definiert werden genau dann, wenn L und \overline{L} Büchi-erkennbar sind.

□

Insbesondere ist also WS2S sogar noch ausdrucksschwächer als Büchi-Automaten, zum Beispiel kann L_{1} aus Beispiel 8.3 nicht durch WS2S-Formeln definiert werden, da \overline{L_{1}} nicht Büchi-erkennbar ist. Anstelle binärer Bäume kann man auch Bäume vom Verzweigungsgrad k betrachten. Es gelten die entsprechenden Resultate wie für k = 2. Man kann Büchi-Automaten für Bäume von Verzweigungsgrad k verwenden, um Entscheidbarkeit der Logik DPDL zu zeigen (für k atomare Programme p_{0}, ..., p_{k−1}).

Definition 8.7 Die Formeln der Logik \underline{DPDL} sind wie die von 1DPDL definiert, mit dem Unterschied, daß man nun k atomare Programme p_{0},...,p_{k−1} zum Aufbau von Programmformeln verwenden kann. Eine Interpretation weist jedem p_{i} eine funktionale Relation p_{i}^{I} ⊆ Δ^{I} × Δ^{I} zu.

□

Wie im Fall k = 1 kann man Programmformeln als reguläre Sprachen (über Σ = {p_{0},...,p_{k−1}}) beschreiben und damit wieder Programmformeln durch Zustände eines geeigneten Automaten B ersetzen. Der Fisher-Ladner-Abschluß einer DPDL-Formel φ_{0} in Negations-Normalform (NNF) wird entsprechend zum Fall k = 1 definiert, zum Beispiel gilt < q > φ ∈ F L(φ_{0}) → φ ∈ F L(φ_{0}) ∧ < q′> φ ∈ F L(φ_{0}) für alle q′mit (q,p_{i},q′) ∈ Δ für ein i, 0 ≤ i < k. Die Rolle des Hintikka-Worts im Fall k = 1 wird von dem Hintikka-Baum übernommen. Es sei Σ = 2^{F L(φ_{0})}.

Definition 8.8 Ein Baum t : \{0,1,...,k − 1\}^{∗} → Σ ist ein \underline{Hintikka-Baum} für φ_{0}, falls gilt^{1}

1. φ̂_{0} ∈ t(ε) und für alle u ∈ {0,1,...,k − 1}^{∗} gilt

2. t(u) = ∅ oder (A_{i} ∈ t(u) gdw ¬A_{i} ∉ t(u) für alle atomaren Eigenschaften A_{i})

3. φ ∧ ψ ∈ t(u) gdw φ ∈ t(u) und ψ ∈ t(u)

4. φ ∨ ψ ∈ t(u) gdw φ ∈ t(u) oder ψ ∈ t(u)

5. [q]φ ∈ t(u), dann gilt

5.1 ε ∈ L(B_{q}), so φ ∈ t(u)

5.2 für alle i, 0 ≤ i < k gilt t(ui) = ∅ oder für alle q′mit (q,p_{i},q′) ∈ Δ : [q′]φ ∈ t(ui)

6. < q > φ ∈ t(u), dann gibt es ein Wort w = p_{i_{1}} ...p_{i_{r}} und Zustände q_{1},...,q_{r} von B mit

• q_{r} ist Endzustand, das heißt w ∈ L(B_{q})

• q −→^{p_{i_{1}}} q_{1} −→^{p_{i_{2}}} q_{2}... −→^{p_{ir}} q_{r}

• < q_{i} > φ ∈ t(ui_{1}...i_{j}) 1 ≤ j < r

• φ ∈ t(ui_{1}...i_{r})

7. t(u) = ∅, so auch t(ui) = ∅ für alle i 0 ≤ i < k

□

1Die Definition eines Hintikka-Wortes sollte an diese Definition angepasst werden

8 Baumautomaten und logische Formeln 113

Satz 8.9 φ_{0} ist erfüllbar genau dann, wenn es einen Hintikka-Baum für φ_{0} gibt.

□

Man betrachtet zunächst wieder einen lokalen Büchi-Baumautomaten A_{L}(φ_{0}), der statt der globalen Bedingung 6 aus Definition 8.8 die lokale Bedingung 6’ überprüft.

6’. < q > φ ∈ t(u), dann gilt 6’.1 ε ∈ L(B_{q}) und φ ∈ t(u) oder 6’.2 es gibt ein i, 0 ≤ i < k und q′mit (q,p_{i},q′) ∈ Δ und < q′> φ ∈ t(ui)

Definition 8.10 A_{L}(φ_{0}) := (Q_{L},Σ,I_{L},Δ_{L},F_{L}) mit

• Q_{L} = {α ∈ 2^{F L(φ_{0})} | α erfüllt 2,3,4 von Definition 8.8}

• Σ = 2^{F L(φ_{0})}

• I_{L} = {α ∈ Q_{L} | φ̂_{0} ∈ α}

• F_{L} = Q_{L}

• Für alle σ ∈ Σ und t(u) ∈ Q_{L} gilt t(u) ≠ σ ⇒ Δ_{L,σ}(t(u)) = ∅ t(u) = σ ⇒ Δ_{L,σ}(t(u)) = {(t(u0),...,t(u(k − 1)))| 5, 6’ und 7 sind erfüllt }

□

Um zu erzwingen, daß <>-Formeln schließlich erfüllt werden, erweitert man A_{L} zum Hintikka-Automaten (der ein Büchi-Automat ist). Definition 8.11 A_{H}(φ_{0}) = (Q_{H},Σ,I_{H},Δ_{H},F_{H}) mit

• Q_{H} = Q_{L}× 2^{F L_{<>} (φ_{0})}, wobei F L_{<>} (φ_{0} = {< q > φ | < q > φ ∈ F L(φ_{0})}

• Σ = 2^{F L(φ_{0})}

• I_{H} = I_{L}× {∅}

• F_{H} = F_{L}× {∅} = Q_{L}× {∅}

• Δ_{H,σ}((α,s)) = 1. Fall s = ∅ ((β_{0},t_{0}),...,(β_{k−1},t_{k−1})) ∈ Δ_{H,σ}((α,∅)) gdw

– (β_{0},...,β_{k−1}) ∈ Δ_{L,σ}(α) und

– für jedes < q > φ ∈ σ mit (ε ∉ L(B_{q}) oder φ ∉ α) gibt es ein i, 0 ≤ i < k und

ein q′so daß < q′> φ ∈ t_{i}∩ β_{i} und (q,p_{i},q′) ∈ Δ

2. Fall s ≠ ∅

entsprechend, wobei (wie bei k = 1) “< q > φ ∈ σ” ersetzt wird durch “< q > φ ∈ s” □ Satz 8.12 A_{H}(φ_{0}) akzeptiert genau die Hintikka-Bäume für φ_{0}.

□

Satz 8.13 Erfüllbarkeit in DPDL ist entscheidbar.

□

Beachte: Entscheidbarkeit in exponentieller Zeit kann gezeigt werden, da das Leerheitsproblem für Büchi-erkennbare Sprachen in polynomieller Zeit entschieden werden kann. Diese Entscheidbarkeit in polynomieller Zeit folgt aber nicht aus dem von uns betrachteten Verfahren.

Index

L_{ω}(φ), 112 Reg(T_{Σ},Z), 95 T_{Σ}, 86 T_{Σ}^{ω}, 99 Σ-Baum, 85 Σ-beschrifteter Baum, 85 Σ_{n}, 85 ≡_{k,n}, 37 ω-Baum, 99 ω-Baumsprache, 99 ω-reguläre Sprache, 62 ∼_{A}, 57 ∼_{A}, 7 A_{H}(φ_{0}), 83 F, 62 1DPDL, 76, 83

Abschlußeigenschaft, 1, 2 akzeptiert, 37 akzeptierte Baumsprache, 88 akzeptierte Sprache, 6 Alphabet mit Stelligkeitsfunktion, 85 α(m,n), 48 α(m,∞), 48 Anfangssegment, 47 aperiodischer Monoid, 32 äquivalente Zustände, 7 Äquivalenzklasse, 37 Ausdruck

regulärer, 5 Automat

Büchi, 49 BW-Baum-, 87 deterministischer, 6 deterministischer Büch-, 62 deterministischer Büchi-, 56 lokaler, 82 minimaler, 7 Muller, 62

nicht-deterministischer, 5

(B_{0})_{Σ}, 23 Büchi-Baumautomat, 100 Büchi-erkennbar, 100 Baumautomat, Büchi-, 100 Baumautomat, Rabin-, 100 binäres Prädikat, 19 Blatt, 86 Boolesche Operatoren, 35 Boolescher Abschluß, 23 Büchi, Satz von, 52 Büchi-Automat, 49 Büchi-erkennbar, 49 BW-Baumautomat, 87

Charakterisierung, 1 Chomsky-Hierarchie, 1

EID, 26 DEA, 6 deterministische Büchi-Automaten, 62 deterministischer Büchi-Automat, 56 deterministischer BW-Baumautomat, 88 deterministischer endlicher Automat, 6 direktes Produkt, 15, 19 Disjunktive Normalform, 36 DPDL, 114

Ehrenfeucht-Fraissé Spiel, 40 Eilenberg/Schützenberg, Satz von, 17 endliche Interpretation, 19 endlicher Baum, 86 endlicher Index, 12 endlicher Monoid, 8 endliches Wort, 47 Entscheidbarkeit, 1 Entscheidungsproblem, 2 erfolgreicher Lauf, 88 erfolgreicher Lauf eines Büchi-Baumautomaten,

100 erfolgreicher Lauf eines Rabin-Baumautomaten,

100 erfolgreicher Pfad, 6, 62, 90 Erfüllbarkeit in 1DPDL, 83 erfüllen einer Gleichung, 16 erkennbar, 92

FL(φ_{0}), 80 Fortsetzungsspiel, 41 freie Variable, 20, 37

geschlossene Formel, 20 gewinnen, 40 Gewinnstrategie, 41 Gleichung, 16 Gruppe in M, 33

Halbgruppe, 25 Halbgruppen, 19 Hintikka-Baum, 84, 114 Hintikka-Wort, 81 homogene Teilmenge, 59 homomorphes Bild, 15, 19 Homomorphismus, 8, 16 Homomorphismus, kanonischer, 18

idempotent, 25 Interpretation, 77 Iteration, unendliche, 48

Klasse der regulären Sprachen, 5, 15 Kleene, Satz von, 6 kommutativer Monoid, 16 Komposition, 10 Konfigurationsformel, 76 Kongruenzrelation, 11 Konkatenation, 48 K_{Σ}, 1

L_{k,n}, 37 L(V), 15 Lauf

Büchi-Baumautomat, 100 Rabin-Baumautomat, 100

Lauf eines BW-Baumautomaten, 88 Lauf eines WB-Automaten, 90 Lauf, erfolgreich, 100 Limes, 48 Logik erster Stufe, 20, 34, 45 Logik mit Gleichheit, 19 Logik zweiter Stufe, 65 lokaler Automat, 82 L_{p,q}, 50

M-Varietät, 15, 17 minimaler Automat, 7 Minimierung, 13 Modell, 20, 78 Monadische Logik zweiter Stufe eines Nach-

folgers, 65 Monoid, 8

akzeptiert von, 9 aperiodischer, 32 endlicher, 8 freies, 8 syntaktischer, 10, 11, 13

Muller-Automat, 62

NEA, 5

Negationsnormalform, 80 Nerode, Satz von, 8 Nerode-Rechtskongruenz, 7 nicht-deterministischer endlicher Automat,

5 NNF, 80 Normalform einer S1S-Formel, 67 Normalform, Disjunktive, 36

ω-regulär, 53

ω-regulärer Ausdruck, 53

ω-Sprache, 47

Pfad, 6 erfolgreich, 6 erfolgreicher, 49, 62 in Muller-Automaten, 62 unendlicher, 49, 62 Pfad in einem Baum, 86 Potenzmengenkonstruktion, 7, 13, 89 Präfixrelation, 86 Presburger Arithmetik, 72 Programmformel, 76

Quantifizierung, 22 Quantorentiefe, 35, 37 Quotientenmonoid, 11

Rabin, Satz von, 104 Rabin-Baumautomat, 100 Rabin-erkennbar, 100 Ramsey, Satz von, 60 Rechtskongruenz, 8 Rechtskongruenz, Nerode-, 7 Rechtsnullen, 14 reguläre Baumsprache, 95 regulär, 9 reguläre Sprache, 5 regulärer Ausdruck, 5 Relativierung, 35

S-Varietät, 19, 25, 26 S1S, 65 S1S_{0}-Formeln, 67 S1S-Formel, Normalform, 67 S2S, 111 saturiert, 75 Satz

Büchi, 52

Eilenberg/Schützenberg, 17 Kleene, 6 Nerode, 8 Ramsey, 60 Schützenberg, 33

Satz von Rabin, 104 schließlich definiert, 17, 26 Schützenberg, Satz von, 33 Segment, 48 Σ^{ω}, 47 Spiel der Länge n, 40 Spiel, Ehrenfeucht-Fraissé, 40 Sprache

ω-regulär, 62 akzeptierte, 6 formale, 1 reguläre, 5 sternfreie, 31 verallgemeinert-definit, 23

Stelligkeitsfunktion, 85 sternfreie ω-Sprache, 74 sternfreie Sprachen, 31, 35 syntaktische Halbgruppe, 19 syntaktische Kongruenz, 11, 19 syntaktischer Monoid, 10, 11

Terme, 29 Theorie der totalen Ordnung, 45 totale Ordnung, 19

Übergangsfunktion, 7 Übergangshalbgruppe, 19 Übergangsmonoid, 10, 14 Übergangsrelation, 5 unendliche Iteration, 48 Untergruppenbildung, 19 Unterhalbgruppe, 33 Untermonoid, 10, 15

verallgemeinert-definite Sprache, 23

WB-Automat, 89

Wort endliches, 47 unendliches, 47

zugehörige Formel, 29 zugehörige Sprachklasse, 19 zyklische Gruppe, 32