Inhaltsverzeichnis

1 Alphabete, Wörter, Sprachen 3

2 Reguläre Sprachen 5 2.1 Reguläre Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Deterministische endliche Automaten (DFA) . . . . . . . . . . . . . . . . . . 8 2.3 Nicht deterministische endliche Automaten (NFA) . . . . . . . . . . . . . . . 8 2.4 Synthese und Analyse endlicher Automaten . . . . . . . . . . . . . . . . . . 10 2.5 Das Pumping - Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.6 Zustandsreduktion endlicher Automaten . . . . . . . . . . . . . . . . . . . . 12 2.7 Entscheidbare Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.7.1 Deterministische endliche Automaten (DFA) . . . . . . . . . . . . . . 15 2.7.2 Reguläre Ausdrücke, nicht-deterministische Automaten (NFA) …. 16

2.8 endliche Automaten mit Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . 16 2.9 Automaten als abstrakte Programme . . . . . . . . . . . . . . . . . . . . . . 16

2.9.1 GOTO-Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.9.2 Parallele Programme, Verteilte Systeme . . . . . . . . . . . . . . . . . 17

3 Kontextfreie Grammatiken und Kellerautomaten 19 3.1 Kontextfreie Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Einseitig-lineare Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Normalformen von kontextfreien Grammatiken . . . . . . . . . . . . . . . . . 22

3.3.1 Die Chomsky-Normalform . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.2 Die Greibach-Normalform, Linksrekursion . . . . . . . . . . . . . . . 25

3.4 Abschlußeigenschaften von CFL, Pumping-Lemma . . . . . . . . . . . . . . . 26 3.5 Entscheidbare Eigenschaften von CFG . . . . . . . . . . . . . . . . . . . . . 28 3.6 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.6.1 Deterministische Kellerautomaten . . . . . . . . . . . . . . . . . . . . 30 3.7 Der Algorithmus von Cocke, Younger und Kasami . . . . . . . . . . . . . . . 31 3.8 Erweiterte kontextfreie Grammatiken (EBNF) . . . . . . . . . . . . . . . . . 32 3.9 Rekursive endliche Automaten (Syntaxdiagramme) . . . . . . . . . . . . . . 33 4 Turingmaschinen und Aufzählbare Sprachen 35

4.1 Chomsky-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.1.1 Kontextrekursive Grammatiken und Sprachen . . . . . . . . . . . . . 38 4.2 Turingmaschinen, linear beschränkte Automaten . . . . . . . . . . . . . . . . 39

4.2.1 Deterministische Turingmaschine, k-Band TM . . . . . . . . . . . . . 42 4.3 Aufzählbare und entscheidbare Sprachen . . . . . . . . . . . . . . . . . . . . 43

5 Unentscheidbare Probleme 45

Kapitel 1

Alphabete, Wörter, Sprachen

Zeichenreihen als Grundobjekte in der Informatik

1. Grundbegriff

Σ : Alphabet, nicht-leere, endliche Menge a ∈ Σ : Buchstabe, Charakter, Symbol

2. Grundbegriff

Σ^{∗} : Menge der Wörter über Σ Σ^{∗} := {a_{1}, a_{2}, ..., a_{n} | n ∈ ℕ, a_{i} ∈ Σ} Wörter, Zeichenreihen, Zeichenketten, Strings n = 0 : das leere Wort, Bez.: ϵ

Operationen auf Σ^{∗}:

• Verkettung (Konkatenation)

· : Σ^{∗} × Σ^{∗} → Σ (w , v) ↦ w · v := wv

Es gilt:

1. · ist assoziativ: (u · v) · w = u · (v · w)

2. ϵ ist · - (verkettungs-) neutral : ϵ · w = w · ϵ = w Sprechweise: < Σ* ; · ; ϵ > ist eine Halbgruppe mit Eins (\underline{Monoid}) . Bemerkung: freie Erzeugung.

• Länge eines Wortes: w = a_{1}a_{2}...a_{n} ∈ Σ^{∗}, |a_{1}...a_{n}| := n, falls alle a_{i} ∈ Σ, also: |ϵ| = 0 und |wv| = |w| + |v| • Potenzen eines Wortes w ∈ Σ^{∗} :

w^{0} := ϵ

w^{n+1} := w · w^{n}

• Spiegelbild eines Wortes:

ϵ^{R} := ϵ

(wa)^{R} := a(w)^{R}

3. Grundbegriff:

p(Σ^{∗}): Menge der sogenannten formalen Sprachen über Σ. Eine (formale) Sprache (über Σ) ist eine beliebige Teilmenge von Σ^{∗}. Es bestehen folgende Beschreibungsmöglichkeiten für Sprachen: Automaten und Grammatiken. (Potenzmenge ≡ Menge aller Teilmengen)

p(Σ^{∗}) := {L | L ⊆ Σ^{∗}}

Beispiel: ∅, {ϵ}, {w_{1}, w_{2}, ..., w_{n}}, Σ^{∗}

Operationen auf p(Σ^{∗})

• Boolesche Operation: L_{1} ∪ L_{2}, L_{1} ∩ L_{2}, \overline{L} := Σ^{∗} \ L

• Komplexprodukt (jeder mit jedem): L_{1}L_{2} := {w_{1}w_{2} | w_{i} ∈ L_{i}} LL := {w_{1}w_{2} | w_{i} ∈ L}

• Potenzen einer Sprache:

L^{0} := {ϵ} (weil {ϵ}L = L)

L^{n+1} := LL^{n}

• Stern einer Sprache (Iteration / Repitition) (unendliche Sprache)

L^{∗} := ⋃_{n∈ℕ} L^{n} (incl. ϵ)

L^{+} := LL^{∗} = ⋃_{n=1}^{∞} (excl.ϵ)

• Spiegelbild einer Sprache L^{R} := {w^{R} | w ∈ L}

• reguläre Operationen L_{1} ∪ L_{2}, L_{1}L_{2}, L^{∗}

Reguläre Sprachen

2.1 Reguläre Ausdrücke

endliche Beschreibungen unendlicher Sprachen wesentliches Hilfsmittel: Stern * \underline{Definition} Syntax Sei Σ ein Alphabet. Die Menge RA(Σ) der regulären Ausdrücke über Σ ist induktiv definiert durch:

1. Λ ∈ RA(Σ)

2. a ∈ RA(Σ) für jedes a ∈ Σ

3. (α ∨ β) ∈ RA(Σ) falls α, β ∈ RA(Σ)

4. (α · β) ∈ RA(Σ) falls α, β ∈ RA(Σ)

5. (α^{∗}) ∈ RA(Σ) falls α ∈ RA(Σ) Vereinfachte Schreibweisen

• Präzedenzregeln, um Klammern zu sparen – ∗ bindet stärker als ·

– · bindet stärker als ∨

• Das · wird unterdrückt Beachte: RA(Σ) ist selbst eine formale Sprache:

RA(Σ) ⊆ (Σ ∪ {Λ, (,), ·, ∨, ∗})^{∗} \underline{Definition} Semantik Ein regulärer Ausdruck beschreibt eine formale Sprache über Σ: [[ ]] : RA(Σ) → p(Σ^{∗})

• [[Λ]] := ∅

• [[a]] := {a}

• [[(α ∨ β)]] := [[α]] ∨ [[β]]

• [[α · β]] := [[α]][[β]] (Komplexprodukt)

• [[α^{∗}]] := [[α]]^{∗} Die so beschreibbaren Sprachen heißen regulär. \underline{Definition} Die Klasse REG(Σ) der regulären Sprachen über Σ ist induktiv definiert durch:

• ∅, {a} ∈ REG(Σ) ∀ a ∈ Σ

• L, L′ ∈ REG(Σ) ↷ L ∪ L′, LL′, L^{∗} ∈ REG(Σ) Anwendungen:

• Dateiauswahl: ls *.ps

• Textsuche: egrep -E ’Gr(ae—ä)del’ publications.txt

• Suchmaschine: and, not

• Symbolklassen Fließkomma in C – ExpPart [eE][-+]?[0-9]+

– FractConst ([0-9]*”·”[0-9]+)—([0-9]+”·)

• WHILE-Programme : formale Pfadsprachen Die Menge WP der WHILE_{0}-Programme (Prof. Thomas) ist induktiv aufgebaut über den Mengen A := {X_{i} := X_{i} + 1, X_{i} := X_{i} − 1 | i ∈ ℕ} und B := {X_{i} > 0 | i ∈ ℕ} durch:

1. A ⊆ W P

2. P, Q ∈ W P ↷ \underline{begin} P; Q \underline{end} ∈ W P

3. b ∈ B, P, Q ∈ W P ↷ \underline{if} b \underline{then} P \underline{else} Q ∈ W P

4. b ∈ B, P ∈ W P ↷ \underline{while} b \underline{do} P ∈ W P Sei Σ_{P AT H} := A ∪ (B × {true, false})

b_{false} := (b, false)

b_{true} := (b, true)

Für P ∈ W P definieren wir die formale Pfadsprache L_{p} ⊆ (Σ_{P AT H}^{∗})

1. L_{a} := {a} für a ∈ A

2. L_{\underline{begin} P; Q \underline{end}} := L_{P} L_{Q}

3. L_{\underline{if} b \underline{then} P \underline{else} Q;} := \{b_{true}\}L_{P} ∪ \{b_{false}\}L_{Q}

4. L_{\underline{while} b \underline{do} P} := (\{b_{true}\}L_{P})^{∗}\{b_{false}\} es folgt: Beschreibung von L_{P} durch α_{P} ∈ RA(Σ_{P AT H}), nämlich:

1. α_{a} := a

2. α_{\underline{begin} P; Q \underline{end}} := α_{P} α_{Q}

3. α_{\underline{if} b \underline{then} P \underline{else} Q;} := b_{true}α_{P} ∨ b_{false}α_{Q}

4. α_{\underline{while} b \underline{do} P} := (b_{true}α_{P})^{∗}b_{false} \underline{Beachte:} Analogie zwischen WP und RA(Σ_{P AT H}) Jedoch: Abstraktion von Anweisungs- und Bedingungssemantik

\underline{Definition} P ∼_{P AT H} Q : ↷ ↶ L_{P} = L_{Q}

\underline{Folgerung:} P ∼_{P AT H} Q :↷ P ∼ Q (d.h. f_{P} = f_{Q})

↓ ↓

entscheidbar durch endl. unentscheidbar Automaten

α ↦ [[α]] ⊆ Σ^{∗} L(α) := [[α]] L(Σ, RA) = REG(Σ)

Standardprobleme für RA(Σ):

• Wortproblem (matching Problem) Gilt w ∈ [[α]] für w ∈ Σ^{∗} und α ∈ RA(Σ)

• Äquivalenzproblem Gilt [[α]] = [[β]] für α, β ∈ RA(Σ)

• Leerheitsproblem

Gilt [[α]] = ∅ für α ∈ RA(Σ) Alle Probleme sind mit endlichen Automaten entscheidbar.

2.2 Deterministische endliche Automaten (DFA)

\underline{Definition}: Seien Q und Σ nicht-leere, endliche Mengen.

q_{0} ∈ Q, F ⊆ Q und δ : Q × Σ → Q Dann heißt 𝔄 =< Q, Σ, δ, q_{0}, F > ein deterministischer endlicher Automat über Σ mit der Zustandsmenge Q

dem Eingabealphabet Σ der Transitionsfunktion δ dem Anfangszustand q_{0}

und der Endzustandsmenge F Darstellung von 𝔄 durch Transitionstafel und Zustandgraphen.

\underline{Definition}: 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DF A(Σ) bestimmt die erweiterte Transitionsfunktion \overline{δ} : Q × Σ^{∗} → Q mit

\overline{δ}(q, ϵ) := q

\overline{δ}(q, wa) := δ(\overline{δ}(q, w), a)

(* oder: \overline{δ}(q, aw) := \overline{δ}(δ(q, a), w) *) und damit die von 𝔄 erkannte Sprache: L(𝔄) := \{w ∈ Σ^{∗} | \overline{δ}(q_{0}, w) ∈ F \}

Ziel: L(Σ, DF A) = REG(Σ) Hilfsmittel: nicht deterministische Automaten!

2.3 Nicht deterministische endliche Automaten (NFA)

\underline{Def.} Seien Q, Σ, q_{0}, F wie bei einem 𝔄 ∈ DF A ferner Σ_{ϵ} := Σ ∪ ϵ und δ : Q ∪ Σ_{ϵ} → p(Q)

Dann heißt 𝔄 =< Q, Σ, δ, q_{0}, F > ein nicht deterministischer endl. Automat über Σ

Es folgt: DF A(Σ) ⊆ NF A(Σ) (Hinweis: Worttransitionen sind durch Zwischenzustände simulierbar)

\underline{Semantik} eines Automaten 𝔄 ∈ NF A(Σ): Menge der Konfigurationen von 𝔄 : Q × Σ^{∗} Transitionen: ∀ q, q′ ∈ Q, w ∈ Σ^{∗}, a ∈ Σ definieren wir:

1. Σ-Transitionen: (q, aw) ⊢ (q′, w) ↷ ↶ q′ ∈ δ(q, a)

2. ϵ-Transitionen: (q, w) ⊢ (q′, w) ↷ ↶ q′ ∈ δ(q, ϵ)

Dann ist die durch 𝔄 erkannte Sprache definiert als: L(𝔄) := {w ∈ Σ^{∗}|(q_{0}, w) ⊢^{∗} (q, ϵ) mit q ∈ F } \underline{Ziel:} α ∈ RA(Σ) ↦ 𝔄(α) ∈ NF A(Σ) ↦ 𝔄(α)_{P} ∈ DF A(Σ) mit [[α]] = L(𝔄(α)) = L(𝔄(α)_{P})

\underline{Definition}: Sei 𝔄 ∈ NF A(Σ). Der Potenzmengenautomat 𝔄_{P} := < Q_{P} , Σ, δ_{P} , q_{0_{P}} , F_{P} > ∈ DF A ist definiert durch:

• Q_{P} := {T ⊆ Q | ∃w ∈ Σ^{∗} : T = {q ∈ Q | (q_{0}, w) ⊢^{∗} (q, ϵ)} (Zustände von 𝔄_{P})}

• q_{0_{P}} := {q ∈ Q | (q_{0}, ϵ) ⊢^{∗} (q, ϵ}

• F_{p} := {T ∈ Q_{P} | T ∩ F ≠ ∅}

• δ_{P} : Q_{P} × Σ → Q_{P}

• δ_{P} (T, a) := {q′ ∈ Q | (q, a) ⊢^{∗} (q′, ϵ) für ein q ∈ T } \underline{Beachte}:

T ⊆ Q_{P} ↷ ∃w ∈ Σ^{∗} : T = {q′ ∈ Q | (q_{0}, w) ⊢^{∗} (q′, ϵ)} ↷ δ_{P} (T, a) = {q′ ∈ Q | (q_{0}, wa) ⊢^{∗} (q′, ϵ)} ∈ Q_{P}

\underline{Lemma:} Sei 𝔄 ∈ NF A(Σ). Dann gilt: L(𝔄) = L(𝔄_{P})

\underline{Beweis:} Zunächst zeigen wir, daß für alle w ∈ Σ^{∗} und q ∈ Q gilt:

\underbrace{q ∈ \overline{δ}_{P} (q_{0_{P}} , w)}_{DF A} ↷ ↶ \underbrace{(q_{0}, w) ⊢^{∗} (q, ϵ)}_{NF A} (q liegt im Folgezustand des neuen PM-Automaten)

Induktion:

(i) \underline{w = ϵ}:

q ∈ \overline{δ}(q_{0_{P}} , ϵ) ↷ ↶ q ∈ q_{0_{P}} ↷ ↶ (q_{0}, ϵ) ⊢^{∗} (q, ϵ)

(ii) \underline{w = w′a}:

q ∈ \overline{δ}_{P} , w′a) = δ_{P} (q_{0_{P}} , w′), a) ↷ ↶ ∃ q′ ∈ \overline{δ}_{P} (q_{0_{P}} , w′) : (q′, a) ⊢ (q, ϵ) ↷ ↶ ∃ q′ ∈ Q : (q_{0}, w′a) ⊢^{∗} (q′, a) ⊢^{∗} (q, ϵ) ↷ ↶ (q_{0}, w′a) ⊢^{∗} (q, ϵ)

Daraus folgt die Behaupung: w ∈ L(𝔄) ↷ ↶ ∃ q ∈ F : (q_{0}, w) ⊢^{∗} (q, ϵ)

↷ ↶ q ∈ \overline{δ}_{P} (q_{0P} , w) und q ∈ F

↷ ↶ \overline{δ}_{P} (q_{0P} , w) ∈ F  ↷ ↶ w ∈ L(𝔄_{P})  ♢

2.4 Synthese und Analyse endlicher Automaten

\underline{Synthese:} Konstruiere für δ ∈ RA(Σ) einen äquivalenten 𝔄(δ) ∈ NF A, d.h. [[δ]] = L(𝔄(δ))

Der Algorithmus von Thompson Idee: 𝔄(δ) hat genau einen Endzustand q_{f}, q_{0} ist Quelle, q_{f} ist Senke (im Zustandsgraphen)

[figure: q_{0}; q_{f}]
- 𝔄(Λ)  :=  [figure: q_{0}; q_{f}]

- 𝔄(a), a ∈ Σ := [figure: q_{0}; q_{f}; a]

- 𝔄(α ∨ β) := [figure: ϵ; ϵ; 𝔄(α); 𝔄(β); ϵ; ϵ]

- 𝔄(αβ) := [figure: 𝔄(α); 𝔄(β)]

- 𝔄(α^{∗}) := [figure: 𝔄(α); ϵ; ϵ; ϵ; ϵ]

Offensichtlich gilt für jedes α ∈ RA(Σ) : [[α]] = L(𝔄(α))

\underline{Korollar:} REG(Σ) ⊆ L(Σ, DF A)

\underline{Analyse:} Konstruiere für 𝔄 ∈ DF A(Σ) einen α(𝔄) ∈ RA(Σ) mit [[α(𝔄)]] = L(𝔄) 𝔄 =< Q, Σ, δ, q_{1}, F >∈ DF A(Σ) und Q = {q_{1}, ..., q_{n}} Für i, j ∈ {1, ..., n} und k ∈ {0, 1, ..., n} definieren wir W_{ij}^{k} := {w ∈ Σ^{∗}| w überführt q_{i} in q_{j} ohne Benutzung von q_{k+1}, ..., q_{n} als Zwischenzustände}.

Dann gilt:

L(𝔄) = ⋃_{q_{j}∈F} W_{1j}^{n}

Somit genügt der Nachweis der Regularität der Sprachen W_{ij}^{k}

Induktion über k:

i) k=0: W_{ij}^{0} ⊆ Σ_{ϵ} ist regulär ({ϵ} = [[Λ^{∗}]]) ii) k-1→k : W_{ij}^{k} = W_{ij}^{k−1} ∪ W_{ik}^{k−1}(W_{kk}^{k−1})^{∗}W_{kj}^{k−1}

\underline{Korollar:} (Satz von Kleene) L(Σ, DF A) = REG(Σ)

\underline{Korollar:} REG(Σ) ist auch abgeschlossen unter ∩,

Beweisidee: a) Komplement: F′ := Q \ F b) L_{1} ∩ L_{2} = \overline{L}_{1} ∪ \overline{L}_{2}

2.5 Das Pumping - Lemma

Hilfsmittel zum Nachweis nicht-regulärer Sprachen \underline{Satz:} (Pumping-Lemma, Iterationslemma) Sei L ∈ REG(Σ), Dann ∃ k ∈ ℕ, so daß für jedes x ∈ L mit |x| ≥ k eine Zerlegung x = uvw mit folgenden Eigenschaften existiert:

1. |v| ≥ 1

2. |uv| ≤ k

3. |uv^{i}w| ∈ L für alle i ∈ ℕ, insbesondere für i = 0

\underline{Beweis:} Sei 𝔄 ∈ DF A(Σ) mit L(𝔄) = L und k = |Q|. Sei x ∈ L mit |x| ≥ k Erkennung von x in 𝔄:

[figure: ...; u; v; w; q_{0}; q_{w}; q_{w}; x]

Im 1. Abschnitt wurde u erkannt Im 2. Abschnitt wurde v erkannt Im 3. Abschnitt wurde w erkannt

Seien [figure: q_{w}; q_{w}] das erste Wiederholungspaar von Zuständen, so folgen die Eigenschaften 1 - 3 ♢ \underline{Beachte:} Das Pumping-Lemma beschreibt eine notwendige, aber nicht eine hinreichende Eigenschaft regulärer Sprachen, daher ist es geeignet zum Nachweis nicht-regulärer Sprachen.

\underline{Beispiel:} L = \{a^{n}b^{n}|n ≥ 1\} ∉ REG(\{a, b\})

\underline{Beweis:} Angenommen, L ∈ REG(Σ). Dann ∃ k ∈ ℕ mit den Eigenschaften des Pumping-Lemmas, “Pumping-Index” Für x = a^{k}b^{k} muß dann eine Zerlegung existieren a^{k}b^{k} = uvw mit v ≠ ∅ und |uv| ≤ k, also

v ∈ {a^{i} | i > 0} und uw = a^{k−|v|}b^{k} ∈ L  Widerspruch!  ♢

2.6 Zustandsreduktion endlicher Automaten

\underline{Ziel:} Konstruktion endlicher Automaten mit minimaler Zustandsanzahl

\underline{Definition}: Für L ⊆ Σ^{∗} und w ∈ Σ^{∗} heißt d_{w}(L) (d_{w}(L) ist das, was auf w in L folgt)

d_{w}(L) := {v ∈ Σ^{∗} | wv ∈ L} die Ableitung von L nach w

\underline{Lemma:} Sei L = L(𝔄) für 𝔄 =< Q, Σ, δ, q, F >∈ DF A(Σ).

Dann gilt für D(L) = {d_{w}(L) | w ∈ Σ^{∗}} |D(L)| ≤ |Q| (D(L) ist Menge aller Ableitungen)

\underline{Beweis:} Für q ∈ Q bezeichne L(q) := L(< Q, Σ, δ, q, F >). Dann gilt:

d_{w}(L) = d_{w}(L(q_{0})) = L(\overline{δ}(q_{0}, w)) ♢

\underline{Definition}: Der Ableitungsautomat 𝔄_{L} := < D(L), Σ, δ, q_{0}, F > ∈ DF A(Σ) ist für L ∈ REG(Σ) definiert durch:

• q_{0} := d_{ϵ}(L) = L

• F := {d_{w}(L) | w ∈ L} (d.h. ϵ ∈ d_{w}(L))

• δ(d_{w}(L), a) := d_{wa}(L) (Instanz von δ(q, a) = q′)

\underline{Beachte:} d_{w}(L) = d_{v}(L) ↷ d_{wa}(L) = d_{va}(L)

\underline{Lemma:} L(𝔄_{L}) = L

\underline{Beweis:}

w ∈ L(𝔄_{L}) : ↷ ↶ \overline{δ}(q_{0}, w) ∈ F ↷ ↶ d_{w}(L) ∈ F ↷ ↶ w ∈ L ♢

\underline{Korollar:} 1. Der Ableitungsautomat ist zustandsminimal

2. Für L ⊆ Σ^{∗} gilt: L ∈ REG ↷ ↶ |D(L)| < ∞

Zustandsreduktion Konstruktion einses zustandsminimalen Automaten aus einem gegebenen Automaten durch:

• Weglassen nicht erreichbarer Zustände

• Verschmelzen äquivalenter Zustände Dann heißt:

• q ∈ Q erreichbar : ↷ ↶ ∃w ∈ Σ^{∗} : \overline{δ}(q_{0}, w) = q

• q_{1} ∼ q_{2} (äquivalent) : ↷ ↶ L(q_{1}) = L(q_{2})

Wenn die Menge der Beschriftungen gleichist , dann ist auch die Menge der Zustände gleich

\underline{Definition}: Für 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DF A(Σ) ist der Faktorautomat (Teilklassenbildung) 𝔄/ ∼ := < Q̃, Σ, δ̃, q̃_{0}, F̃ >∈ DF A(Σ) wie folgt definiert: Für q ∈ Q sei [q] := {q′ | q ∼ q′}

• Q̃ := \{[\overline{δ}(q_{0}, w)] | w ∈ Σ^{∗}\}

• q̃_{0} := [q_{0}]

• F̃ := \{[q] | q ∈ F \} \overline{δ}(q, ϵ) := q • δ̃([q], a) := [δ(q, a)]

\underline{Beachte:} q ∼ q′ ↷ L(q) = L(q′) ↷ δ(q, a) ∼ δ(q′, a)

\underline{Lemma:} Für \underline{𝔄} ∈ DF A(Σ) gilt (bis auf Zustandsnamen) :

𝔄/ ∼ ≅ 𝔄_{L(\underline{𝔄})}

Insbesondere ist 𝔄/ ∼ äquivalent zu 𝔄, und es folgt: Zustandsminimale Automaten sind bis auf Isomorphie eindeutig bestimmt.

\underline{Beweis:} Sei β : Q̃ → D(L(𝔄)) definiert durch β([\overline{δ}(q_{0}, w)]) := d_{w}(L(𝔄)) β ist unabhängig vom Repräsentanten w ∈ Σ^{∗} :

\overline{δ}(q_{0}, v) ∼ \overline{δ}(q_{0}, w) ↷ L(\overline{δ}(q_{0}, v)) = L(\overline{δ}(q_{0}, w) ↷ d_{w}(L(𝔄)) = d_{v}(L(𝔄))

• β ist bijektiv, weil die obige Folgerung umkehrbar ist.

• β ist strukturerhaltend:

– β([q_{0}]) = β([\overline{δ}(q_{0}, ϵ)]) = d_{ϵ}(L(𝔄))

Anfangszustand des Ableitungsautomaten – \overline{δ}(q_{0}, w) = q ∈ F : β([\overline{δ}(q_{0}, w)]) = d_{w}(L(𝔄)) Endzustand des Ableitungsautomaten

– δ̃([q], a)  = [δ(q, a)]

↷ δ̃([\overline{δ}(q_{0}, w)], a) = [\overline{δ}(q_{0}, wa)]
↷ δ(d_{w}(L(𝔄)), a) = d_{wa}(L(𝔄))
♢

Verfahren zur Zustandsminimierung:

• Weglassen nicht erreichbarer Zustände

• Verschmelzen äquivalenter Zustände

\underline{Definition}: Sei 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DF A und jeder Zustand erreichbar; ferner k ∈ ℕ, q_{1}, q_{2} ∈ Q. Dann sagt man:

• q_{1} k-äquivalent q_{2} (q_{1} ∼^{k} q_{2}): ↷ ↶ ∀w ∈ Σ^{∗}, |w| ≤ k : w ∈ L(q_{1}) ↷ ↶ w ∈ L(q_{2})

• 𝔄 induziert die Abbildungen R^{k} : Q^{k} → {0, 1} mit r^{k}(q_{1}, q_{2}) = 1 : ↷ ↶ q_{1} ∼^{k} q_{2}

Diese können als Matrizen R^{k} = (r^{k}(q_{i}, q_{j}))_{i,j=1}^{n} mit n = |Q| dargestellt werden. \underline{Beachte:} r^{k}(q_{i}, q_{j}) = r^{k}(q_{j}, q_{i})

Berechnung der k-Äquivalenzen

• q_{1} ∼^{0} q_{2} ↷ ↶ (q_{1} ∈ F ↷ ↶ q_{2} ∈ F)

• q_{1} ∼^{k+1} q_{2} ↷ ↶ q_{0} ∼^{0} q_{2} und δ(q_{1}, a) ∼^{k} δ(q_{2}, a)∀a ∈ Σ

\underline{Lemma:} Es gibt ein k ∈ ℕ, so daß für alle n ∈ ℕ: R^{k} = R^{k+n}

\underline{Beweis:} Da r^{k}(q_{i}, q_{j}) = 0 ↷ r^{k+1}(q_{i}, q_{j}) = 0 muß es ein k geben mit r^{k} = r^{k+1}. Dann muß auch r^{k} = r^{k+n}∀n ∈ ℕ:

Sei r^{k}(q_{1}, q_{2}) = r^{k+1}(q_{1}, q_{2}) = 1, also q_{1} ∼^{k} q_{2} und q_{2} ∼^{k+1} q_{2}.

Sei ferner a_{1}, ..., a_{k+2} ∈ L(q_{1})

δ(q_{1}, a_{1}) ∼^{k} δ(q_{2}, a_{1}), also auch δ(q_{1}, a_{1}) ∼^{k+1} δ(q_{2}, a_{1})

Somit a_{2}, ..., a_{k+2} ∈ L(δ(q_{2}, a_{1})) und a_{1}, ..., a_{k+2} ∈ L(q_{2}) Wegen Symmetrie folgt q_{1} ∼^{k+2} q_{2} ♢ Markierungsalgorithmus

Eingabe: 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DF A Jedes q ∈ Q ist erreichbar. Ausgabe: Äquivalente Zustände

Verfahren:

• Tabelle aller Zustandspaare {q, q′} mit q ≠ q′

• Markiere alle Paare {q, q′} mit q ∈ F und q′ ∉ F oder umgekehrt

• Für jedes unmarkierte Paar {q, q′} und Eingabesymbol a ∈ Σ, teste ob {δ(q, a), δ(q′, a)} markiert. Wenn ja, markiere {q, q′}.

• Wiederhole letzten Schritt, bis keine Änderung mehr erfolgt.

• Unmarkierte Paare repräsentieren äquivalente Zustände.

\underline{Bemerkung:} Implementierung mit O(|Q|^{2}) Zeitkomplexität möglich.

2.7 Entscheidbare Eigenschaften

2.7.1 Deterministische endliche Automaten (DFA)

• \underline{Wortproblem:} w ∈ L(𝔄)? für w ∈ Σ^{∗} und 𝔄 ∈ DF A(Σ)

Durch Eingabe in |w| + 1 Schritten entscheidbar.

• \underline{∅-Problem:} L(𝔄) = ∅? für 𝔄 ∈ DF A(Σ)

Durch Eingabe aller Werte w mit |w| < |Q| entscheidbar. \underline{Beachte:} w ∈ L(𝔄), |w| ≥ |Q| ↷ ∃v ∈ L(𝔄), |v| < |w| Verfahren: testen, ob F von q_{0} erreichbar ist. Durchführung in O(|Q|^{2})-Zeit. Bei geschickter Implementierung der Mengenoperationen auch besser.

• \underline{∼-Problem:} L(𝔄) = L, (𝔄′)? für 𝔄𝔄′ ∈ DF A(Σ)

Reduktion auf das ∅-Problem: L(𝔄) = L(𝔄′) ↷ ↶ L(𝔄) ⊆ L(𝔄′) und L(𝔄′) ⊆ L(𝔄)

↷ ↶ \underbrace{L(𝔄) ∩ \overline{L(𝔄′)}}_{𝔄_{1}} und \underbrace{L(𝔄′) ∩ \overline{L(𝔄)}}_{𝔄_{2}} = ∅

(Komplementautomat ≡ Komplement der Endzustände) 2 Produktautomaten mit |Q||Q′| Zuständen auf ∅ testen. ∼-Problem ist in O(|Q|^{2}|Q|^{2}) lösbar.

2.7.2 Reguläre Ausdrücke, nicht-deterministische Automaten (NFA)

Durch Transformationen in DFA’s sind alle drei Probleme entscheidbar. Aber der Aufwand steigt:

• \underline{Wortproblem:} O(|α||w|)-Zeit bzw. O(|α||w|)-Platz

• \underline{∅-Problem:} NFA wie DFA behandeln. RA ↦ NF A in O(|α|)-Zeit mit |Q| ≤ 2(α)

• \underline{∼-Problem:} NP-hart (Problem ∈ NP ⇒ P ≤_{p}, ∼-Problem)

2.8 endliche Automaten mit Ausgabe

\underline{Idee:} Bei Zustandsübergängen erfolgt sequentielle Ausgabe

\underline{Definition}: Sei < Q, Σ, δ, q_{0}, F >∈ DF A, Δ ein Ausgabealphabet (nicht-leere, endliche Menge) und λ : Q × Σ → Δ eine Ausgabefunktion. Dann heißt 𝔄 =< Q, Σ, δ, q_{,}λ > ein Mealy-Automat 𝔄 berechnet die sequentielle Transformation f_{𝔄} : Σ^{∗} ⟶ Δ^{∗} Bsp: f(aab) = bcc mit f_{𝔄}(ϵ) := ϵ und f_{𝔄}(wa) := f_{𝔄}(w) · λ(\overline{δ}(q_{0}, w), a) [figure: q_{0}; q_{1}; q_{2}; q_{3}; (a, b); (a, c); (b, c)]

2.9 Automaten als abstrakte Programme

2.9.1 GOTO-Programme

GOTO-Programme sind aufgebaut über den Mengen

A := {X_{i} := X_{i} + 1, X_{i} := X_{i} − 1 | i ∈ ℕ} (Anweisungen) und B := {X_{i} = 0 | i ∈ ℕ} (Bedingungen) nämlich als Zeichenreihen der Form 1 : α_{1}; 2 : α_{2}; ...; k : α_{k} mit α_{i} ∈ A ∪ \{\underline{if} b \underline{then} j_{0} \underline{else} j_{1} | b ∈ B, 1 ≤ j_{0}, j_{1} ≤ k\} und α_{k} = STOP Sei Σ_{P AT H} := A ∪ (B × {true, false}). Für ein GOTO-Programm P = 1 : α_{1}, ..., k : ST OP definieren wir ein 𝔄_{P} =< Q, Σ_{P AT H}, δ, q_{0}, F > ∈ DF A(Σ)

• Q = {1, ..., k, 0}

• q_{0} = 1

• F = {k}

• δ(i, a) = i + 1 falls i : a in P; a ∈ A

\begin{matrix}δ(i, b_{true}) = j_{0} \\ δ(i, b_{false}) = j_{1} \end{matrix} \} falls i : \underline{if} b \underline{then} j_{0} \underline{else} j_{1}

δ(i, c) = 0 sonst \underline{Definition}: L_{P} := L(𝔄_{P}) heißt \underline{\underline{formale} Pfadsprache von P}

P ∼_{P AT H} Q : ↷ ↶ L_{P} = L_{Q}

\underline{Lemma:} P ∼_{P AT H} Q ↷ P ∼ Q (aber nicht umgekehrt)

entscheidbar unentscheidbar

2.9.2 Parallele Programme, Verteilte Systeme

Reduktion von Parallelität auf Nichtdeterminismus. Für Aktionen a und b wird a ∥ b := ab ∨ ba [figure: b; a; b; a] NFA zur Modellierung verteilter Systeme \underline{Beispiel:} Deadlocks als Senkzustände Bsp. MS-Windows 18 KAPITEL 2. REGULÄRE SPRACHEN

Kontextfreie Grammatiken und Kellerautomaten

3.1 Kontextfreie Grammatiken

\underline{Definition:} Seien N und Σ nicht-leere endliche Mengen mit N ∩ Σ = ∅. Sei P ⊆ N × (N ∪ Σ)^{∗} mit |P | < ∞ und S ∈ N Dann heißt G =< Q, Σ, P, S > eine kontextfreie Grammatik. Bezeichnung: G ∈ CF G(Σ)

Bezeichnungen und Konventionen

A, B, C, ... ∈ N Nichtterminalsymbole a, b, c, ... ∈ Σ Terminalsymbole S ∈ N Startsymbol X, Y, Z, ... ∈ X := N ∪ Σ (Symbole der Grammatik) α, β, γ, ... ∈ X^{∗} Satzformen u, v, w, ... ∈ Σ^{∗} Terminalwörter A → α := (A, α) ∈ P Regel, Produktion

\underline{Definition:} Sei G =< N, Σ, P, S >∈ CFG und π = A → α ∈ P.

π bestimmt eine Ableitungsrelation: ⇒_{π} ⊆ X^{∗} × X^{∗} mit β_{1} ⇒_{π} β_{2} ↷ ↶ es existiert ein Kontext γ_{1}, γ_{2} ∈ X^{∗}, so daß β_{1} = γ_{1} A γ_{2} und β_{2} = γ_{1} α γ_{2} Dann heißt das Tripel (γ_{1}, π, γ_{2}) auch Ableitungsschritt G bestimmt die Ableitungsrelation ⇒_{G} ⊆ X^{∗} × X^{∗} durch

⇒_{G} := ⋃_{π∈P} ⇒_{π}

und damit die von G erzeugte Sprache L(G) := {w ∈ Σ^{∗} | S ⇒^{∗}_{G} w}

⇒^{∗}_{G} := ⋃_{n=0}^{∞} ⇒^{n}_{G} (reflexive und transitive Hülle)

Es folgt: w ∈ L(G) ↷ ↶ ∃α_{0}, α_{1}, ..., α_{n} ∈ X^{∗}

und π_{1}, ..., π_{n} ∈ P : S = α_{0} ⇒_{π_{1}} α_{1}... ⇒_{π_{n}} α_{n} = w

\underline{Bezeichnung:} CFL(Σ) := \{L ⊆ Σ^{∗} | ∃G ∈ CFG(Σ) : L(G) = L\}

Ableitungsbäume, Rechts- und Linksableitungen, Ein- und Mehrdeutigkeit

Sei G =< N, Σ, P, S >∈ CFG Darstellung von Ableitungen durch Bäume

1. Eine Regel π = A → x_{1}, ...x_{n} bestimmt den Regelbaum [figure: X_{1} ... X_{n}; A] , Spezialfall {A \atop ϵ} für n = 0

2. Eine Ableitung A ⇒ α_{1} ⇒ α_{2} ⇒ ... ⇒ α_{n} bestimmt den Ableitungsbaum durch entsprechendes Verkleben der Regelbäume. Definiert durch Induktion über n ∈ ℕ.

• \underline{n = 1} Regelbaum

• \underline{n → n + 1} A ⇒ α_{1} ⇒ ... ⇒ α_{n} habe den Ableitungsbaum: [figure: X_{1} ... X_{n}; A] α_{n} ⇒ α_{n+1} mit dem Ableitungsschritt π : B → β(u, π, v) Dann entsteht der Ableitungsbaum von A ⇒ α_{1} ⇒ ... ⇒ α_{n+1} durch Anhängen des Regelbaums von π zwischen u und v.

\underline{Folgerung:} Ein Ableitungsbaum repräsentiert eine Klasse von Ableitungen, die sich nur in der Reihenfolge von Ableitungsschritten unterscheiden. Ein Ableitungsbaum repräsentiert die relevante syntaktische Struktur.

\underline{Definition:} Eine Ableitung heißt Rechtsbleitung (Linksableitung), wenn jeder Ableitungsschritt (α, π, β) ein Rechtsableitungsschritt, d.h. β ∈ Σ^{∗} (Linksableitungsschritt, d.h. α ∈ Σ^{∗}) ist. Schreibweise: ⇒_{r} bzw. ⇒_{l}

\underline{Folgerung:} Ein Ableitungsbaum hat genau eine Rechts- und genau eine Linksableitung.

\underline{Definition:}

• G ∈ CFG(Σ) heißt eindeutig :↷ ↶ zu jedem w ∈ L(G) gibt es genau eine Rechtsableitung

S ⇒_{r} α_{1} ⇒_{r} ... ⇒_{r} w

• G heißt mehrdeutig :↷ ↶ nicht eindeutig.

Beispiel für Mehrdeutigkeit: a + b ∗ c

3.2 Einseitig-lineare Grammatiken

\underline{Def.} Sei G =< N, Σ, P, S >∈ CFG.

• Dann heißt G linkslinear, wenn für jedes π = A → α ∈ P gilt: α = Bw oder α = w für ein w ∈ Σ^{∗} und B ∈ N

• Gilt stattdessen α = wB oder α = w für jedes π ∈ P, so heißt G rechtslinear

• G einseitig-linear :↷ ↶ G linkslinear oder G rechtslinear.

\underline{Ziel:} \{L(G) | G linkslinear\} = {L(G) | G rechtslinear}

= {L(G) | G einseitig − linear} = REG(Σ)

\underline{Satz:} L(Σ,NFA) = \{L ⊆ Σ^{∗}|L = L(G), G rechtslinear\}

\underline{Beweis:} 1.) “ ⊇ ” Sei G =< N, Σ, P, S > rechtslinear. Auffassung von G als 𝔄 =< Q, Σ, δ, q_{0}, F >∈ NF A

Q := N ∪ {q_{f}} q_{f} neu

q_{0} := S

F := {q_{f}}

\overline{δ}(A, w) ∋ B, falls A → wB in G existiert.

\overline{δ}(A, w) ∋ q_{f}, falls A → wB in G existiert. Offensichtlich: L(G) = L(𝔄) Wortübergänge durch Zwischenzustände beseitigen. 2.) “ ⊆ ” 𝔄 =< Q, Σ, δ, q_{0}, F >∈ NF A kann ebenso als rechtslineare Grammatik aufgefaßt werden.

♢

\underline{Korollar:} REG(Σ) ⊆ CF L Für |Σ| ≥ 2 ist diese Inklusion echt, weil {a^{n}b^{n} | n ∈ ℕ} = L(G) mit G = (δ → aSb | ϵ)

\underline{Bem.:} |Σ| = 1 ↷ L^{R} ∈ REG(Σ)

\underline{Lemma:} L ∈ REG(Σ) ↷ L^{R} ∈ REG(Σ)

\underline{Beweis}: Zu 𝔄 ∈ DF A(Σ) konstruieren wir 𝔄^{R} ∈ NF A(Σ) mit L(𝔄^{R}) = L(𝔄)^{R} Idee: ersetze [figure: a; durch; a; q; q’; q; q’; durch; q_{0}; q_{0}]

und ergänze diesen NFA durch [figure: q̃_{0}; ϵ; ϵ] für alle q ∈ F ♢

\underline{Korollar}: \{L ⊆ Σ^{∗}|L = L(G), 𝔄 rechtslinear\} = {L ⊆ Σ^{∗}|L = L(G), 𝔄 linkslinear}

\underline{Beweis}: L ist rechtslinear erzeugbar.

↷ ↶ L^{R} ist rechtslinear erzeugbar.

↷ ↶ L = L^{RR} ist linkslinear erzeugbar. ♢

3.3 Normalformen von kontextfreien Grammatiken

\underline{Hilfsmittel:} Vorgänger von Satzformen α ⇒ β α heißt direkter Vorgänger von β α ⇒^{∗} β α Vorgänger von β

\underline{Definition}: Sei G =< N, Σ, P, S >∈ CF G und L ⊂ X^{∗}. Dann ist

1. die direkte Vorgängermenge von L definiert durch: \underline{P re}_{G}(L) := \{α ∈ X^{∗} | ∃β ∈ L : α ⇒_{G} β\}

2. der Vorgängerabschluß von L definiert durch:

\underline{P re}_{G}(L) := \{α ∈ X^{∗} | ∃β ∈ L : α ⇒^{∗}_{G} β\}

\underline{Lemma:} Sei G =< N, Σ, P, S >∈ CF G und L ⊆ X^{∗}. Dann gilt: L ∈ REG(X) ↷ \underline{P re}_{G}(L) ∈ REG(X)

\underline{Beweis}: Sei 𝔄 =< Q, X , δ, q_{0}, F >∈ NF A mit L(𝔄) = L Konstruiere 𝔄′ =< Q, X , δ′, q_{0}, F >∈ NF A durch hinzufügen folgender Transitionen: wenn A → α ∈ P und \overline{δ}(q, α) ∋ q′, so \overline{δ}(q, A) ∋ q′. Ergänze δ um solche Transitionen, solange das möglich ist. Dieser Erweiterungsprozeß terminiert, weil Q und X endlich sind. Die Korrektheit ist offensichtlich. ♢

Beispiel:

[figure: ⟲; ⟲; ⟲; ⟲; S; AS; A,S; A,S; A,S; A,S; b; a; b; G:; S → bSb|A; A → aA|ϵ]

\underline{Definition}: Sei G ∈ CF G(Σ) und A ∈ N

1. A heißt produktiv : ↷ ↶ ∃w ∈ Σ^{∗} : A ⇒^{∗} w

2. A heißt erreichbar : ↷ ↶ ∃α, β ∈ X^{∗} : S ⇒^{∗} αAβ

\underline{Folgerung}: A produktiv ↷ ↶ A ∈ \underline{P re}_{G}(Σ^{∗})

A erreichbar ↷ ↶S ∈ \underline{P re}_{G}(X^{∗}\{A\}X^{∗})

\underline{Definition}: G ∈ CF G(Σ) heißt reduziert :↷ ↶ entweder P = ∅ oder jedes A ∈ N ist produktiv und erreichbar.

\underline{Lemma}: Jedes G ∈ CF G(Σ) läßt sich in ein äquivalentes reduziertes G′ ∈ CF G(Σ) transformieren.

\underline{Beweis}: Stelle für jedes A ∈ N mit Hilfe von NFA fest, ob A erreichbar und produktiv ist.

Fall 1: S nicht produktiv: Wähle P = ∅

Fall 2: S produktiv: Weglassen aller A ∈ N, die nicht produktiv oder nicht erreichbar sind, sowie aller Regeln, in denen solche A’s vorkommen. ♢

\underline{Korollar}: Das Leerheitsproblem von CFG’s ist entscheidbar.

Elimination von ϵ-Regeln

\underline{Definition}: G ∈ CF G(Σ) heißt ϵ-frei :↷ ↶ (A → ϵ ∈ P ↷ A = S und S auf keiner rechten Regelseite)

\underline{Lemma}: X ⇒^{∗} ϵ ↷ ↶ X ∈ \underline{P re}_{G}(\{ϵ\})

\underline{Satz}: Jedes G ∈ CF G(Σ) läßt sich in eine äquivalente ϵ-freie Grammatik G′ ∈ CF G(Σ) transformieren.

\underline{Beweis:} Konstruiere mit \underline{P re}_{G}(\{ϵ\}) die Menge N_{ϵ} := \{A ∈ N|A ⇒^{∗} ϵ\} und damit G′ =< N′, Σ, P′, S′ >∈ CF G :

• N′ := N ∪^{·} {S′}

• P′ := {S′ → S} ∪ {S′ → ϵ|S ∈ N_{ϵ}} ∪{A → X_{1}...X_{k} | k ≥ 1, X_{i} ∈ (N ∪Σ), ∃α_{0}, α_{1}, ..., α_{k} ∈ N_{ϵ}^{∗} : A → α_{0}X_{1}α_{1}...X_{k}α_{k} ∈ P } \underline{Beachte}: Wegen k ≥ 1 entfallen ϵ-Regeln und G′ ist ϵ-frei.

Bleibt zu zeigen: L(G′) = L(G)

1. w = ϵ: ϵ ∈ L(G′) ↷ ↶ S ∈ N_{ϵ} ↷ ↶ S ⇒_{G} ϵ ↷ ↶ ϵ ∈ L(G)

2. w ≠ ϵ:

(a) w ∈ L(G′), d.h. ↷ S ⇒^{∗}_{G′} w ↷ S ⇒^{∗}_{G} w ↷ w ∈ L(G′), weil Ableitung in G′ mit

α_{i} ⇒^{∗} aufgefüllt werden kann zur Ableitung in G

(b) w ∈ L(G)

Wir zeigen mit Induktion über der Ableitungslänge v, daß gilt:

A ⇒^{r}_{G} w ∈ Σ^{+} ↷ A ⇒^{∗}_{G} w

\underline{r = 1 :} A ⇒ w, w ≠ ϵ ↷ A → w ∈ P ↷ A → w inP′ ↷ A ⇒^{∗}_{G′} w

\underline{r → r + 1 :} A ⇒ X_{1}...X_{k} ⇒^{r}_{G} w.

Dann existiert eine Ableitung X_{i} ⇒^{∗}_{G} w_{i} mit w = w_{1}...w_{k}, r_{i} ≤ r

Falls w_{i} ≠ ϵ, X_{i} ⇒^{∗}_{G′} w_{i} nach Ind. Vor.

Falls w_{i} = ϵ, so X_{i} ∈ N_{ϵ}. Durch entsprechendes Löschen entsteht:

A ⇒_{G′} X′_{1}...X′_{k} ⇒^{∗} w′_{1}...w′_{j} = w ♢

Elimination von Kettenregeln

\underline{Def.:} Eine Regel der Form A → B heißt Kettenregel.

\underline{Satz:} Jedes G =< N, Σ, P, S >∈ CF G läßt sich in eine äquivalente ϵ-freie Grammatik G′ ∈< N′, Σ, P′, S >∈ CF G ohne Kettenregeln transformieren.

\underline{Beweis:} O.B.d.A. Sei G ϵ-frei. Wir definieren G′ =< N, Σ, P′, S > durch: A → α ∈ P′ :↷ ↶ α ∉ N und es gibt B ∈ N mit A ∈ \underline{P re}^{∗}(B) und B → α ∈ P ♢

3.3.1 Die Chomsky-Normalform

\underline{Definition}: G =< N, Σ, P, S >∈ CF G ist in Chomsky-Normalform (G ∈ CNF : gdw Jede Regel von P hat die Form:

• A → BC mit B, C ∈ N oder

• A → a mit a ∈ Σ oder

• S → ϵ und S auf keiner rechten Regelseite.

\underline{Satz}: Jedes G =< N, Σ, P, S >∈ CF G läßt sich in eine äquivalente Grammatik G′ ∈ CNF transformieren.

\underline{Beweis}: O.B.d.A sei G ϵ-frei und ohne Kettenregeln. Außerdem können wir annehmen, daß für k ≥ 2 A → X_{1}...X_{k} ∈ P ↷ X_{i} ∈ N. Denn X_{i} = a kann ersetzt werden durch ein neues C_{i} ∈ N unter Hinzufügen von C_{i} → a. Bleibt die Elimination von Regeln der Form A → B_{1}...B_{k} mit k ≥ 3 Ersetzen durch: A → B_{1}C_{1}

C_{1} → B_{2}C_{2}

C_{k−2} → B_{k−1}B_{k}

mit neuen N-Symbolen C_{1}, ..., C_{k−2} ♢

3.3.2 Die Greibach-Normalform, Linksrekursion

\underline{Definition}: G =< N, Σ, P, S >∈ CF G ist in Greibach-Normalform (G ∈ GNF) :↷ ↶Jede Regel von P hat die Form:

• A → aB_{1}...B_{n} oder

• A → a oder

• S → ϵ und S auf keiner rechten Regelseite.

\underline{Bemerkung} G rechtslinear (A → wB, A → w) läßt sich offensichtlich in GNF äquivalent transformieren

\underline{Satz:} Jedes G ∈ CF G läßt sich in ein äquivalentes G′ ∈ GNF transformieren.

\underline{Beweisidee:} Elimination linksrekursiver N-Symbole. \underline{Definition}: A ∈ N linksrekursiv :↷ ↶ A ⇒^{+} Aα für ein α ∈ X^{∗}.

\underline{Spezialfall:} Direkte Linksrekursion. Seien A → Aα_{1} | Aα_{2} | ... | Aα_{r} alle Regeln der Form A → Aα

A → β_{1} | ... | β_{s} Transformation:

[figure: A; A; α_{3}; A; α_{1}; β; wird simuliert durch; A; β; Z; α_{1}; Z; α_{3}]

Neuer Regelsatz: A → β_{1}Z | ... | β_{s}Z | β_{1} | ... | β_{s} Z → α_{1}Z | ... | α_{r}Z | α_{1} | ... | α_{r}

3.4 Abschlußeigenschaften von CFL, Pumping-Lemma

\underline{Hilfsmittel}: Substitutionssatz, Pumping-Lemma \underline{Definition} Sei Σ ein Alphabet und für jedes a ∈ Σ Σ_{a} ein weiteres Alphabet. Dann heißt

γ : p(Σ^{∗}) → p(( ⋃_{a∈Σ} Σ_{a})^{∗})

eine Substitutionsabbildung, falls:

• ϕ({a}) ⊆ Σ_{a}^{∗}

• ϕ({ϵ}) = {ϵ}

• ϕ({a_{1}...a_{r}}) = ϕ({a_{1}}) · ϕ({a_{2}}) · ... · ϕ({a_{r}})

•

ϕ(L) = ⋃_{w∈L} ϕ({w})

\underline{Substitutionssatz:} Sei

ϕ : p(Σ^{∗}) → p(( ⋃_{a∈Σ} Σ_{a})^{∗})

eine Substitutionsabbildung. Dann gilt:

L ∈ CF L(Σ), ϕ(a) ∈ CF L(Σ_{a})∀a ∈ Σ ↷ ϕ(L) ∈ CF L( ⋃_{a∈Σ} Σ_{a})

\underline{Beweis}: Kombination kontextfreier Grammatiken mit disjunkten N-Symbol-Mengen. Ersetze a ∈ Σ durch S_{a}:

[figure: S; S_{a}; S_{b}; S_{c}; w_{1}; w_{2}; w_{3}] ♢

\underline{Korollar:} CF L(Σ) ist unter regulären Operationen abgeschlossen. \underline{Beweis:} Seien L_{1}, L_{2} ∈ CF L(Σ) und a, b Buchstaben mit ϕ(a) = L_{1} und ϕ(b) = L_{2}. Dann gilt:

• ϕ({a, b}) = L_{1} ∪ L_{2}

• ϕ(ab) = L_{1}L_{2}

• ϕ({a}^{∗}) = L_{1}^{∗} Da {a, b}, {a, b}, {a}^{∗} ∈ CF L({a, b}), folgt die Behauptung. ♢ \underline{Das Pumping-Lemma} (uvwxy-Theorem) Für den fehlenden Abschluß unter ∩ und ^{−} betrachten wir das Pumping-Lemma, (uvwxy-Theorem). Sei L ⊆ CF L(Σ). Dann existiert k ≥ 1, so daß für alle z ∈ L mit |z| ≥ k gilt: Es existiert eine Zerlegung z = uvwxy mit

• |vwx| ≤ k,

• vx ≠ ϵ und

• uv^{i}wx^{i}y ∈ L ∀i ∈ ℕ.

\underline{Beweis:} O.B.d.A. sei G =< N, Σ, P, S >∈ CNF mit L(G) = L\\{ϵ\}. Sei n := |N|, k := 2^{n} und

z ∈ L mit |z| ≥ k. Ein Ableitungsbaum t = [figure: S; z] hat mindestens 2^{n} Blätter. Da G ∈ CNF muß ein Pfad p maximaler Länge mindestens n + 1 Kanten, also n + 2 Knoten besitzen. p Besitzt daher mindestens n + 1 Knoten mit N-Symbolen. Also gibt es zwei Knoten mit gleichen N-Symbolen. Wähle auf p den letzten Knoten, dessen Marke A ∈ N sich wiederholt. Dann hat sein Teilbaum höchstens 2^{n} = k Blätter.

• |uwx| ≤ 2^{n} = k

• vx ≠ ϵ, weil G ∈ CNF (A → BC)

• uv^{i}wx^{i}y ∈ L ∀i ∈ ℕ ♢

\underline{Lemma:} L = \{a^{n}b^{n}c^{n}|n ≥ 1\} ∉ CF L(\{a, b, c\})

\underline{Beweis:} Währe L kontextfrei, so existiert ein Pumping-Index k ∈ ℕ. Für a^{k}b^{k}c^{k} existiert eine Zerlegung uvwxy mit den Eigenschaften des Pumpin-Lemmas, insbesondere uwy ∈ L

a .. \underbrace{.ab..}_{k} .bc...c = u \underbrace{vwx}_{≤k} y

Da vx ≠ ϵ, muß |uwy| ≤ 3k. Da |vwx| ≤ k, kann vx nicht gleichzeitig ein a und ein c enthalten. Also muß uwy = a^{k}... oder uwy = ...a^{k} sein. ♢

\underline{Satz:} CFL ist weder unter Durchschnitt noch unter Komplement abgeschlossen.

\underline{Beweis:} S → Sc | Ac  und  S → aS | aA
A → aAb | ab A → bAc | bc

erzeugen die Sprachen {a^{n}b^{n}c^{k} | n, k ≥ 1} bzw. {a^{k}b^{n}c^{n} |k, n ≥ 1} deren Schnitt nicht kontextfrei ist. Da CF L unter Vereinigung abgeschlossen ist, kann Sie nicht unter Komplement abgeschlossen sein, denn L_{1} ∩ L_{2} = \overline{\overline{L_{1}} ∩ \overline{L_{2}}} ♢

3.5 Entscheidbare Eigenschaften von CFG

\underline{Satz:} Das Wortproblem und das Leerheitsproblem sind für CF G entscheidbar.

\underline{Beweis:} w ∈ L(G) ↷ ↶ S ∈ \underline{P re}^{∗}(\{w\})

L(G) = ∅ ↷ ↶ S ∉ \underline{P re}^{∗}(Σ^{∗})  [figure: ⟲]  ♢

Bemerkungen: 1.) Das Wortproblem ist in O(n^{3}) entscheidbar (CYK-Algorithmus). 2.) Das Äquivalenzproblem ist nicht entscheidbar.

3.6 Kellerautomaten

• Kellerspeicher (Stack, Stapel) : Wichtige Datenstruktur für die sequentielle Behandlung strukturierter Objekte.

• Charakterisierung von CF L durch nicht-deterministische Kellerautomaten. Keine Äquivalenz zu deterministischen Kellerautomaten.

• Bedeutung deterministischer Kellerautomaten für den Compilerbau:

– Syntaxanalyse

– Datenkeller (Auswertung von Rechenausdrücken)

– Prozedurkeller (Speichertechnik für rekursive Prozeduren)

\underline{Definition}: Seien Q, Σ, Γ nicht-leere endliche Mengen von Zuständen, Eingabe-, und Kellersymbolen; ferner q_{0} ∈ Q Anfangszustand, F ⊆ Q Endzustandsmenge, Z_{0} ∈ Γ Kellerstartsymbol und δ : Q × Σ_{ϵ} × Γ → P\underline{f}(endlicheT eilmenge)(Q × Γ^{∗}) Transitionsfunktion. Dann heißt 𝔄 =< Q, Σ, Γ, δ, q_{0}, F, Z_{0} > ein Kellerautomat über Σ. Bezeichnung: 𝔄 ∈ P DA(Σ)

\underline{Semantik}

• Konfigurationsmenge: Q × Σ^{∗} × Γ^{∗}

• Einzelschrittrelation: (q, w, α) ⊢ (q′, w′, α′)

– Σ-Schritt: (q, aw, Z_{α}) ⊢ (q′, w, βα) falls δ(q, a, Z) ∋ (q′, β)

– ϵ-Schritt: (q, w, Z_{α}) ⊢ (q′, w, β) falls δ(q, ϵ, Z) ∋ (q′, β)

Die von 𝔄 erkannte Sprache: L(𝔄) := {w ∈ Σ^{∗} | q_{0}, w, Z_{0}) ⊢^{∗} (q, ϵ, α), q ∈ F }

\underline{Bemerkung}: Alternative Erkennung mit leerem Keller äquivalent. L(P DA, F) = L(P DA, ϵ)

\underline{Definiere} 𝔄_{G} =< Q, Σ, Γ, δ, q_{0}, F, Z_{0} >∈ P DA(Σ) durch Q := \{q\}, Γ := N ∪ Σ, Z_{0} := S δ(q, a, a) := {(q, ϵ)} ∀a ∈ Σ δ(q, ϵ, A) := {(q, β) | A → β in P } ∀A ∈ N

\underline{Satz}: CF L(Σ) ⊆ L(Σ, P DA)

\underline{Beweis:} “Simulation von Linksableitungen auf Keller” Sei G =< N, Σ, P, S >∈ CF G \underline{Ziel}: Nachweis von L(G) = L(𝔄_{G}, ϵ)

A ⇒^{∗} w ↷ ↶ (q, wv, Aα) ⊢^{∗} (q, v, α) ∀v ∈ Σ^{∗} und α ∈ Γ^{∗}

• “↷” Induktion über die Ableitungsmenge n

– n = 1: A → w (q, wv, Aα) ⊢ (q, wv, wα) ⊢^{∗} (q, v, α)

– n → n + 1: A ⇒ v_{0}A_{1}v_{1}...A_{r}v_{r} ⇒^{n} w. Dann muß A_{i} ⇒^{n_{i}} w_{i}, w = v_{0}w_{1}v_{1}...w_{r}v_{r}, so

daß nach Induktion

(q, \underbrace{v_{0}w_{1}v_{1}...w_{r}v_{r}}_{w} v, Aα)

⊢ v_{0}w_{1}...v_{r}v, v_{0}A_{1}v_{1}...A_{r}v_{r}α) ⊢^{∗} (q, w_{1}v_{1}...v_{r}v, A_{1}v_{1}...A_{r}vrα) ⊢_{I.V.}^{∗} (q, v_{1}w_{1}...v_{r}v, v_{1}...α)... ⊢^{∗} (q, v, α)

• “↶” Induktion über die Länge der Berechnung.

– n = 1: Dann muß A → ϵ und w = ϵ gelten, also A ⇒^{∗} w

– n → n + 1: (q, wv, Aα) ⊢^{n+1} (q, v, α) zerfällt in (q, wv, Aα) ⊢ (q, wv, v_{0}A_{1}v_{1}...A_{r}v_{r}α) ⊢^{∗} (q, w_{1}v_{1}...w_{r}v_{r}v, A_{1}v_{1}...A_{r}v_{r}α) ⊢^{n_{1}} (q, v_{1}, w_{r}v_{r}v, v_{1}...vA_{r}v_{r}α) ... ⊢^{n_{r}} (q, v_{r}v, v_{r}α) ⊢^{∗} (q, v, α)

Nach Induktionsvoraussetzung gibt es Ableitungen

A_{1} ⇒^{∗} w_{1}...A_{r} ⇒^{∗} w_{r} so daß A ⇒ v_{0}A_{1}v_{1}...A_{r}v_{r} ⇒^{∗} v_{0}w_{1}...v_{r} = w ♢

\underline{Satz}: L(Σ, P DA, F) ⊆ CF L(Σ) (ohne Beweis)

\underline{Korollar}: CF L ist unter Schnitt mit regulären Sprachen abgeschlossen.

\underline{Beweis}: Für L ∈ CF L(Σ) und R ∈ REG(Σ) ex.𝔄_{L} ∈ P DA(Σ) und 𝔄_{R} ∈ DF A(Σ) mit L = L(𝔄_{L}) und R = L(𝔄_{R}). Konstruiere 𝔄_{L}∥𝔄_{R} ∈ P DA(Σ) durch Parallelkonstruktion. Q := Q_{L} × Q_{R}

δ((q_{1}, q_{2}), a, Z) ∋ (q′_{1}, q′_{2}, α)

falls δ_{L}(q_{1}, a, Z) ∋ (q′_{1}, α) und δ_{R}(q_{2}, a) = q′_{2} F := F_{L} × F_{R} ♢

\underline{Ziel}: Der Deklarationszwang von Variablen ist keine kontextfreie Eigenschaft.

\underline{Lemma}: L = \{ww | w ∈ \{a, b\}^{+}\} ∈ CF L

\underline{Beweis}: Zunächst zeigen wir: L′ = \{a^{m}b^{n}a^{m}b^{n} | m, n ≥ 1\} ∉ CF L Wäre L′ ∈ CF L, so ex. Pumping-Index k mit a^{k}b^{k}a^{k}b^{k} = uvwxy mit |vwx ≤ k und vx ≠ ϵ, also auch uwy ∈ L′. Dies ist ein Widerspruch, weil die Zahl der vorderen und hinteren a’s bzw. b’s nicht mehr gleich ist.

L′ = L ∩ \underbrace{\{a\}^{+}\{b\}^{+}\{a\}^{+}\{b\}^{+}}_{regulär}. Wäre L ∈ CF L, so auch L’. ♢

\underline{Korollar}: Die Menge P der Pascal-Programme ist nicht kontextfrei.

\underline{Beweis}: L := \{\underline{program} T (output); \underline{var} w : integer; \underline{begin} w := 1 \underline{end}. | w ∈ \{a, b\}^{+}\} Also: L ⊆ P R sei bestimmt durch den regulären Ausdruck:

\underline{program} T (output); \underline{var} (a ∨ b)^{+} : integer; \underline{begin} (a ∨ b)^{+} := 1 \underline{end}. Dann gilt: L = P ∩ R h Sei eine Substitutionsabbildung mit h(a) = a, h(b) = b, h(x) = ϵ Dann: h(L) = {ww | w ∈ {a, b}^{+}} ∉ CF L ↷ L ∉ CF L ↷ P ∉ CF L

3.6.1 Deterministische Kellerautomaten

\underline{Ziel}: L(Σ, DP DA) unter Komplement abgeschlossen, somit L(Σ, DP DA) ⫋ L(Σ, P DA) = CF L, d.h. i.A. keine Erkennung von L ∈ CF L durch deterministische Kellerautomaten möglich.

Syntaxanalyse mit DPDA’s für spezielle CFG.

\underline{Definition}: Sei 𝔄 =< Q, Σ, Γ, δ, q_{0}, Z_{0}, F >∈ P DA 𝔄 heißt deterministisch, in Zeichen 𝔄 ∈ DP DA(Σ), wenn gilt:

1. |δ(q, a, Z)| ≤ 1 für alle (q, a, Z) ∈ Q × Σ_{ϵ} × Γ

2. |δ(q, ϵ, Z)| = 1 ↷ |δ(q, a, Z)| = 0 für alle a ∈ Σ \underline{Folgerung}: Zu jeder Konfiguration (q, w, α) git es höchstens eine Folgekonfiguration. ϵ-Schritte möglich.

\underline{Bemerkung}: Bei Erkennung mit leerem Keller sind weniger Sprachen erkennbar.

\underline{Satz}: L(Σ, DP DA) ist unter Komplement abgeschlossen.

\underline{Beweisidee}: Zu jedem 𝔄 ∈ DP DA(Σ) ist ein äquivalenter _{ 𝔄̃} ∈ DP DA(Σ) konstruierbar, so daß gilt: Für jedes w ∈ Σ^{∗} gibt es q̃ ∈ Q und α ∈ Γ^{∗} mit (q̃_{0}, w, Z̃_{0}) ⊢^{∗} (q̃, ϵ, α). Dazu müssen Schleifenkonfigurationen eliminiert werden.

\underline{Definition}: q, w, α) ∈ Q × Σ^{∗} × Γ^{∗} heißt Schleifenkonfiguration, falls für jedes i ∈ ℕ ein q_{i} ∈ Q und ein α_{i} ∈ Γ^{∗} ex., so daß |α_{i}| ≥ |α| und (q, w, α) ⊢^{i} (q_{i}, w, α_{i}).

Diese Eigenschaft ist entscheidbar ↷ Elimination.

3.7 Der Algorithmus von Cocke, Younger und Kasami

Effiziente Lösung des Wortproblems für beliebige CF L. Dynamische Programmierung, O(n^{3})- Zeit, O(n^{2})-Platz. O.B.d.A. sei G ∈ CNF (auf beliebige CF G übertragbar). Für G =< N, Σ, P, S >∈ CNF (∗ A → BC, A → a ∗) und w = a_{1}a_{2}...a_{n} mit n > 0 definieren wir:

w_{ij} := a_{i}a_{i+1}...a_{j} für 1 ≤ i ≤ j ≤ n

N_{ij} := {A ∈ N | A ⇒^{∗} w_{ij}}

so daß gilt: w ∈ L(G) ↷ ↶ S ∈ N_{1n}

\underline{Bestimme N_{1n}}:

Bestimme N_{11}N_{22}N_{33} ... N_{nn} dann N_{12}N_{23} ... N_{(n−1)n}

N_{13} ... N_{(n−2)n}

⋮ ...

bis N_{1n}

mit Hilfe von:

1. A ∈ N_{ii} ↷ ↶A → a_{i} ∈ P

2. A ∈ N_{ij} mit i < j ↷ ↶∃k : i ≤ k ≤ j ∃A → BC ∈ P, B ∈ N_{ik}, C ∈ N_{k+1,j}

\underline{Bsp.:} G: S → AB | a A → BA | a

B → AB | b

[figure: i; 1; 2; 3; 4; j; 1; 2; 3; 4; b; a; a; b; {B}; {A}; ∅; {S, B}; {S, A}; ∅; {S, B}; {S, A}; {S, B}; {B}]

also baab ∈ L(G) Komplexität:

• Zeit: äußere “for i” c_{1} · n Schritte
“for k” c_{2} · d Schritte

innere “for i” c_{2} · (n − d) · d Schritte

“for d” c_{2} · ∑_{d=1}^{n−1}(n − d) · d Schritte

Insgesamt: c · ∑_{d=1}^{n}(n − d)d = c(n ∑_{d=1}^{n} d − ∑_{d=1}^{n} d^{2})

= c · (n^{2} \frac{n+1}{2} − n\frac{(n+1)(2n+1)}{6})
= c · \frac{n^{3}−n}{6} ∈ O(n^{3})

• Platz: O(n^{2})

3.8 Erweiterte kontextfreie Grammatiken (EBNF)

Höherer Beschreibungskomfort durch reguläre Ausdrücke als rechte Regelseite; äquivalente Erweiterung: \underline{Definition}: G =< N, Σ, P, S > ist eine erweiterte CFG, in Zeichen: G ∈ ECF G, wenn < N, Σ, P, S >∈ CF G und P : N → RA(N ∪ Σ). Schreibweise: A → α, falls P (A) = α. \underline{Semantik}: P repräsentiert die Regelmenge P̃ mit A → α̃ ∈ P̃ : :↷ ↶ã ∈ [[P (A)]] \underline{Beachte:} P̃ ist i.A. unendlich. L(G) := L(< N, Σ, P̃, S >) \underline{Satz:} CF L(Σ) = L(Σ, ECF G) \underline{Beweisidee:}

• “⊆” nach Definition.

• “⊇” Transformation von ECF G nach CF G durch Elimination regulärer Ausdrücke:

– Disjunktion: Regelalternation

– Stern: neues NT (non-terminal) mit A → αA | ϵ

3.9 Rekursive endliche Automaten (Syntaxdiagramme)

Syntaxdiagramme entsprechen endlichen Automaten, die sich rekursiv aufrufen können. Neben ·_{q} ⟶^{a} ·_{q′} ist auch ·_{q} ⟶^{r} ·_{q′} möglich.

\underline{Definition}: 𝔄 =< Q, Σ, δ, q_{0}, F > heißt rekursiver endlicher Automat über Σ, falls δ : Q × (Σ_{ϵ} ∪ Q) → P (Q) und sonst wie ein endlicher Automat. Bezeichnung: 𝔄 ∈ RF A(Σ)

\underline{Semantik}: Konfigurationen: Q × Σ^{∗} Transitionsrelation: ⊢ ⊆ (Q × Σ^{∗})^{2} ist definiert durch:

\frac{p ∈ δ(q, a)}{(q, aw) ⊢ (p, w)} \frac{p ∈ δ(q, ϵ)}{(q, w) ⊢ (p, w)}

\frac{p ∈ δ(q, r) (r, w) ⊢^{∗} (s, v) s ∈ F}{(q, w) ⊢ (p, v)}

L(Q) := {w ∈ Σ^{∗}|q_{0}, w) ⊢^{∗} (p, ϵ), p ∈ F }

\underline{Satz}: L(Σ, RF A) = L(Σ, P DA)

\underline{Beweis}:

• “⊆” 𝔄 =< Q, Σ, δ, q_{0}, F >∈ RF A(Σ)

Simulation von 𝔄 durch 𝔄′ =< Q, Σ, Q, δ′, q_{0}, q_{0}, ∅ >∈ P DA

Idee: Keller für “Rücksprungadressen” (Zustände)

δ′(q, a, s) = {(p, s)|p ∈ δ(q, a)} δ′(q, ϵ, s) = {(p, s)|p ∈ δ(q, ϵ)}

∪ {(r, ps)|p ∈ δ(q, r)} “Aufruf”
∪ {(s, ϵ)|q ∈ F } “Rücksprung”

für alle q, s, r, p ∈ Q und a ∈ Σ

• “⊇”

Für L ∈ L(Σ, P DA) existiert G ∈< N, Σ, P, S >∈ CNF mit L = L(G). Konstruiere

𝔄 =< Q, Σ, δ, q_{0}, F >∈ RF A durch Q := N ∪^{·} {q_{f}}, q_{0} := S, F := {q_{f}} und

c ∈ δ(A, B), falls A → BC q_{f} ∈ δ(A, a), falls A → a q_{f} ∈ δ(S, ϵ), falls S → ϵ ♢ 34 KAPITEL 3. KONTEXTFREIE GRAMMATIKEN UND KELLERAUTOMATEN

Turingmaschinen und Aufzählbare Sprachen

4.1 Chomsky-Grammatiken

Verallgemeinerung kontextfreier Grammatiken, kontextabhängige Ersetzung, Wertersetzung.

\underline{Definition}: Seien N, Σ, X und S wie bei CF G. Sei ferner P ⊆ X^{∗}\{N\}X^{∗} × X, P endlich. Dann heißt G =< N, Σ, P, S > eine Chomsky-Grammatik

\underline{Semantik}: π = α_{1} → α_{2} ∈ P bestimmt die Ableitungsrelation ⇒_{π}⊆ X^{∗} × X^{∗} durch β_{1} ⇒_{π} β_{2} ↷ ↶ es ex. γ, δ ∈ X^{∗} mit β_{1} = γα_{1}δ und β_{2} = γα_{2}δ Ableitungsrelation von G:

⇒_{G}:= ⋃_{π∈P} ⇒_{π}

G erzeugt L(G) := {w ∈ Σ^{∗} | S ⇒_{G}^{∗} w}

Folien 4.2 und 4.3 Abschlußeigengschaften von L_{0} und L_{1}.

\underline{Definition}: Sei G =< N, Σ, P, S > vom Typ-0. G heißt normiert, wenn gilt:

• Für jedes π = α_{1} → α_{2} ∈ P gibt es γ, δ ∈ N^{∗}, A ∈ N, β ∈ X^{∗} mit α_{1} = γAδ und α_{2} = γβδ

• Σ-Symbole nur in Regeln der Form A → a

\underline{Beachte}: β = ϵ erlaubt im Gegensatz zu Typ-1.

\underline{Satz}: Zu jedem G =< N, Σ, P, S > vom Typ-0 läßt sich eine äquivalente normierte Grammatik G′ =< N′, Σ, P′, S′ > konstruieren.

\underline{Beweis}:

1. Terminalsymbolbedingung: a ∈ Σ → A_{a} neues N-Symbol a durch Aa ersetzen (in P), Aa → a hinzufügen.

2. Simulation von A_{1}...A_{n} → B_{1}...B_{m}(n ≥ 1, m ∈ ℕ) durch folgende Regeln:

A_{1}A_{2}A_{3}...A_{n−1}A_{n} → A′_{1}A_{2}A_{3}...A_{n−1}A_{n} A′_{1}A_{2}A_{3}...A_{n−1}A_{n} → A′_{1}A′_{2}A_{3}...A_{n−1}A_{n}

A′_{1}A′_{2}A′_{3}...A′_{n−1}A_{n} → A′_{1}A′_{2}A′_{3}...A′_{n−1}A′_{n} A′_{1}A′_{2}A′_{3}...A′_{n−1}A′_{n} → B_{1}A′_{2}A′_{3}...A′_{n−1}A′_{n}

\underline{2 Fälle}:

Fall 1: n ≤ m B_{1}...B_{n−1}A′_{n} → B_{1}...B_{m}

Fall 2: n > m B_{1}...B_{m}A′_{m+1}A′_{n} → B_{1}...B_{m}A′_{m+1}...A′_{n}

B_{1}...B_{m}A′_{n} → B_{1}...B_{m}

A′_{i} neue N-Symbole: Sie verhindern Seiteneffekte: neue Satzformen, mehr Ableitungen

♢

\underline{Satz}: L_{0}(Σ) ist unter Substitution abgeschlossen, d.h.: ist

ϕ : P(Σ^{∗}) → P ( ⋃_{a∈Σ} Σ_{a})^{∗}

eine Substitutionsabbildung, so gilt:

L ∈ L_{0}(Σ), ϕ(a) ∈ L_{0}(Σ_{a})∀a ∈ Σ ↷ ϕ(L) ∈ L_{0}( ⋃_{a∈Σ} Σ_{a})

\underline{Beweis}: Konstruktion von kontextfreien Grammatiken (CF G) nicht anwendbar, wegen möglicher neuer Satzformen. Idee: Sequentialisierung mit einem Kontrollsymbol (Siehe Bild auf Blatt 26, Rückseite) L = L(G) mit G =< N, Σ, P, S > vom Typ-0. ϕ(a) = L_{a} = L(G_{a}) mit G_{a} =< N_{a}, Σ_{a}, P_{a}, S_{a} > vom Typ-0. O.B.d.A.: G, G_{a} normiert, N, N_{a} disjunkt. Konstruktion von \overline{G} mit L(\overline{G}) = ϕ(L).

\overline{N} := N ∪^{·} ( · ; ⋃_{a∈Σ} N_{a}) ∪^{·} \{A_{a} | a ∈ Σ\} ∪^{·} \{\overline{S}, C\}

\overline{Σ} := ⋃_{a∈Σ} Σ_{a}

\overline{P} := P_{0} ∪ P_{1} ∪ P_{2} ∪ ( ⋃_{a∈Σ} P_{a}) ∪ \{\overline{S}_{R} → CS, C → ϵ\}

mit P_{0} entstehe aus P durch Ersetzen von a durch A_{a} (a ∈ Σ)

P_{1} := {CA_{a} → CSa | a ∈ Σ} P_{2} := \{Ca → aC | a ∈ \overline{Σ}\}

1. ϕ(L) ⊆ L(\overline{G}) :

\overline{S} ⇒ CS ⇒^{∗} CAa_{1}...Aa_{r} ⇒^{∗} CS_{a_{1}}A_{a_{2}}...A_{a_{r}}

Cw_{1}A_{a_{2}}...A_{a_{r}} w_{1}CA_{a_{2}}... ... w_{1}...w_{r}

2. L(\overline{G}) ⊆ ϕ(L): keine Ableitungen neuer Wörter, weil G normiert ist und daher A_{a} auf keiner linken Regelseite, weil die N-Alphabete disjunkt sind und weil C die Teilableitungen der G_{a} sequentialisiert. ♢

\underline{Korollar}: L_{0}(Σ) ist unter den regulären Operationen abgeschlossen.

\underbrace{L}_{\{a\}}, \underbrace{L′}_{\{b\}} ∈ L_{0}(Σ) ↷ \underbrace{L ∪ L′}_{\{a,b\}}, \underbrace{LL′}_{\{ab\}}, \underbrace{L^{∗}}_{\{a\}^{∗}} ∈ L_{0}(Σ).

\underline{Beweis}: Wie für CF L.

\underline{Satz:} L_{0}(Σ) ist unter Schnitt abgeschlossen.

\underline{Beweis}: L_{i} = L(G_{i}) und G_{i} =< N_{i}, Σ, P_{i}, S_{i} > vom Typ-0 für i = 1, 2. O.B.d.A. sei N_{1} ∩ N_{2} ≠ ∅ Konstruktion von G =< N, Σ, P, S >:

N := N_{1} ∪ N_{2} ∪ {A_{a} | a ∈ Σ} ∪^{·} {S, C_{1}, C_{2}}

P := P_{1} ∪ P_{2} ∪ Q Q := {S → C_{1}S_{1}C_{2}S_{2}C_{1},

C_{2}a → A_{a}C_{2},

bA_{a} → A_{a}b,
C_{1}A_{a}a → aC_{1},

C_{1}C_{2}C_{1} → ϵ} ♢

4.1.1 Kontextrekursive Grammatiken und Sprachen

Typ-1 ∼ Platzbedarf von Berechnungen.

\underline{Definition}: G =< N, Σ, P, S > heißt von wachsender Länge :↷ ↶ für jede Regel α → β ∈ P gilt |α| ≤ |β|, es sei denn, daß S → ϵ ∈ P und S auf keiner rechten Regelseite.

\underline{Korollar}: Eine Typ-1-Grammatik ist von wachsender Länge.

\underline{Satz}: Zu jeder Grammatik von wachsender Länge läßt sich eine äquivalente Typ-1-Grammatik konstruieren.

\underline{Beweis:} Normierung

\underline{Definition}: (Platzbedarf) Sei G =< N, Σ, P, S > von Typ-0, δ = (S ⇒ α_{0} ⇒ α_{1} ⇒ ...α_{n}) eine Ableitung von G und w ∈ Σ^{∗}. Dann heißt:

\underline{pl}_{G}(δ) := \underline{max}\{|α_{i}| | 0 ≤ i ≤ n\} der Platzbedarf von δ und \underline{pl}_{G}(w) := \underline{min}\{\underline{pl}_{G}(δ) | δ = (S ⇒ ... ⇒ w)\}

\underline{Folgerungen}:

1. \underline{pl}_{G}(w) ≥ |w|

2. G vom Typ-2, w ∉ ϵ ↷ \underline{pl}_{G}(w) = |w|

\underline{Platzbedarfssatz}: Sei G vom Typ-0, p ∈ ℕ, p > 0, so daß für alle w ∈ L(G) \ \{ϵ\} : \underline{pl}_{G}(w) ≤ p|w| Dann ist L(G) ∈ L_{1}

\underline{Beweis}: Sei p = 1, also für w ∈ L(G) \ ϵ : \underline{pl}_{G}(w) = |w| Elimination verkürzender Regeln durch auffüllen. Konstruktion einer äquivalenten Grammatik von wachsender Länge: G′ =< N ∪^{·} {$}, Σ, P′, S >

1. α → β ∈ P mit |α| = |β| + i (i > 0) ↷ α → $^{i}β ∈ P′

2. α → β ∈ P mit |α| ≤ |β| ↷ $^{i}α → β ∈ P′ ∀j = 0, 1, ..., |β| − |α|

3. $X → X$, X$ → $X ∈ P′ ∀X ∈ X

Wegen \underline{pl}_{G}(w) = |w| lassen sich die eingeschlossene $ löschen. p > 1: Induktion. Idee: N′ ⊇ N^{P} Abschlußeigenschaften von L_{1}(Σ) mit Hilfe des Platzbedarfssatzes. ♢

\underline{Satz}: L_{1}(Σ) ist unter ϵ-freien Substitutionen (ϵ ∉ ϕ(a)) abgeschlossen.

\underline{Beweis}: Platzbedarf der Ausgangsgrammatik mit p = 1 ↷ Platzbedarf der Substitutionsgrammatik |w| + 1 ≤ 2|w| wegen zusätzlicher Kontrollsymbole C und fehlender ϵ-Regeln.

♢

\underline{Korollar}: L_{1}(Σ) ist unter regulären Operationen (∪, ·, ∗) abgeschlossen.

\underline{Beweis}: Reduktion auf ϵ-freie Sprachen: L ∈ L_{1}(Σ) ↷ L \ \{ϵ\} ∈ L_{1}(Σ) Für ϵ-freie L, L′ ∈ L_{1}(Σ) folgt L ∪ L′, LL′, L^{∗} ∈ L_{1}(Σ) wie für Typ-0-Sprachen durch ϵ-freie Substitution. Falls ϵ ∈ L und/oder ϵ ∈ L′, so folgert man aus den ϵ-freien Teilsprachen,

z.B.: (L ∪^{·} {ϵ})(L′ ∪^{·} {ϵ}) = LL′ ∪ L ∪ L′ ∪ {ϵ} ∈ L_{1}(Σ) ♢

\underline{Korollar}: L_{1}(Σ) ist unter Durchschnitt abgeschlossen.

\underline{Beweis}: L_{1}, L_{2} ∈ L_{1}(ϵ) sind mit linearem Platzbedarf (p = 1) erzeugbar. Die ∩-Konstruktion für Typ-0:

[figure: C_{2}S_{1}C_{1}S_{2}C_{2}; w = v; w]

hat dann einen Platzbedarf von 2|w| + 3 ≤ 5|w| ♢

\underline{Korollar}: L_{2}(Σ) ⫋ L_{1}(Σ)

\underline{Beweis}: L_{2}(Σ) ist nicht unter ∩ abgeschlossen. ♢

Ein lange offenes Problem: Abschluß L_{1} unter Komplement: 1987: L_{1} ist unter Komplement abgeschlossen.

4.2 Turingmaschinen, linear beschränkte Automaten

\underline{Ziel:} L_{0}(Σ) = L(Σ, T M)

L_{1}(Σ) = L(Σ, LBA)

(unendliches Band, endlicher Anteil beschrieben)

□ a b c d a c □ □ □ □ □ □^{}endliche Steuerung (endlicher Automat)

\underline{Definition}: (Nicht-deterministische erkennende Turingmaschinen) Seien die folgenden nicht-leeren, endliche Mengen gegeben:

• Q Zustandsmenge

• Σ Eingabealphabet

• Γ Arbeitsalphabet mit Σ ⊆ Γ Ferner:

• q_{0} ∈ Q Anfangszustand

• □ ∈ Γ \ Σ Blank

• F ⊆ Q Endzustandsmenge und die Transitionsfunktion:

• δ : Q × Γ → p(Q × Γ × {L, N, R}) Dann heißt:

𝔄 =< Q, Σ, Γ, q_{0}, □, F, δ > eine (nicht-deterministische) erkennende Turingmaschine. Bezeichnung: 𝔄 ∈ T M(Σ) \underline{Semantik}: Konfigurationsmenge: Q × Γ^{∗} × Γ × Γ^{∗} =: \underline{Conf}(𝔄) Einzelschrittrelation: ⊢_{𝔄}⊆ Conf(𝔄)^{2} ist definiert durch:

• (q, α, X, β) ⊢ (q′, α, X′, β) falls δ(q, X) ∋ (q′, X′, N)

• (q, αY, X, β) ⊢ (q′, α, Y, X′β) falls δ(q, X) ∋ (q′, X′, L)

• (q, ϵ, X, β) ⊢ (q′, ϵ, □, X′β) falls δ(q, X) ∋ (q′, X′, L)

• (q, α, X, Y β) ⊢ (q′, αX′, Y, β) falls δ(q, X) ∋ (q′, X′, R)

• (q, α, X, ϵ) ⊢ (q′, αX′, □, ϵ) falls δ(q, X) ∋ (q′, X′, R) \underline{Anfangskonfiguration} von w ∈ Σ^{∗}:

κ(w) := \{ \begin{matrix}(q_{0}, ϵ, a, v) falls w = av \\ (q_{0}, ϵ, □, ϵ) falls w = ϵ \end{matrix}

\underline{Endkonfiguration} (q, α, X, β) falls q ∈ F Die von 𝔄 erkannte Sprache: L(𝔄) := {w ∈ Σ^{∗} | κ(w) ⊢^{∗} (q, α, X, β), q ∈ F } \underline{Beachte}: Erreichen von q ∈ F genügt, kein Anhalten gefordert. Die Klasse der TM-erkennbaren Sprachen: L(Σ, T M)

\underline{Satz}: L(Σ, T M) = L_{0}(Σ)

\underline{Beweis}:

1. \underline{L(Σ, T M) ⊆ L_{0}(Σ)}

𝔄 =< Q, Σ, Γ, q_{0}, □, F, δ >∈ T M(Σ) Simulation von 𝔄 durch Typ-0-Grammatik. \underline{Idee:} Erzeugen einer beliebigen Anfangskonfiguration mit hinreichend vielen Blanks an den Rändern (bei Ableitungen sind Ränder nicht erkennbar). Zwei Spuren:

1. Spur hält Eingabe für die Erzeugung 2. Spur simuliert TM

Für a_{1}...a_{r} ∈ Σ^{∗}, m, n ∈ ℕ erzeugt man:

(*) (Σ, □)^{m}q_{0}(a_{1}, a_{1})(a_{2}, a_{2})...(a_{r}, a_{r})(ϵ, □)^{n} Dazu G =< N, Σ, P, S > mit

N := Q ∪^{·} (Σ_{ϵ} × Γ) ∪^{·} {S, C_{1}, C_{2}}

P : S → (ϵ, □)S | q_{0}C_{1} C_{1} → (a, a)C_{1} | C_{2} (a ∈ Σ)

C_{2} → (ϵ, □)C_{2} | ϵ

( P: erzeugen von (*) ) q(a, X) → q′(a, X′) falls δ(q, X) ∋ (q′, X′, N) q(a, X) → (a, X′)q′ falls δ(q, X) ∋ (q′, X′, R) (b, Y)q(a, X) → q′(b, Y), (a, X′) falls δ(q, X) ∋ (q′, X′, L) q → ϵ falls q ∈ F löschen von q und der 2. Spur (a, X) → a (a ∈ Σ_{ϵ}) ursprüngliches Wort bleibt übrig. Es folgt: L(G) = L(𝔄)

2. \underline{L_{0}(Σ) ⊆ L(Σ, T M)} Simulation einer Typ-0-Sprache durch TM. Neben Eingabewort Ableitung von G simulieren und erzeugtes Wort mit der Eingabe vergleichen. Technisch aufwendig: Einschieben und Löschen von Worten auf einem Turingband. ♢

Automatencharakterisierung von L_{1}(Σ) durch Platzbedarf \underline{Definition}: (Platzbedarf für TM) Sei 𝔄 ∈ T M(Σ), γ = (κ_{0} ⊢ κ_{1} ⊢ ... ⊢ κ_{n}) eine Berechung und w ∈ L(𝔄). Dann ist:

• |κ_{i}| = |αXβ| falls κ_{i} = (q, α, X, β)

• bv_{𝔄}(γ) := \underline{max}\{|κ_{i}| |0 ≤ i ≤ n\}

• bv_{𝔄}(w) := \underline{min}\{bv_{𝔄}|γ erkennt w\} der Bandverbrauch von 𝔄 für γ bzw. w. \underline{Definition}: 𝔄 ∈ T M heißt linear beschränkt, wenn p ≥ 1 existiert, so daß für alle w ∈ L(𝔄) \ {ϵ} bv_{𝔄}(w) ≤ p · |w| gilt. \underline{Korollar:} L(Σ) = L(Σ, lbT M) Grund: Simulationen erhalten linearen Platzbedarf / Bandverbrauch. \underline{Definition}: 𝔄 ∈ LBA(Σ) :↷ ↶ 𝔄 lbT M mit p = 1, d.h. nur Eingabefelder werden benutzt. \underline{Satz}: L_{1}(Σ) = L(Σ, LBA) \underline{Beweisidee}: Kompression des benutzten Bandbereichs durch Vergrößerung des Arbeitsalphabets Γ^{L} := Γ^{P}

4.2.1 Deterministische Turingmaschine, k-Band TM

Reduktion nicht-det. TM auf det. TM in 2 Schritten:

1. Simulation einer ndTM durch 3-Band-TM

2. Reduktion von k-Band-dTM auf 1-Band dTM \underline{Definition}: (det. k-Band-TM) 𝔄 =< Q, Σ, Γ, q_{0}, □, F, δ >∈ k − dT M, wenn δ : q × Γ^{k} − → Q × (Γ × {L, N, R})^{k} und sonst wie TM \underline{Konfigurationen:} Q × (Γ^{∗} × Γ × Γ^{∗})^{k} \underline{Einzelschrittrelation:} simultanes Arbeiten auf k-Bändern gemäß δ \underline{Anfangskonfiguration} für w ∈ Σ^{∗}:

κ_{w} := \{ \begin{matrix}(q_{0}, (ϵ, a, v), (ϵ, □, ϵ)^{k−1}) & falls w = av \\ (q_{0}, (ϵ, □, ϵ)^{k}) & falls w = ϵ \end{matrix}

\underline{Satz}: Zu jedem 𝔄 ∈ T M läßt sich ein äquivalenter 𝔄′ ∈ 3 − dT M konstruieren. \underline{Beweis}: Für δ_{𝔄} : Q × Γ → p_{f}(Q × Γ × \{L, N, R\}) gelte: max{|δ(q, X)| |(q, X) ∈ Q × Γ} =: r Bezeichnung der Alternativen von 𝔄 durch Elemente von [r] := {1, ..., r} Berechnung von 𝔄 bestimmt ζ ∈ [r]^{∗} Umgekehrt Auswahl einer Berechnung durch ein ζ als Steuerwert.

• Band 1: Eingabe, wiederholtes Lesen.

• Band 2: Erzeugung der Zahlenfolgen ζ ∈ [r]^{∗}

• Band 3: Simulation von Q gemäß Band 2

Sukzessive Berechnung aller ζ ∈ [r]^{∗} Für jedes ζ Kopie der Eingabe auf Band 3. \underline{Beachte}: Nicht jedes ζ entspricht einer Berechnung. ♢

\underline{Satz}: Zu jeder 𝔄 ∈ k − dT M läßt sich ein äquivalentes 𝔄′ ∈ 1 − dT M konstruieren.

\underline{Korollar}: L(Σ, T M) = L(Σ, dT M)

\underline{Bemerkung}: Für LBA’s ist diese Frage offen: das LBA-Problem.

4.3 Aufzählbare und entscheidbare Sprachen

\underline{Intuitiv}:

• L ⊆ Σ^{∗} ist aufzählbar, wenn es ein effektives Verfahren gibt, welches genau die Elemente von L erzeugt.

• L ⊆ Σ^{∗} ist entscheidbar, wenn es ein effektives Verfahren gibt, welches für jedes w ∈ Σ^{∗} feststellt, ob w ∈ L oder ob w ∉ L gilt.

\underline{Folgerung}: Für L ⊆ Σ^{∗} gilt: L entscheidbar ↷ ↶ L und Σ^{∗} \ L aufzählbar. (Reißverschlußverfahren)

\underline{Formalisierung}: TM mit Ausgabe.

\underline{Satz}: \{L ⊆ Σ^{∗} | L aufzählbar \} = L(Σ, dT M)

\underline{Church-Turing-These}: ↷ Jede effektiv beschreibbare Sprache ist eine Typ-0-Sprache.

\underline{Satz}: L_{0}(Σ) ⫋ p(Σ^{∗})

\underline{Beweis}: Die Menge der Typ-0-Grammatiken über Σ läßt sich abzählen (nach ihrer Größe).

Also ist L_{0}(Σ) abzählbar. p(Σ^{∗}) ist jedoch überabzählbar. \underline{Diagonalverfahren von Cantor}: |Σ| = 1, Σ^{∗} = ℕ, L ⊆ Σ^{∗} ↦ \underline{char}_{L} : ℕ → \{0, 1\} Angenommen: p(ℕ) sei abzählbar.

3210 0 1 2 3 0 1 1 0 1 0 1 0^{...}

f : ℕ^{R} → {0, 1} f(i, j) = 1 ↷ ↶ \underline{char}_{L−i}(d) = 1 ♢ \underline{Definition}: L_{diag} ⊆ ℕ durch \underline{char}_{L_{diag}}(j) := 1−f(j, j), dann kann L_{diag} nicht in der Abzählung vorkommen. \underline{Satz}: DEC(Σ) := \{L ∈ Σ^{∗} | L entscheidbar\} ⫋ L_{0}(Σ) \underline{Beweis}: Die Sprache Univ ist nicht entscheidbar. Diagonalisierungsschluß (Selbstanwendungsproblem). Vgl. Vorl. BuK. ♢ \underline{Satz:} Jede Typ-1-Sprache ist entscheidbar. \underline{Beweis:} Sei G eine Typ-1-Grammatik über Σ und w ∈ Σ^{∗}

Fall 1: w = ϵ ∈ L ↷ ↶ S → ϵ ∈ P

Fall 2: w ≠ ϵ ∈ L ↷ ↶ ∃ Ableitung: S ⇒ α_{1} ⇒ ... ⇒ α_{n} = w mit |α_{i}| ≤ |w|

Nur endlich viele solcher Ableitungen. ♢

\underline{Satz:} Es gibt entscheidbare, nicht-kontextsensitive Sprachen. \underline{Beweis:} Literatur.

Unentscheidbare Probleme

\underline{Ziel:} Die Folgenden Probleme sind unentscheidbar:

• das Wortproblem für Typ-0-Beschreibugnen (BuK);

• das Leerheitsproblem für Typ-1-Beschreibungen;

• das Äquivalenzproblem für Typ-2-Beschreibungen.

\underline{Bemerkung:} Das Äquivalenzproblem für DP DA’s wurde kürzlich als entscheidbar nachgewiesen.

\underline{Hilfsmittel:} Das Postsche Korrespondenzproblem (BuK). Seien w = (w_{1}, w_{2}, ..., w_{n}) und v = (v_{1}, v_{2}, ..., v_{n}) mit w_{i}, v_{i} ∈ Σ^{∗} und 1 ≤ i ≤ n

\underline{Beispiel:} Eingabe (1, 10, 011) und (101, 00, 11), Indizes: (1, 3, 2, 3): 1 011 10 011 = 101 11 00 11

Dann heißt (i_{1}, ..., i_{k}) ∈ {1, .., n}^{k} eine Lösung von P CP (w, r),falls w_{i_{1}}w_{i_{2}}...w_{i_{k}} = v_{i_{1}}v_{i_{2}}...v_{i_{k}}

\underline{Es gilt:} Das Postsche Korrespondenzproblem ist unentscheidbar, d.h. es gibt kein Verfahren, welches für n ∈ ℕ und w, v ∈ (Σ^{∗})^{n} feststellt, ob P CP (w, v) eine Lösung besitzt oder nicht.

\underline{Beweis:} Reduktion des P CP auf das Leerheitsproblem (Typ-1) Sei w = (w_{1}, ..., w_{n}), v = (v_{1}, ..., v_{n}) ∈ (Σ^{∗})^{n} Konstruktion von 𝔄(w, r) ∈ lbT M mit P CP (w, v) lösbar ↷ ↶L(𝔄(w, v)) ∈ ∅ 𝔄(w, v) erzeugt bei Eingabe von u ∈ Σ^{+} alle Folgen (i_{1}, ..., i_{k}) ∈ {1, ..., n}^{k} mit k ≤ |u| und prüft jeweils, ob w_{i_{1}}...w_{i_{k}} = v_{i_{1}}...v_{i_{k}}. 𝔄 erkennt u, falls eine solche Indexfolge auftritt. Platzbedarf ist linear in |u|. Wäre das Leerheitsproblem entscheidbar, so auch P CP.

♢

\underline{Satz:} Schnittproblem für Kontextfreie Sprachen. Es ist nicht entscheidbar, ob für G_{1}, G_{2} ∈ CF G gilt: L(G_{1}) ∩ L(G_{2}) = ∅

\underline{Beweis:} Reduktion des P CP auf das Schnittproblem von CF L. Sei w = (w_{1}, ..., w_{n}) und v = (v_{1}, ..., v_{n}) ∈ (Σ^{∗})^{n}. Konstruiere G_{w}, G_{v} ∈ CF G, so daß P CP (w, v) lösbar ↷ ↶ L(G_{w}) ∩ L(G_{v}) ≠ ∅

Σ̃ := Σ ∪^{·} {b_{1}, ..., b_{n}}

G_{w} :=< {S_{w}}, Σ̃, P_{w}, S_{w} > mit den Regeln: P_{w} := S_{w} → w_{i}S_{w}b_{i}, S_{w} → w_{i}b_{i} | 1 ≤ i ≤ n} G_{v} analog. Es folgt: L_{w} := L(G_{w}) = {w_{i_{1}}w_{i_{2}}...w_{i_{k}}b_{i_{k}}b_{i_{k−1}}...b_{i_{1}} |k ≥ 1, 1 ≤ i_{j} ≤ n} L_{v} analog. Und L − w ∩ L_{v} ≠ ∅ ↷ ↶∃I − 1...i_{k} ∈ 1...n, w_{i_{1}}...w_{i_{k}}b_{i_{k}}...b_{i_{1}} = v_{i_{1}}...v_{i_{k}}b_{i_{k}}...b_{i_{1}} also w_{i_{1}}...w_{i_{k}} = v_{i_{1}}...v_{i_{k}} ↷ ↶P CP (w, v) lösbar. ♢

\underline{Korollar:} Das Schnittproblem für DP DA ist nicht entscheidbar.

\underline{Beweis:} G_{w} und G_{v} sind durch deterministische Kellerautomaten simulierbar. ♢

\underline{Satz:} Es ist nicht entscheidbar, ob für G_{1}, G_{2} ∈ CF G gilt: L(G_{1}) = L(G_{2}) (Äquivalenzproblem)

\underline{Beweis:} Reduktion des Schnittproblems für DP DA’s auf das Äquivalenzproblem von CF G ♢

\underline{Beachte:}

1. Zu 𝔄 ∈ DP DA(Σ) läßt sich \overline{𝔄} ∈ DP DA(Σ konstruieren mit L(\overline{𝔄} = \overline{L(𝔄)}

2. Zu 𝔄 ∈ P DA(Σ) läßt sich G_{𝔄} ∈ CF G(Σ konstruieren mit L(G_{𝔄} = L(𝔄)

3. Zu G_{1}, G_{2} ∈ CF G(Σ) läßt sich G_{v} ∈ CF G(Σ) konstruieren mit L(G_{v}) = L(G_{1}) ∨ L(G_{2})

Sei 𝔄_{1}, 𝔄_{2} ∈ DP DA

L(𝔄_{1}) ∩ L(𝔄_{2}) = ∅ ↷ ↶ L(𝔄_{1}) ⊆ L(\overline{𝔄_{2}}) ↷ ↶ L(G_{𝔄_{1}}) ⊆ L(G\overline{𝔄_{2}}) ↷ ↶ L(G_{𝔄_{1}}) ∪ L(G\overline{𝔄_{2}}) = L(G\overline{𝔄_{2}}) ↷ ↶ L(G_{v})L(G_{𝔄_{2}})

Die Entscheidbarkeit des Äquivalenzproblems für kontextfreie Grammatiken würde daher die Entscheidbarkeit des Schnittproblems nach sich ziehen: Widerspruch.