Automatentheorie und formale Sprachen Vorlesung – Prof. Dr. K. Indermark – Sommersemester 2001

geTEX’t von Matthias Hensler (mh@wspse.de)

1. September 2001

2

Inhaltsverzeichnis

1 Alphabete, Wörter, Sprachen 5 1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Operationen auf Menge von Worten . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Operationen auf 𝔭(Σ^{∗}) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Reguläre Ausdrücke und endliche Automaten 7

2.1 Reguläre Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Definition (Syntax) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.2 Vereinfachte Schreibweise . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.3 Definition (Semantik von RegE(Σ)) . . . . . . . . . . . . . . . . . . . 8 2.1.4 Standardprobleme für RegE(Σ) . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Deterministische endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Nicht-deterministische endliche Automaten . . . . . . . . . . . . . . . . . . . 9

2.3.1 Der Potenzmengenautomat . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Synthese und Analyse endlicher Automaten . . . . . . . . . . . . . . . . . . . 11

2.4.1 Synthese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.5 Das Pumping-Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Zustandsreduktion endlicher Automaten . . . . . . . . . . . . . . . . . . . . . 13

2.6.1 Ableitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.6.2 Der Ableitungsautomat . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.6.3 Der Faktorautomat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.7 Entscheidbare Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.7.1 Deterministische endliche Automaten . . . . . . . . . . . . . . . . . . 16 2.7.2 Reguläre Ausdrücke, nicht-deterministische Automaten . . . . . . . . 16

2.8 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Kontextfreie Grammatiken und Kellerautomaten 19

3.1 Kontextfreie Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Bezeichnungen und Konventionen . . . . . . . . . . . . . . . . . . . . . 19 3.1.2 Ableitungsbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1.3 Rechts- und Linksableitung . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1.4 Ein- und Mehrdeutigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Einseitig lineare Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Normalformen von Kontextfreien Grammatiken . . . . . . . . . . . . . . . . . 22 3.3.1 Elimination von ε-Regeln . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.2 Die Chomsky-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3.3 Die Greibach Normalform, Linksrekursion . . . . . . . . . . . . . . . . 25

3.4 Abschlußeigenschaften von CFL, Pumping-Lemma . . . . . . . . . . . . . . . 26 3.4.1 Substitutionssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.2 Pumping-Lemma (für CFL) . . . . . . . . . . . . . . . . . . . . . . . . 27

3.5 Entscheidbare Eigenschaften von CFG . . . . . . . . . . . . . . . . . . . . . . 28 3.6 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.6.1 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.6.2 Die von 𝔄 erkannten Sprachen . . . . . . . . . . . . . . . . . . . . . . 29 3.6.3 Deterministische Kellerautomaten . . . . . . . . . . . . . . . . . . . . 31

3.7 Der Algorithmus von Cocke, Yonnger und Kasami . . . . . . . . . . . . . . . 32

3.7.1 Komplexität des CYK-Algorithmus . . . . . . . . . . . . . . . . . . . . 32 3.8 Erweiterte kontextfreie Grammatiken (EBNF) . . . . . . . . . . . . . . . . . . 33 3.9 Rekursive endliche Automaten (Syntaxdiagramme) . . . . . . . . . . . . . . . 33

3.9.1 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4 Turingmaschinen und aufzählbare Sprachen 35

4.1 Chomsky-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1.1 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1.2 Klassifikation von Chomsky-Grammatiken und Sprachfamilien …. 35 4.1.3 Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1.4 Abschlußeigenschaften von ℒ_{0}(Σ) . . . . . . . . . . . . . . . . . . . . 36 4.1.5 Kontextsensitive Grammatiken und Sprachen . . . . . . . . . . . . . . 38 4.1.6 Platzbedarf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.1.7 Platzbedarfssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1.8 Abschlußeigenschaften von ℒ_{1}(Σ) mit Hilfe des Platzbedarfssatzes . . 39

4.2 Turingmaschinen, linear beschränkte Automaten . . . . . . . . . . . . . . . . 40 4.2.1 Nicht deterministisch erkennende TM . . . . . . . . . . . . . . . . . . 40 4.2.2 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.3 I. ℒ (Σ, TM) ⊆ ℒ_{0}(Σ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.4 II. ℒ_{0}(Σ) ⊆ ℒ (Σ, TM) . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2.5 Platzbedarf für Turingmaschinen . . . . . . . . . . . . . . . . . . . . . 43 4.2.6 Deterministische TM, k-Band-TM . . . . . . . . . . . . . . . . . . . . 44

4.3 Aufzählbare und entscheidbare Sprachen . . . . . . . . . . . . . . . . . . . . . 45 4.3.1 Aufzählbare Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.3.2 Entscheidbare Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5 Unentscheidbare Probleme 49 5.1 Das ∅-Problem von lbTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2 Schnittproblem für kontextfreie Grammatiken . . . . . . . . . . . . . . . . . . 50 5.3 Äquivalenzproblem für CFG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.4 Mehrdeutigkeitsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.5 Komplexität der entscheidbaren Probleme . . . . . . . . . . . . . . . . . . . . 51

5.5.1 Äquivalenzproblem bei Typ 3-Beschreibungen . . . . . . . . . . . . . . 51 5.5.2 Wortproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Kapitel 1

Alphabete, Wörter, Sprachen

1.1 Einführung

Zeichenreihe als Grundobjekt der Informatik • Präzisierung des Algorithmenbegriffs durch Turing-Maschinen

• Kommunikation mit dem Rechner über Tastatur

• automatische Datenverarbeitung (Bitfolgen) Grundbegriffe: Σ-Alphabet, nicht-leere endliche Menge. Beachte: Elemente eines Alphabets können aus Zeichen zusammengesetzt sein (Symbole in Programmiersprachen).

Σ  Alphabet
a ∈ Σ Buchstaben, Zeichen, Charakters, Symbol
Σ^{∗}  Menge der Wörter über Σ, Σ^{∗} := {(a_{1}a_{2} … a_{n}) | a_{i} ∈ Σ, n ∈ ℕ}
w ∈ Σ^{∗} Wort einer Sprache
L  Sprache, Menge von Wörtern
ε  leeres Wort (n = 0)

Beispiel: Bitstrings, Dezimalzahl, Programme, Textdatei

1.2 Operationen auf Menge von Worten

• Verkettung/Concatenation

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

Es gilt: – Verkettung ist assoziativ

– ε ist neutrales Element bezüglich ” · “: v · ε = ε · v = v

Sprachweise: ⟨Σ^{∗}, · , ε⟩ (Monoid, Halbgruppe mit ” 1 “)

• Länge eines Wortes w = a_{1}a_{2} … a_{n} ∈ Σ^{∗} ⇒ |w| = n (n ∈ ℕ) |ε| = 0 |w · v| = |w| + |v|

• Potenzen eines Wortes w^{0} := ε ⇐ muß neutrales Element sein w^{m+1} := ww^{m}

• ” Spiegelbild “ eines Wortes ε^{R} := ε (wa)^{R} := a(w)^{R}

1.3 Grundbegriffe

𝔭(Σ^{∗}) Potenzmenge von Σ^{∗}, Menge der formalen Sprachen über Σ 𝔭(Σ^{∗}) := {L | L ⊆ Σ^{∗}}

\begin{matrix}∅ ≠ \{ε\} \\ \{w_{1}, …, w_{n}\}, Σ^{∗} \\ Menge der Java − Programme \\ Menge der URLs \\ Menge der HTML − Dateien \end{matrix} \} Sprachen ∈ 𝔭(Σ^{∗})

1.4 Operationen auf 𝔭(Σ^{∗})

boolsche Operationen: L_{1} ∪ L_{2}, L_{1} ∩ L_{2}, \overline{L} := Σ^{∗}\L

Komplexprodukt: L_{1} · L_{2} := {w_{1} · w_{2}|w_{i} ∈ L_{i}} Beachte: ”Jeder mit jedem“, L · L := {w · v|w, v ∈ L} (nicht {w^{2}|w ∈ L})!

Potenzen einer Sprache: L^{0} := {ε} weil {ε}L = L L^{m+1} = LL^{m}

Stern einer Sprache: (Iteration / Repetition)

L^{∗} := ⋃_{n∈ℕ} L^{n}

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

Reguläre Ausdrücke und endliche Automaten

2.1 Reguläre Ausdrücke

endliche Beschreibung unendlicher Sprachen mit (Technik) Hilfe regulärer Operationen.

wichtig: Stern-Operator

2.1.1 Definition (Syntax)

Sei Σ ein Alphabet. Die Menge RegE(Σ) der regulären Ausdrücken über Σ ist induktiv definiert durch:

1. Λ ∈ RegE(Σ)

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

3. (α ∨ β) ∈ RegE(Σ) (Alternation)

4. (α · β) ∈ RegE(Σ) (Concatenation)

5. (α^{∗}) ∈ RegE(Σ) (Repetiton)

2.1.2 Vereinfachte Schreibweise

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

• Der · wird auch weggelassen.

Beispiel: a ∨ b^{∗}c statt (a ∨ ((b^{∗}) · c)). Beachte: RegE(Σ) ist selbst eine formale Sprache. RegE(Σ) ⊆ (Σ ∪ {Λ, (,), ·, ∨,^{∗} })^{∗}

8  2.2 Deterministische endliche Automaten

2.1.3 Definition (Semantik von RegE(Σ))

Ein regulärer Ausdruck α beschreibt eine formale Sprache. Statt L(α) schreiben wir hier �α� �.� : RegE(Σ) → 𝔭(Σ^{∗})

• �Λ� := ∅

• �a� := {a}

• �(α ∪ β)� := �a� ∪ �β�

• �(α · β)� := �a��β�

• �(α^{∗})� := �a�^{∗} Sprechweise: für w ∈ �α�, w ist ein Match für α, α ein Muster (Pattern). Beachte: Unterschied zwischen Syntax und Semantik

�a^{∗}� := {a^{n}|n ∈ ℕ}

Definition: Die Klasse RegL(Σ) der regulären Sprachen über Σ ist induktiv definiert durch • ∅, {a} ∈ RegL(Σ) für alle a ∈ Σ

• L, L′ ∈ RegL(Σ) ⇒ L ∪ L′, LL′, L^{∗} ∈ RegL(Σ) Also gilt: RegL(Σ) = �RegE(Σ)� (siehe man 7 regex unter Unix)

2.1.4 Standardprobleme für RegE(Σ)

1. Wortproblem (matching problem)

2. Äquivalenzproblem

3. Leerheitsproblem

2.2 Deterministische endliche Automaten

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 (Übertragungsfunktion) δ

• dem Anfangszustand q_{0} und

• der Endzustandsmenge F Bezeichnung: 𝔄 ∈ DFA(Σ), 𝔄 ∈ DFA(det. finite aut.) Definition: 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DFA(Σ) bestimmt die erweiterte Transitionsfunktion

\overline{δ} : Q × Σ^{∗} → Q

mit

\overline{δ}(q, ε) := q
\overline{δ}(q, wa) := δ(\overline{δ}(q, w), a) für w ∈ Σ^{∗}, a ∈ Σ

und die von 𝔄 erkannte Sprache

L(𝔄) : \{w ∈ Σ^{∗}|\overline{δ}(q_{0}, w) ∈ F \}

Bezeichnung: ℒ (Σ, DFA) Klasse der von deterministischen endlichen Automaten erkennbaren Sprachen über Σ. Ziel: ℒ (Σ, DFA) = Regℒ (Σ) nachweisen. wesentliches Hilfsmittel: nicht deterministische Automaten.

2.3 Nicht-deterministische endliche Automaten

Definition: Seien Q, Σ, q_{0} und F wie bei einem 𝔄 ∈ DFA, ferner Σ_{ϵ} := Σ ∪ {ϵ} und δ : Q × Σ_{ϵ} ↷ 𝔭(Q). Dann heißt

𝔄 =< Q, Σ, δ, q_{0}, F >

ein nicht-deterministischer endlicher Automat über Σ. Bezeichnung: NFA(Σ), NFA. Es folgt: DFA(Σ) ⊆ NFA(Σ).

Semantik eines 𝔄 ∈ NFA(Σ). Erweiterung der Semantik von DFA’s. Für T ⊆ Q ist die ε-Hülle (bez: ε(T)), induktiv durch

• T ⊆ ε(T)

• q ∈ ε(T) ↷ δ(q, ε) ⊆ ε(T)

Die erweiterte Transitionsfunktion

\overline{δ} : 𝔭(Q) × Σ^{∗} → 𝔭(Q)

ist induktiv definiert durch

• \overline{δ}(T, ε) := ε(T)

• \overline{δ}(T, w) := ε (⋃_{q∈\overline{δ}(T,w)} δ(q, a))

𝔄 =< Q, Σ, δ, q_{0}, F >∈ DFA(Σ)

δ : Q × Σ → Q \overline{δ} : Q × Σ^{∗} → Q \overline{δ}(q, ε) := q \overline{δ}(q, wa) := δ (\overline{δ}(q, w), a) L(𝔄) := \{w ∈ Σ^{∗}|\overline{δ}(q_{0}, w) ∈ F \}

𝔄 =< Q, Σ, δ, q_{0}, F >∈ NFA(Σ)

δ : Q × Σ_{ε} → 𝔭(Q) \overline{δ} : 𝔭(Q) × Σ^{∗} → 𝔭(Q) \overline{δ}(T, ε) = ε(T) \overline{δ}(T, wa) := ε (⋃_{q∈\overline{δ}(T,w)} δ(q, a)) Dann ist die durch 𝔄 erkannte Sprache definiert durch

L(𝔄) := \{w ∈ Σ^{∗}|\overline{δ}(\{q_{0}\}, w) ∩ F ≠ ∅\}

Beachte: Für DFAs stimmen beide Definitionen überein.

Grund: |δ(q, a)| = 1 für alle q ∈ Q, a ∈ Σ

|δ(q, ε)| = 0 für alle q ∈ Q, a ∈ Σ

2.3.1 Der Potenzmengenautomat

Definition: 𝔄^{P} :=< Q̂, Σ, δ̂, q̂_{0}, F̂ >∈ DFA(ε) ist der Potenzmengenautomat von 𝔄 =< Q, Σ, δ, q_{0}, F >∈ NFA(ε) wenn gilt:

• Q̂ = \{T ⊆ Q | T = \overline{δ} (\{q_{0}\}, w) , w ∈ Σ^{∗}\}

• δ̂: Q̂ × Σ → Q̂ δ̂(T, a) := \overline{δ}(T, a)^{1}

• q̂_{0} := ε({q_{0}})

• T ∈ F̂ ↷ T ∈ Q̂ und T ∪ F ≠ ∅ Lemma: Für 𝔄 ∈ NFA(Σ) gilt: L(𝔄) = L(𝔄^{P}) Beweis: (einfach wegen Defintion von 𝔄^{P})

w ∈ L(𝔄) ↶ ↷ \overline{δ}(\{q_{0}\}, w) ∪ F ≠ ∅
↶ ↷ \overline{δ̂}(\{q_{0}\}, w) ∈ F̂
↶ ↷ w ∈ L(𝔄^{P})
□

1T ⊆ Q̂ ↷ T = \overline{δ}(\{q_{0}\}, w)

ferner gilt: \overline{δ}(T, ε) = ε(T) = T \overline{δ}(T, a) = ε (⋃_{q∈\overline{δ}(T,ε)} δ(q_{0}, a)) = ε (⋃_{q∈T} δ(q, a)) = ε (⋃_{q∈\overline{δ}(\{q_{0}\},w)} δ(q, a)) = \overline{δ}(\{q_{0}\}, wa) ∈ Q̂

Kapitel 2. Reguläre Ausdrücke und endliche Automaten  11

2.4 Synthese und Analyse endlicher Automaten

2.4.1 Synthese

Konstruiere für α ∈ RegE(Σ) einen äquivalenten 𝔄(α) ∈ NFA(Σ), d.h. �α� = L(𝔄(α))

Der Algorithmus von Thompson Beh: 𝔄(α) hat genau 1 Endzustand q_{f} ≠ q_{0}, q_{0} ist Quelle, q_{f} ist Senke.

• 𝔄(Λ) :=⟶ •_{q_{0}} ⊚_{q_{f}}

• 𝔄(a) :=⟶ •_{q_{0}} ⟶^{a} ⊚_{q_{f}}

• 𝔄(α ∨ β) :=⟶ •_{q_{0}} \begin{aligned}& ∘ ∼ 𝔄(α) ∼ ⊚ \\ ↗^{ε} & & ↘^{ε} \\ ↘_{ε} & & ↗_{ε} \\ & ∘ ∼ 𝔄(β) ∼ ⊚ \end{aligned} ⊚_{q_{f}}

• 𝔄(αβ) :=⟶ •_{q_{0}} ∼ 𝔄(α) ∼ ∘ ∼ 𝔄(β) ∼ ⊚_{q_{f}} (Beachte: q_{0} Quelle, q_{f} Senke)

• 𝔄(α^{∗}) := [figure: → •_{q_{0}} ⟶^{ε} ∘ ∼ 𝔄(α) ∼ ⊚ ⟶^{ε} ⊚_{q_{f}}; ε; ε]

Offensichtlich gilt für jedes α ∈ RegE : �α� = L (𝔄(α)). Korollar: RegL ⊆ ℒ (Σ, DFA) (endlicher Automat ist beschreibbar durch eine Turingmaschine, die sich nur nach rechts bewegen kann).

2.4.2 Analyse

Konstruiere für 𝔄 ∈ DFA(Σ) einen α(𝔄) ∈ RegE(Σ) mit �α(𝔄)� = L(𝔄). 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DFA(Σ) 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_{ij}^{n} Somit genügt der Nachweis der Regularität der W_{ij}^{k}. Dies zeigen wir nun durch Induktion über k:

k = 0: W_{ij}^{0} ⊆ Σ ∪ {ε} (beachte: {ε} = �Λ^{∗}�)

↷ W_{ij}^{0} ist regulär. k − 1 → k: siehe Folie

Korollar: (Satz von Kleene) ℒ (Σ, DFA) = RegL(Σ) Korollar: RegL(Σ) ist abgeschlossen unter ∩ und ^{−}.

Beweis: (Idee):

Komplement: F′ : Q\F

L_{1} ∩ L_{2}: \overline{\overline{L_{1}} ∪ \overline{L_{2}}}
□

2.5 Das Pumping-Lemma

Hilfsmittel zum Nachweis nicht-regulärer Sprachen.

Satz: (Pumping-Lemma, Iterationslemma) Sei L ∈ RegL(Σ). Dann existiert k ∈ N, so daß für jedes x ∈ L mit |x| ≥ k eine Zerlegung

x = uvw

mit folgenden Eigenschaften existiert:

1. v ≠ ε

2. |uv| ≤ k

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

Beweis: Sei 𝔄 ∈ DFA(Σ) mit L(𝔄) = L und k = |Q|. Sei x ∈ L mit |x| ≥ k. Dann wird beim ”Erkennungslauf“ von x in 𝔄 mindestens 1 Zustand mehr als einmal besucht.

→ •_{q_{0}} ⟶^{u} •_{i}^{↶^{v}} ⟶^{w} ⊚

Sei i der erste solche ”Iterationszustand“ und v das Teilwort von dort bis zur ersten Wiederholung. Dann gelten offensichtlich 1 − 3.

□

Beachte: Das Pumping-Lemma beschreibt eine notwendige, aber nicht hinreichende Eigenschaft ⇝ Hilfsmittel zum Nachweis nicht regulärer Sprachen.

Beispiel: L = {a^{n}b^{n}|n ≥ 1} ∉ RegL({a, b}) Beweis: Angenommen, L ∈ RegL. Dann existiert k ∈ ℕ mit den Eigenschaften des Pumping-Lemma. (”Pumping Index“). Für x = a^{k}b^{k} muß dann eine Zerlegung existieren:

a^{k}b^{k} = uvw

mit v ≠ ε und |uv| ≤ k, hieraus folgt sofort v ∈ {a^{i}|i ≥ 1} und uw = a^{k−|v|}b^{k} ∉ L. Widerspruch!

□

2.6 Zustandsreduktion endlicher Automaten

Ziel: Konstruktion endlicher Automaten mit minimaler Zustandszahl

2.6.1 Ableitung

Definition: Für L ⊆ Σ^{∗} und w ∈ Σ^{∗} heißt

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

die Ableitung von L nach w.

Lemma: Sei L = L(𝔄) für 𝔄 =< Q, … >∈ DFA(Σ). Dann gilt für D(L) := {d_{w}(L)|w ∈ Σ^{∗}} : |D(L)| ≤ |Q| Beweis: Für q ∈ Q bezeichne

L(q) := L < Q, Σ, δ, q_{!}, F >

Dann gilt: d_{w}(L) = d_{w}(L(q_{o})) = L (\overline{δ}(q_{0}, w)).

2.6.2 Der Ableitungsautomat

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

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

• F := {d_{w}(L)|w ∈ L} also: ε ∈ d_{w}(L)

• δ (d_{w}(L), a) := d_{wa}(L)

Beachte: d_{w}(L) = d_{v}(L) ↷ d_{wa}(L) = d_{va}(L) Also ist die Definition von δ unabhängig vom Repräsentanten w.

Lemma: L(𝔄_{L}) = L (𝔄_{L} erkennt L). Beweis: w ∈ L(𝔄_{L}) ↶ ↷ \overline{δ}(q_{0}, w) ∈ F ↶ ↷d_{w}(L) ∈ F ↶ ↷ w ∈ L

□

Korollar:

1. Der Ableitungsautomat ist zustandsminimal.

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

Zustandsreduktion: Konstruktion eines zustandsminimalen Automaten aus einem gegebenen Automaten durch • Weglassen nicht erreichbarer Zustände

• Verschmelzen äquivalente Zustände Dabei heißt:

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

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

2.6.3 Der Faktorautomat

Definition: Für 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DFA(Σ) ist der Faktorautomat

𝔄/ ∼:=< Q̃, Σ, δ̃, q̃_{0}, F̃ >∈ DFA(Σ)

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 } ∩ Q̃

• δ̃([q], a) := [δ(q, a)] Beachte: q ∈ F.q ∼ q′ ↷ q′ ∈ F und q ∼ q′ ↶ ↷ δ(q, a) ∼ δ(q′, a) zeigen die Unabhängigkeit der Definition von den Repräsentanten. Lemma: Für 𝔄 ∈ DFA(Σ) gilt: 𝔄/ ∼= 𝔄_{L(𝔄)} (bis auf Zustandsnamen). Insbesondere ist 𝔄/ ∼ äquivalent zu 𝔄 und es folgt: Zustandsminimale Automaten sind bis auf Isomorphie eindeutig bestimmt. Beweis: β ([\overline{δ}(q_{0}, w)]) := d_{w}(L(𝔄))

• β ist unabhängig vom Repräsentanten w ∈ Σ^{∗}: \overline{δ}(q_{0}, v) ∼ \overline{δ}(q_{1}, w) ↷ L(\overline{δ}(q_{0}, v)) = L(\overline{δ}(q_{1}, w)) ↷ d_{w}(L(𝔄)) = d_{v}(L(𝔄))

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

• β ist strukturerhaltent:

– β([q_{0}]) = β ([\overline{δ}(q_{0}, ε)]) = d_{ε}(L(𝔄)) ”Anfangszustand im Ableitungsautomaten“ – \overline{δ}(q_{0}, w) = q ∈ F : β ([\overline{δ}(q_{0}, w)]) = d_{w}(L(𝔄)) ”Endzustand vom Ableitungsautoma-

ten“, weil w ∈ L(𝔄).

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

□

Zustandsreduktion • Weglassen nicht erreichbarer Zustände

• Verschmelzen äquivalenter Zustände k-Äquivalenz und k-Äquivalenzmatrizen

Definition: Sei 𝔄 =< Q, Σ, δ, q_{0}, F >∈ DFA 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^{2} → {0, 1} mit r^{k}(q_{1}, q_{2}) = 1 : ↶ ↷q_{1} ∼^{k} q_{2}. Sie können als Matrizen R^{k} = (r^{k}(q_{i}, q_{j}))_{i,j=1}^{n} mit n = |Q| dargestellt werden. Beachte: r^{k}(q_{i}, q_{j}) = r^{k}(q_{j}, q_{i})

Berechnung der k-Äquivalenz Matrizen

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

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

Lemma: Es gibt ein k ∈ ℕ, so daß für alle n ∈ ℕ gilt: R^{k} = R^{k+n} Beweis: Da r^{k}(q_{i}, q_{0}) = 0 ↷ r^{k+1}(q_{i}, q_{0}) = 0, muß es ein k ∈ ℕ geben, mit r^{k} = r^{k+1}. Dann muß auch r^{k} = r^{k+n} für alle n ∈ ℕ gelten:

Sei r^{k}(q_{1}, q_{2}) = r^{k+1}(q_{1}, q_{2}) = 1, also q_{1} ∼^{k} q_{2} und q_{1} ∼^{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 >∈ DFA, jeder q ∈ Q 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 a ∈ Σ teste, ob {δ(q, a), δ(q′, a)} markiert. Wenn ja: markiere {q, q′}.

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

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

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

2.7 Entscheidbare Eigenschaften

2.7.1 Deterministische endliche Automaten

• Wortproblem: w ∈ L(𝔄)? für w ∈ Σ^{∗} und Q ∈ DFA(Σ) Durch Eingabe in |w| + 1 Schritten entscheidbar.

• ∅-Problem (Leerheitsproblem): L(𝔄) = ∅? für 𝔄 ∈ DFA(Σ) Durch Eingabe alle Wörter w mit |w| < |Q| entscheidbar. Beachte: w ∈ L(𝔄), |w| ≥ |Q| ↷ ∃v ∈ L(𝔄), |v| < |w| (Vergleiche Beweis zum Pumping-Lemma [2.5]) Verfahren: testen, ob F von q_{0} erreichbar. Durchführung in ρ(|Q|^{2})-Zeit.

• ∼-Problem: L(𝔄) = L(𝔄′)? für 𝔄, 𝔄′ ∈ DFA(Σ)

Reduktion auf ∅-Problem: L(𝔄) = L(𝔄′)↶ ↷L(𝔄) ⊆ L(𝔄′) und L(𝔄′) ⊆ L(𝔄)↶ ↷L(𝔄)∩\overline{L(𝔄′)} = ∅ und L(A′)∩\overline{L(𝔄)} = ∅ 2 Automaten mit |Q| · |Q′| Zuständen auf ∅ testen. ∼-Problem in ρ ((|Q| · |Q′|)^{2})-Zeit lösbar.

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

Durch Transformation in DFA’s sind alle 3 Probleme entscheidbar. Aber der Aufwand steigt:

Wortproblem: ρ(|α| · |w|) Zeit, bzw. ρ(|Q| · |w|).

∅-Problem: NFA wie DFA.

RegE ↦ NFA in ρ(|α|) Zeit mit |Q| ≤ 2|α|.

∼-Problem: NP-hart.

Grund: Exponentieller Aufwand der P-Mengen-Konstruktion.

2.8 Anwendung

1. Endliche Automaten mit Ausgabe.

Beispiel: Mealy-Automaten, Moore-Automaten. Beschreibung von Schaltwerken.

2. Wortsuche in Texten (siehe Folie 2.15).

2 Implementierungstechniken:

(a) NFA-Methode: u = aebwewebba bestimmt einen Lauf. {a}a{1}e{1, 5}b{1, 6}w{1, 2}e{1, 3, 5}w{1, 2}e{1, 3, 5}b{1, 4, 6} …

(b) DFA-Methode

3. Verteilte Systeme / Parallele Prozesse (siehe Folie 2.17)

4. Erweiterte reguläre Ausdrücke: ∩,^{−} Wichtig für Suchmaschinen.

5. Zusammenhang zwischen endlichen Automaten und iterativen Programmen (Flußdiagramme) bzw. regulären Ausdrücken und WHILE -Programmen.

18  2.8 Anwendung

Kontextfreie Grammatiken und Kellerautomaten

Anwendung: Compilerbau (Syntaxanalyse), XML.

3.1 Kontextfreie Grammatiken

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

3.1.1 Bezeichnungen und Konventionen

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

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 durch

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

und damit die von G erzeugte Sprache L(G) := {w ∈ Σ^{∗}|S ⇒^{∗}_{G} w} mit ⇒^{∗}_{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}} α ⋯ ⇒_{π_{n}} α_{n} = w (n ≥ 1). Bezeichnung: CFL(Σ) := {L ⊆ Σ^{∗}| ∃G ∈ CFG(Σ) : L(G) = L}

3.1.2 Ableitungsbäume

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

1. Eine Regel π = A → X_{1} … X_{n} bestimmt den Regelbaum A_{/\_{X_{1}...Xn}} , Spezialfall: A_{|_{ε}} für

n = 0.

2. Eine Ableitung A ⇒ α_{1} … ⇒ α_{n} bestimmt den Ableitungsbaum durch entsprechendes Verkleben der Regelbäume.

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. Ein Compiler bestimmt zu einem Programm (geben als Zeichenreihe) einen Ableitungsbaum als Basis der Codegenerierung. (weitere Anwendungen: HTML, XML).

3.1.3 Rechts- und Linksableitung

Definition: Eine Ableitung heißt Rechtsableitung (Linksableitung), wenn jeder Ableitungsschritt (α, π, β) ein Rechtsableitungsschritt, d.h. β ∈ Σ^{∗} (, bzw. ein Linksableitungsschritt, d.h. α ∈ Σ^{∗}).

Schreibweise: ⇒_{r} bzw. ⇒_{l} Folgerung: Ein Baum hat genau eine Rechts- bzw. genau eine Linksableitung. (siehe Folie 3.4)

3.1.4 Ein- und Mehrdeutigkeit

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: ↶ ↷G nicht eindeutig.

Bemerkung: Syntaktische Mehrdeutigkeit (fehlende Klammern) wird durch Präzedenzregeln beseitigt.

3.2 Einseitig lineare Grammatiken

Definition: Sei G =< N, Σ, P, S >∈ CFG.

• Dann heißt diese Grammatik G linkslinear, wenn für jedes π = A → α gilt: α = Bw oder α = w.

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

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

Ziel: {L(G)|G :, linkslinear} = {L(G)|G :, rechtslinear} = {L(G)|G einseitig − linear} = RegL Satz: ℒ (Σ, NFA) = {L ⊆ Σ^{∗}|L = L(G), G rechtslinear}. Beweis:

”⊇“ Sei G =< N, Σ, P, S > rechtslinear. Auffassung von G als 𝔄(G) =< Q, Σ, δ, q_{0}, F >∈ NFA: Q := N ∪ {q_{f}} (q_{f} neu) q_{0} := S F := {q_{f}} δ(A, w) ∋ B falls A → wB ∈ P δ(A, w) ∋ q_{f} falls A → w ∈ P Offensichtlich gilt: L(G) = L(𝔄(G)). Beachte: Wortübergänge durch Zwischenzustände beseitigen (siehe Folie 3.5).

”⊆“ 𝔄 =< Q, Σ, δ, q_{0}, F >∈ NFA kann ebenso als rechtslineare Grammatik aufgefasst werden.

∘_{q} ⟶^{a} ⊚_{q′}  ↦  q → aq′|q′ → ε

q ∈ F ↦ neue Regel q → ε

□

Korollar: RegL(Σ) ⊆ CFL(Σ) := ℒ (Σ, CFG)

Für |Σ| ≥ 2 ist diese Inklusion echt, weil {a^{n}b^{n}|n ∈ N} = L(G) mit G = (S → aSb|ε). Lemma: L ∈ RegL(Σ) ↷ L^{R} ∈ RegL(Σ) Beweis: Zu 𝔄 ∈ DFA(Σ) konstruieren wir 𝔄^{R} ∈ NFA(Σ) mit L(𝔄^{R}) = L(𝔄)^{R}. Idee: ersetze •_{q} ⟶^{a} •_{q′} durch •_{q} ⟵^{q} •_{q′},

sowie → •_{q_{0}} durch ⊚_{q_{0}}

und ergänze diesen NFA durch

→ •_{q_{0}} _{↗^{ε}}⊚_{q_{1}} ; ⋮ ; ^{↘_{ε}}⊚_{q_{n}} ∀q_{i} ∈ F

□

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

Beweis: L rechtslinear ↶ ↷L^{R} rechtslinear ↶ ↷L = L^{RR} linkslinear (Regeln spiegeln). (siehe Folie 3.6)

□

3.3 Normalformen von Kontextfreien Grammatiken

Hilfsmittel: Vorgänger von Satzformen.

α, β ∈ X^{∗} , X = Σ ∪ N

α ⇒ β α direkte Vorgänger von β α ⇒^{∗} β α Vorgänger von β

Definition: Sei G =< N, Σ, P, S >∈ CFG und L ⊆ X^{∗}. Dann ist

die direkte Vorgängermenge von L definiert durch

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

der Vorgängerabschluß von L definiert durch

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

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

Beweis: Sei 𝔄 =< Q, X, δ, q_{0}, F >∈ NFA mit L(𝔄) = L. Konstruiere 𝔄′ =< Q, X, δ′, q_{0}, F >∈ NFA durch

1. δ(q, a) ⊆ δ′(q, a) ∀(q, a) ∈ Q × X_{ε}

2. Wenn A → α ∈ P und \overline{δ′}(\{q\}, α) ∋ q′, so füge δ′(q, A) ∋ q′ hinzu. Ergänze δ′ um solche Transitionen, solange dies möglich ist. Der Prozeß terminiert, weil Q und X endlich sind.

Die Korrektheit ist offensichtlich. (Erläuterungen siehe Folie 3.7).

□

Bemerkung: Die Zeitkomplexität der Automatenkonstruktion liegt in ρ(|Q|^{6}).

Definition: Sei G ∈ CFG(Σ) und A ∈ N.

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

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

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

A erreichbar ↶ ↷S ∈ \underline{Pre}^{∗}(X^{∗}AX^{∗})

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

Lemma: Jedes G ∈ CFG(Σ) läßt sich in eine äquivalente reduzierte Grammatik G′ ∈ CFG(Σ) transformieren.

Beweis: Stelle für jedes A ∈ N fest, ob A produktiv und erreichbar. Unterscheide zwei Fälle:

1. S ist nicht produktiv. Wähle: P′ = ∅.

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

□

Korollar: Das ∅-Problem von CFG’s ist entscheidbar.

3.3.1 Elimination von ε-Regeln

Definition: G ∈ CFG(Σ) heißt ε-frei: ↶ ↷

A → ε ∈ P ↷ A = S und S auf keiner rechten Regelseite.

Lemma: X ⇒^{∗} ε ↶ ↷ X ∈ \underline{Pre}^{∗}(\{ε\}).

Satz: Jedes G ∈ CFG(Σ) läßt sich in eine äquivalente ε-freie Grammatik G′ ∈ CFG(Σ) transformieren.

Beweis: Konstruiere mit \underline{Pre}^{∗}(\{ε\}) die Menge

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

und damit G′ =< N′, Σ, P′, S′ >∈ CFG:

• N′ := N ·∪ {S′} (neues Startsymbol)

• P′ := {S′ → S} ∪ {S′ → ε | S ∈ N_{ε}}

∪ {A → X_{1} … X_{k} | k ≥ 1, X_{i} ∈ (N ∪ Σ), ∃α_{0}, …, α_{k} ∈ N_{ε}^{∗} : A → α_{0}X_{1}α_{1} … X_{k}α_{k} ∈ P } Beachte: Wegen k ≥ 1 entfallen ε-Regeln und G′ ist ε-frei. Bleibt zu zeigen: L(G′) = L(G)

1. w = ε : ε ∈ L(G′) ↶ ↷ S′ → ε ∈ P′ ↶ ↷ S ∈ N_{ε}

↶ ↷S ⇒^{∗}_{G} ε ↶ ↷ ε ∈ L(G)

2. w ≠ ε

(a) w ∈ L(G′) ↷ S ⇒^{∗}_{G′} w ↷ S ⇒^{∗}_{G} w ↷ w ∈ L(G)

weil Ableitung in G′ mit L_{i} ⇒^{∗} ε aufgefüllt werden kann.

(b) w ∈ L(G): Wir zeigen durch Induktion über die Ableitungslänge r, daß gilt:

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

r = 1 : A → w, w ≠ ε ↷ A → w ∈ P

↷ A → w ∈ P′ ↷ A ⇒^{∗}_{G′} w

r → r + 1: A ⇒_{G} X_{1} … X_{k} ⇒^{r}_{G} w ≠ ε

Dann existieren Abbleitungen X_{i} ⇒^{r_{i}}_{G} w_{i} mit w_{1} … w_{k}, r_{i} ≤ r Falls w_{i} = ε, so X_{i} ∈ N_{ε}. Durch entsprechendes Löschen entsteht

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

□

Beispiel: Transformation in ε-freie Grammatik G′ ∈ CFG

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

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

• P′ := {S′ → S} ∪ {S′ → ε|S ∈ N_{ε}} ∪ {A → X_{1} … X_{k}|k ≥ 1, X_{i} ∈ (N ∪ Σ), ∃α_{0}, …, α_{k} ∈ N_{ε}^{∗} : A → α_{0}X_{1}α_{1} … X_{k}α_{k} ∈ P }

Beispiel:

A → aBa B → b|ε

wird transformiert nach

A → aBa|aa B → b

Definition: Eine Regel der Form A → B heißt Kettenregel. Satz: Jedes G =< N, Σ, P, S >∈ CFG läßt sich in eine äquivalente ε-freie Grammatik G′ =< N′, Σ, P′, S′ >∈ CFG ohne Kettenregeln transformieren.

Beweis: o.B.d.A sei G ε-frei. Dann definieren wir G′ =< N, Σ, P′, S > durch

1nichtleeres Wort

Kapitel 3. Kontextfreie Grammatiken und Kellerautomaten  25

A → α ∈ P′ : ↶ ↷α ≠ N und es gibt B → α ∈ P mit A ∈ \underline{Pre}^{∗}(B). Die Korrektheit folgt, da wegen ε-Freiheit von G gilt:

A ∈ \underline{Pre}^{∗}(B) ↶ ↷ A ⇒ A_{1} ⇒ A_{2} … ⇒ A_{n} = B

□

3.3.2 Die Chomsky-Normalform

Definition: G =< N, Σ, P, S >∈ CFG ist in Chomsky-Normalform (G ∈ CNF): ↶ ↷ Jede Regel von P hat die Form

• A → BC mit B, C ∈ N oder • A → a mit a ∈ Σ

• S → ε Im letzten Fall darf S auf keiner rechten Regelseite auftreten. Satz: Jedes G =< N, Σ, P, S >∈ CFG läßt sich in eine äquivalente Grammatik G′ ∈ CNF transformieren. Beweis: o.B.d.A. sei G ε-frei und ohne Kettenregeln. Außerdem können wir annehmen, daß für k ≥ 2 gilt

A → X_{1} … X_{k} ∈ P ↷ X_{i} ∈ N

Denn, X_{i} = a kann ersetzt werden durch neues C_{i} ∈ N unter hinzufügen von C_{→}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_{2} → B_{3}C_{3}
⋮ ⋮
C_{k−2} → B_{k−1}B_{k}

mit neuen ℕ-Symbolen C_{1}, …, C_{k−2}

□

3.3.3 Die Greibach Normalform, Linksrekursion

Definition: G =< N, Σ, P, S >∈ CFG ist in Greibach-Normalform (G ∈ GNF): ↶ ↷ Jede Regel von der Form

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

26  3.4 Abschlußeigenschaften von CFL, Pumping-Lemma

• A → a

• S → ε (S auf keiner rechten Regelseite) Satz: Jede G ∈ CFG läßt sich in eine äquivalente Grammatik G′ ∈ CFG transformieren. Beweis: Elimination linksrekursiver Nichtterminalsymbole. Definition: A ∈ N linksrekursiv: ↶ ↷A ⇒^{+} Aα für ein α ∈ X^{∗} Spezialfall: Direkte Linksrekursion

\begin{matrix}Seien & A → Aα_{1}|Aα_{2}| … |Aα_{r} \\ und & A → β_{1}| … |β_{s} \end{matrix} \} alle Regeln der Form A → Aα(α_{i} ≠ ε)

Dann läßt sich dieser Regelsatz äquivalent ersetzen durch A → β_{1}Z| … b_{s}Z|β_{1}| … |β_{s} Z → α_{1}Z| … α_{r}Z|α_{1}| … |α_{r} Grund:

\begin{matrix}A \\ \begin{matrix}A \\ A ; \begin{aligned}β_{i} \\ & α_{i_{r}} \end{aligned} & α_{i_{2}} \end{matrix} & α_{i_{1}} \end{matrix} wird simuliert durch A ; β_{i} ; Z ; α_{i_{n}} ; Z ; α_{i_{n−1}} ; \begin{matrix}Z \\ α_{1} \end{matrix}

Bemerkung: Linksrekursion stört die Syntaxanalyse

3.4 Abschlußeigenschaften von CFL, Pumping-Lemma

Hilfsmittel: Substitutionssatz, Pumping-Lemma Definition: Sei Σ ein Alphabet und für jedes a ∈ Σ, Σ_{a} ein weiteres Alphabet. Dann heißt ϕ : 𝔭(Σ^{∗}) → 𝔭((⋃_{a∈Sigma} Σ_{a})^{∗}) eine Substitutionsabbildung, falls

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

• ϕ({ε}) = {ε} • ϕ({a_{1} … a_{k}}) = ϕ({α_{1}}) · ϕ({α_{2}}) · . . . · ϕ({α_{k}})

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

ϕ ist also durch die ”Substitutionssprachen“ ϕ({a}) bestimmt. Statt ϕ({w}) schreiben wir auch ϕ(w).

3.4.1 Substitutionssatz

Sei ϕ : 𝔭(Σ^{∗}) → 𝔭(⋃_{a∈Σ} Σ_{a})^{∗} eine Substitutionsabbildung. Dann gilt: L ∈ CFL(Σ), ϕ(a) ∈ CFL(Σ_{a}) ∀a ∈ Σ ↷ ϕ(L) ∈ CFL(⋃_{a∈Σ} Σ_{a})

Beweis: Kombination kontextfreier Grammatiken mit disjunkten Nichtterminal-Symbolmengen. Ersetze a ∈ Σ durch S_{a}.

Korollar: CFL(Σ) ist unter regulären Operationen abgeschlossen.

Beweis: Seien L_{1}, L_{2} ∈ CFL(Σ) und a, b Buchstaben mit ϕ(a) := L_{1} und ϕ(b) := L_{2}(Σ = {a, b}). Dann gilt:

ϕ({a, b}) = L_{1} ∪ L_{2}
ϕ(ab) = L_{1}L_{2}
ϕ({a}^{∗}) = L_{1}^{∗}

Da {a, b}, {ab}, {a}^{∗} ∈ CFL({a, b}) folgt die Behauptung.

□

3.4.2 Pumping-Lemma (für CFL)

uvwxy-Theorem

Sei L ∈ CFL(Σ). 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 für alle i ∈ ℕ.

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 [figure: Z; S] hat mind. 2^{n} Blätter.

Da G ∈ CNF, muß ein Pfad p maximaler Länge mindestens n + 1 Kanten, also n + 2 Knoten haben. p besitzt daher mindestens n + 1 Knoten, markiert durch Nichtterminalsymbole, also 2 Knoten mit gleichem Nichtterminal-Symbol.

[figure: A; A; S; u; v; w; x; y]

Wähle auf p den letzten Knoten, dessen Marke A ∈ N sich wiederholt. Dann hat sein Teilbaum höchstens 2^{n} = k Blätter.

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

• vx ≠ ε

• uv^{i}wx^{i}y ∈ L für alle i ∈ ℕ_{0} wegen der Ersetzbarkeit der A-Teilbäume.

□

Lemma: L = {a^{n}b^{n}c^{n}|n ≥ 1} ∉ CFL({a, b, c}).

Beweis: (durch Widerspruch) Wäre L kontextfrei, so existiert ein Pumping-Index k ∈ ℕ und für a^{k}b^{k}c^{k} eine Zerlegung uvwxy mit den Pumping-Eigenschaften, insbesondere uwy ∈ L. Da vx ≠ ε, muß |uwy| < 3k sein. Da |vwx| ≤ k, kann vx nicht gleichzeitig ein a und ein c enthalten. Also muß uwy = a^{k} … oder uwx = … c^{k}. Dies ist ein Widerspruch

□

Satz: CFL ist weder unter Durchschnitt, noch unter Komplement abgeschlossen.

Beweis: \{ \begin{matrix}S → Sc|Ac \\ A → aAb|ab \end{matrix} \} und \{ \begin{matrix}S → aS|aA \\ A → bAc|bc \end{matrix} \} erzeugen die Sprachen \{a^{n}b^{n}c^{p}|n, p ≥ 1\},

bzw. {a^{p}b^{n}c^{n}|n, p ≥ 1}, deren Schnitt nicht kontextfrei ist. Da CFL unter ∪ abgeschlossen ist, kann CFL nicht unter komplement abgeschlossen sein, denn:

L_{1} ∩ L_{2} = \overline{\overline{L_{1}} ∪ \overline{L_{2}}}
□

3.5 Entscheidbare Eigenschaften von CFG

Satz: Das Wortproblem und das ∅-Problem sind für CFG entscheidbar.

Beweis:

w ∈ L(G) ↶ ↷ S ∈ \underline{Pre}^{∗}(\{w\})
L(G) = ∅ ↶ ↷ S ∉ \underline{Pre}^{∗}(Σ^{∗})
□

Bemerkung:

1. Das Wortproblem ist in ρ(n^{3}) entscheidbar (siehe: CYK-Algorithmus [3.7])

2. Das Äquivalenzproblem ist nicht entscheidbar.

3.6 Kellerautomaten

Kellerspeicher (Stack, Stapel, push down store): wichtige Datenstruktur für die sequentielle Behanlung strukturierter Objekte

Charakterisierung von CFL durch nicht-deterministische Kellerautomaten, keine Äquivalenz zu deterministischen Kellerautomaten

Bedeutung deterministischer Kellerautomaten für den Compilerbau:

• Syntaxanalyse

• Datenkeller

• Prozedurkeller (Speichertechnik für rekursive Prozeduren)

Wir betrachten nun zusätzlich zum Eingabeband und dem Zustand noch das Symbol, welches wir auf dem Kellerspeicher lesen. Der Kellerspeicher ist ein Stapelspeicher, auf dem wir oben Elemente hinzufügen und lesen könenn (LIFO-Prinzip: Last In - First Out). Definition: Seien Q, Σ, Γ nicht-leere endlichen Mengen von Zuständen, Eingabe- und Kellersymbolen; ferner: q_{0} ∈ Q Anfangszustand, Z_{0} ∈ Γ Kellerstartsymbol und δ : Q × Σ_{ε} × Γ → 𝔭_{f}(Q × Γ^{∗}) Transitionsfunktion und F ⊆ Q Entzustandsmenge.

Dann heißt 𝔄 =< Q, Σ, Γ, δ, q_{0}, Z_{0}, F > ein Kellerautomat über Σ, Bezeichnung: 𝔄 ∈ PDA(Σ).

3.6.1 Semantik

Konfigurationsmenge Q × Σ^{∗} × Γ^{∗} (Kellerspitze links)

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′, β)

Startkonfiguration für w ∈ Σ^{∗} : (q_{0}, w, Z_{0})

3.6.2 Die von 𝔄 erkannten Sprachen

L(𝔄, F) := {w ∈ Σ^{∗}|(q_{0}, w, Z_{0}) ⊢^{∗} (q, ε, α), q ∈ F }
L(𝔄, ε) := {w ∈ Σ^{∗}|(q_{0}, w, Z_{0}) ⊢^{∗} (q, ε, ε)}
L(𝔄, F, ε) := {w ∈ Σ^{∗}|(q_{0}, w, Z_{0}) ⊢^{∗} (q, ε, ε), q ∈ F }

Bemerkung: Die Erkennungsarten sind äquivalent. (Stichwort: Simulation)

ℒ (Σ, PDA) := {L ⊆ Σ^{∗}|∃𝔄 ∈ PDA(Σ), L = L(𝔄, F)}

(Beispiel: siehe Folie 3.8)

Ziel: CFL(Σ) = L(Σ, PDA) Satz: CFL(Σ) ⊆ ℒ (Σ, PDA)

Beweis: Sei G =< N, Σ, P, S >∈ CFG. Dann definiere 𝔄_{G} =< Q, Σ, Γ, δ, q_{0}, Z_{0}, F >∈ PDA(Σ) durch Q := {q}, Γ := N ∪ Σ, Z_{0} := S, q_{0} = q, F = ∅ δ(q, a, a) := {(q, ε) für alle a ∈ Σ (Vergleichsschritt) δ(q, ε, A) := {(q, β)|A → β ∈ P } für alle A ∈ N (Ableitungsschritt)

Behauptung: L(G) = L(𝔄_{G}, ε) (*) A ⇒^{∗} w ↶ ↷ (q, wv, Aα) ⊢^{∗} (q, v, a)

”↷“ Induktion über die Ableitungslänge 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_{2} … v_{r} n_{i} ≤ n, so daß nach Induktionsvoraussetzung:

(q, v_{0}w_{1}v_{1} … v_{r}v, Aα) ⊢ (q_{0}, v_{0}w_{1} … v_{r}v, v_{0}A_{1} … v_{r}α) ⊢^{∗} (q, v, α)

”↶“ Induktion über die Länge der Berechnung (Übung)

Es folgt: L(G) = L(𝔄_{G}, ε)

□

(Beispiel siehe Folie 3.9)

Satz: ℒ (Σ, PDA) ⊆ CFL(Σ) Beweis: ” Schöning “

Korollar: CFL ist unter Schnitt mit regulären Sprachen abgeschlossen. Beweis: Für L ∈ CFL(Σ) und R ∈ RegL(Σ) existiert 𝔄_{L} ∈ PDA(Σ) und 𝔄_{R} ∈ DFA(Σ) mit L = L(𝔄_{L}) und R = L(𝔄_{R}). Konstruiere 𝔄_{L}∥𝔄_{R} ∈ PDA(Σ)

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}

□

Ziel: Der Deklarationszwang von Variablen ist keine kontextfreie Eigenschaft.

Lemma: L = {ww|w ∈ {a, b}^{+}} ∉ CFL Beweis: Zunächst zeigen wir L′ = {a^{m}b^{n}a^{m}b^{n}|m, n ≥ 1} ∉ CFL Wäre L′ ∈ CFL, so ergäbe sich mit Pumping-Index k: a^{k}b^{k}a^{k}b^{k} = uvwxy mit |vwx| ≤ k, vx ≠ ε also auch uvy ∈ L′. Dies is ein Widerspruch, weil die Zahl der vorderen und hinteren a’s bzw. b’s nicht mehr gleich ist. L′ = L ∩ {a}^{+}{b}^{+}{a}^{+}{b}^{+} ist also ebenfalls nicht kontextfrei.

Korollar: Die Menge P der Pascal-Programme ist nicht kontextfrei.

Beweis: L := { program T (output); var w: integer; begin w := 1 end. |w ∈ {a, b}^{+}} Also: L ⊆ P R sei bestimmt durch den regulären Ausdruck program T (output); var (a ∨ b)^{+}; begin (a ∨ b)^{+} := 1 end. Dann gilt: L = P ∩ R. h sei eine Substitutionsabbildung mit

h(a) = a, h(b) = b, h(x) = ε sonst

Dann h(L) = {ww|w ∈ {a, b}^{+}} ∉ CFL, was einen Widerspruch zu der Annahme P ∈ CFL darstellt.

□

3.6.3 Deterministische Kellerautomaten

Definition: 𝔄 =< Q, Σ, Γ, δ, q_{0}, Z_{0}, F >∈ PDA(Σ) heißt deterministisch, in Zeichen: 𝔄 ∈ DPDA(Σ), wenn gilt:

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

2. |δ(q, ε, Z)| = 1 ↷ |δ(q, a, Z)| = 0

Folgerung: Zu jeder Konfiguration (q, w, α) gibt es höchstens eine Folgekonfiguration. ε-Schritte möglich.

L(𝔄) := L(𝔄, F)
ℒ (Σ, DPDA) := ℒ (Σ, DPDA, F) ⫌ ℒ (Σ, DPDA, ε)

Satz: ℒ (Σ, DPDA) ist unter Komplement abgeschlossen. (Schade: da unerwünscht)

Beweis: (Idee): Zu jedem 𝔄 ∈ DPDA(Σ) ist ein äquivalenter 𝔄̃ ∈ DPDA(Σ) konstruierbar, so daß gilt: Für jedes w ∈ Σ^{∗} gibt es q ∈ Q̃ und α ∈ Γ̃^{∗} mit

(q̃_{0}, w, Z̃_{0}) ⊢^{∗} (q, ε, α) (Endkonfiguration)

Dazu müssen Schleifenkonfigurationen eliminiert werden.

(q, w, α) ∈ Q × Σ^{∗} × Γ^{∗} heißt Schleifenkonfiguration, falls für jedes i ∈ ℕ ein q_{i} ∈ Q und ein

α_{i} ∈ Γ^{∗} existiert, so daß |α_{i}| ≥ |α| und (q, w, α) ⊢^{i} (q_{i}, w, α_{i}).

Diese Eigenschaft ist entscheidbar (Kern des Beweises) ↷ Elimination.

□

Folgerung: ℒ (Σ, DPDA) ⫋ ℒ (Σ, PDA) = CFL

3.7 Der Algorithmus von Cocke, Yonnger und Kasami

effiziente Lösung des Wortproblems für beliebige CFL, dynamische Programmierung, ρ(n^{3})- Zeit, ρ(n^{2})-Platz. O.B.d.A. G ∈ CNF (auf beliebige CFG ü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}

Berechnung von N_{1n}: Bestimme N_{11} N_{22} …  N_{nn} dann  N_{12} N_{23}  N_{n−1} N_{n} dann  N_{13} N_{24} … N_{n−2} N_{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}

(siehe auch Folie 3.10, Beispiel 3.11)

3.7.1 Komplexität des CYK-Algorithmus

Zeit äußere “for i“-Schleife 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}. Also ρ(n^{3}).

Platz ρ(n^{2})

Kapitel 3. Kontextfreie Grammatiken und Kellerautomaten  33

3.8 Erweiterte kontextfreie Grammatiken (EBNF)

höherer Beschreibungskomfort durch die Verwendug von regulären Ausdrücke als rechte Regelseiten; äquivalente Erweiterung. Definition: G =< N, Σ, P, S > heißt erweiterte CFG, in Zeichen: G ∈ ECFG, wenn < N, Σ, ∅, S >∈ CFG und P : N → RegE(N ∪ Σ). Schreibweise: A → α, falls α = P (A) Semantik: P repräsentiert die Regelmenge P̃ mit A → α̃ ∈ P̃ : ↶ ↷α̃ ∈ �P (A)�. Beachte: P̃ ist im allgemeinen unendlich. L(G) := L (< N, Σ, P̃, S >) Satz: CFL(Σ) = ℒ (Σ, ECFG) Beweis: (Idee) “⊆“: nach Definition. “⊇“: Transformation von ECFG nach CFG durch Elimination regulärer Ausdrücke: Disjunktion: Regelalternation Stern: neues Nichtterminal mit A → αA|ε

□

(siehe auch Folie 3.12)

3.9 Rekursive endliche Automaten (Syntaxdiagramme)

Syntaxdiagramme entsprechen endlichen Automaten die sich rekursiv aufrufen können (Beispiel siehe Folien 3.13 und 3.14). Dabei sind neben den gewohnten Transitionen q_{1} ⟶^{a} q_{2} auch Transitionen der Form q_{1} → q_{3} → q_{2} möglich. Definition: 𝔄 =< Q, Σ, δ, q_{0}, F > heißt rekursiver endlicher Automat über Σ, falls

δ : Q × (Σ_{ε} ∪ Q) → 𝔭(𝔄)

und sonst wie ein endlicher Automat. Bezeichnung: 𝔄 ∈ RFA(Σ).

3.9.1 Semantik

Konfiguration: Q × Σ^{∗} Transitionsrelation: ⊢⊆ (Q × Σ^{∗})^{2} definiert als kleinste Relation für die gilt:

1. p ∈ δ(q, a) ↶ ↷ (q, aw) ⊢ (p, w)

2. p ∈ δ(q, ε) ↶ ↷ (q, w) ⊢ (p, w)

3. p ∈ δ(q, r), (r, w) ⊢^{∗} (s, v), s ∈ F ↶ ↷ (q, w) ⊢ (p, v)

L(𝔄) := {w ∈ Σ^{∗}|(q_{0}, w) ⊢ (p, ε), p ∈ F } Beispiel für den Erkennungslauf siehe Folie 3.15.

Satz: ℒ (Σ, RFA) = ℒ (Σ, PDA) Beweis:

”⊆“ 𝔄 =< Q, Σ, δ, q_{0}, F >∈ RFA(Σ). Simulation von 𝔄 durch 𝔄′ < Q, Σ, Q, δ′, q_{0}, q_{0}, F >∈ PDA(Σ) Idee: Keller für ”Rücksprungadressen“ verwenden:

δ′ : Q × Σ_{ε} × Q → 𝔭_{f}(Q × Q^{∗}), p ∈ δ(q, a)

δ′(q, a, s) := {(p, s)|p ∈ δ(q, a)}
δ′(q, ε, s) := {(p, s)|p ∈ δ(q, ε)}
∪{(r, ps)|p ∈ δ(q, r)}
∪{s, ε)|q ∈ F }

”⊇“ Für L ∈ ℒ (Σ, PDA) ∃G =< N, Z, P, S >∈ CFG mit L = L(G).

Konstruiere 𝔄 =< Q, Σ, δ, q_{0}, F >∈ RFA durch: Q := N ∪ {q_{f}}, q_{0} := S, F = {q_{f}} und

C ∈ δ(A, B) falls A → BC
q_{f} ∈ δ(A, a) falls A → q
q_{f} ∈ δ(S, ε) falls S → ε
□

Turingmaschinen und aufzählbare Sprachen

4.1 Chomsky-Grammatiken

Verallgemeinerung kontextfreier Grammatiken.

Definition: Seien N, Σ, X und S wie bei kontextfreien Grammatiken (CFG). Sei ferner P ⊆ X^{∗}NX^{∗}xX^{∗}, P endlich. Dann heißt G =< N, Σ, P, S > eine Chomsky-Grammatik.

4.1.1 Semantik

π = α_{1} → α_{2} ∈ P bestimmt die Ableitungsrelation ⇒_{π}⊆ X^{∗}xX^{∗} durch β_{1} ⇒_{π} β_{2} : ↶ ↷ es existiert γ, δ ∈ X^{∗} mit β_{1} = γα_{1}δ und β_{2} = γα_{2}δ.

Ableitungsrelation von G :⇒_{g}:= ⋃_{π∈P} ⇒_{π}

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

4.1.2 Klassifikation von Chomsky-Grammatiken und Sprachfamilien

Sei G =< N, Σ, P, S > eine Chomsky-Grammatik und i ∈ {0, 1, 2, 3}. Dann heißt G vom Typ i oder auch eine Typ i-Grammatik, wenn P die Eigenschaft (i) besitzt mit

(0) Keine Einschränkung

(1) Jedes π ∈ P hat die Form γAδ → γβδ mit β ≠ ε oder S → ε. Ferner S → ε, α → β ∈ P ↷ S nicht in β.

(2) Jedes π ∈ P hat die Form A → α.

(3) Entweder: Jedes π ∈ P hat die Form A → Bw oder A → w oder: Jedes π ∈ P hat die Form A → wB oder A → w

Es folgt:

Grammatiken vom Typ 0 sind genau die Chomsky-Grammatiken Grammatiken vom Typ 1 heißen auch kontextsensitiv Grammatiken vom Typ 2 sind genau die kontextfreien Grammatiken Grammatiken vom Typ 3 sind genau die einseitig linearen Grammatiken

L ⊆ Σ^{∗} heißt vom Typ i : ↶ ↷ ∃G vom Typ i : L(G) = L. Bezeichnung: ℒ (Σ) := {L ⊆ Σ^{∗}|L vom Typ i}

4.1.3 Chomsky-Hierarchie

ℒ_{3}(Σ) ⫋ ℒ_{2}(Σ)^{1}⫋ℒ_{1}(Σ) ⫋ ℒ_{0}(Σ)

falls |Σ| > 1; |Σ| = 1 ↷ ℒ_{3}(Σ) = ℒ_{2}(Σ).

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} = γβδ. Beachte: β = ε erlaubt, im Gegensatz zu Typ 1.

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

4.1.4 Abschlußeigenschaften von ℒ_{0}(Σ)

G normiert (π = γ\underline{A}δ → γ\underline{β}δ)

Satz: Zu jedem G =< N, Σ, P, S > vom Typ 0 läßt sich eine äquivalente Grammatik G′ =< N′, Σ, P′, S′ >, G′ normiert, konstruieren.

Beweis:

1. Terminalsymbol-Bedingung:

a ∈ Σ ↦ A_{a} neues Nichtterminalsymbol. (a durch A_{a} ersetzen und A_{a} → a hinzufügen).

2. Simulation von A_{1} … A_{n} → B_{1} … B_{m} (n ≠ 1, m ∈ ℕ): durch Symbolersetzungsregeln mit Hilfe neuer Nichtterminal-Symbole A′_{i}.

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

1folgt aus CNF

Zwei Fälle zu unterschieden:

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+2} … A′_{n}
⋮  ⋮
B_{1} … B_{m}A′_{n} → B_{1} … B_{m}

□

Satz: ℒ (Σ) ist unter Substitution abgeschlossen, d.h. ist ϕ : 𝔭(Σ^{∗}) → 𝔭((⋃_{a∈Σ} Σ_{a})^{∗}) eine Substitutionsabbildung, so gilt: L ∈ ℒ_{0}(Σ), ϕ(a) ∈ ℒ_{0}(Σ_{a}) ∀a ∈ Σ ↷ ϕ(L) ∈ ℒ_{0}(⋃_{a∈Σ} Σ_{a}).

Beweis: Konstruktion von CFG nicht anwendbar: neue Ableitungen wegen unzulässiger Satzformen. Idee: Sequentialisierung der Ableitungen mit Kontrollsymbol. L = L(G) mit G =< N, Σ, P, S > vom Typ 0. ϕ(a) =: L_{a} = L(G_{a}) mit G_{a} =< N_{a}, Σ, P_{a}, S_{a} > vom Typ 0. O.B.d.A.: G, G_{a} normiert, N, N_{a} disjunkt.

Konstruktion von \overline{G} (Typ 0) 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} → CS, C → ε\} P_{0} entstehe aus P durch Ersetzen von a durch A_{a}(a ∈ Σ) P_{1} := {CA_{a} → CS_{a}|a ∈ Σ}

C ; \begin{matrix}CS_{a}A_{b} \\ Cw_{1} \end{matrix}

P_{2} := {C_{a} → aC|a ∈ Σ}

1. ϕ(L) ⊆ L(\overline{G}), \overline{S} ⇒ CS ⇒^{∗} CA_{a_{1}} … A_{a_{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}C ⇒ w_{1} … w_{r}

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

□

Korollar: ℒ_{0}(Σ) ist unter regulären Operationen abgeschlossen: L, L′ ∈ ℒ_{0}(Σ) ↷ L∪L′, LL′, L^{∗} ∈ ℒ_{0}(Σ). Beweis: wie für CFL.

□

Satz: ℒ_{0}(Σ) ist unter Durchschnitt abgeschlossen. Beweis: L_{i} = L(G_{i}) und G_{i} =< N_{i}, Σ, P_{i}, S_{i} > vom Typ 0 (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} → ε|a, b ∈ Σ}

□

Bemerkung: Da ℒ_{0}(Σ) = ℒ (Σ, TM) (siehe 4.2.2), ist ℒ_{0}(Σ) nicht unter Komplement abgeschlossen.

4.1.5 Kontextsensitive Grammatiken und Sprachen

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 steht.

Kontextsensitive Regel: αAβ → αγβ und γ ≠ ε.

Korollar: Eine Typ 1-Grammatik ist von wachsender Länge. Satz: Zu jeder Grammatik von wachsender Länge läßt sich eine äquivalente Typ 1-Grammatik konstruieren. Beweis: Normierung von Typ 0-Grammatiken.

□

Zur Erinnerung: A_{1} … A_{n} → B_{1} … B_{m} neue N-Symbole: A′_{1}, …, A′_{n}

A_{1} … A_{n} → A′_{1}A_{n} … A_{n}

⋮
A′_{1} … A′_{n−1}A_{n} → A′_{1} … A′_{n}

m ≥ n : B_{1} … B_{n−1}A′_{n} → B_{1} … B_{m} m < n : B_{1} … B_{m}A′_{m+1} … A′_{n} → B_{1} … B_{m}A′_{m+2} … A′_{n}

4.1.6 Platzbedarf

Definition: Sei G =< N, Σ, P, S > eine Typ 0-Grammatik, δ = (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)\} der Platzbedarf von w bezüglich G.

Folgerung:

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

2. G Typ 1, w ≠ ε ↷ \underline{pl}_{G}(w) = |w|

4.1.7 Platzbedarfssatz

Sei G vom Typ 0 und p ∈ ℕ, p > 0, so daß für alle Worte w ∈ L(G)\{ε} :

\underline{pl}_{G}(w) ≤ p|w|

Dann ist L(G) ∈ ℒ_{1}.

Beweis: Sei p = 1, also für w ∈ L(G)\ε

\underline{pl}_{G}(w) = |w|

Idee: Elimination verkürzender Regeln durch Auffüllen mit Hilfssymbolen. Konstruktion einer äquivalenten Grammatik von wachsender Länge: G′ =< N ·∪{$}, Σ, P′, S >

1. α → β ∈ P mit |α| = |β| + i (i > 0)

↷ α → $^{i}β ∈ P′

2. α → β ∈ P mit |α| + i = |β| (i ∈ ℕ)

↷ $^{δ}α → β ∈ P′ für alle δ = 0, 1, …, i

3. $X → X$, X$ → $X ∈ P′ für alle X ∈ X.

Wegen \underline{pl}_{G}(w) = |w| lassen sich die eingeschobenen $-Symbole löschen. p > 1: Induktion über p. N^{P} ⊆ N′.

□

4.1.8 Abschlußeigenschaften von ℒ_{1}(Σ) mit Hilfe des Platzbedarfssatzes

Satz: ℒ_{1}(Σ) ist unter ε-freier Substitution (ε ∈ ϕ(a)) abgeschlossen. Beweis: Platzbedarf der Ausgangsgrammatiken mit p = 1 ↷ Platzbedarf der Substitutionsgrammatik |w| + 1 ≤ 2|w| wegen zusätzlichen Kontrollsymbol C und fehlender ε-Regeln.

□ Korollar: ℒ_{1}(Σ) ist unter regulären Operationen abgeschlossen. Beweis: Reduktion auf ε-freie Typ 1-Sprachen.

L ∈ ℒ_{1}(Σ) ↷ L\{ε} ∈ ℒ_{1}(Σ)

Für ε-freie L, L′ ∈ ℒ_{1}(Σ) folgt

L ∪ L′, LL′, L^{∗} ∈ ℒ_{1}(Σ)

wie für Typ 0-Sprachen durch ε-freie Substitution. Falls ε ∈ L und/oder ε ∈ L′, so schließt man über die ε-freie Teilsprachen, zum Beispiel:

(L ·∪ {ε})(L′ ·∪ {ε}) = LL′ ∪ L ∪ L′ ∪ {ε}
□

Korollar: ℒ_{1}(Σ) ist unter ∩ abgeschlossen. Beweis: L_{1}, L_{2} ∈ ℒ_{1}(Σ) sind mit linearen Platzbedarf (p = 1) erzeugbar. Die ∩-Konstruktion für Typ 0-Grammatiken hat dann einen Platzbedarf von 2|w| + 3 ≤ 5|w|

□

Ein lange ungelöstes Problem ist der Abschluß von ℒ_{1} unter Komplement. 1987: ℒ_{1}(Σ) ist unter Komplement abgeschlossen.

Korollar: ℒ_{1}(Σ) ⫋ ℒ_{0}(Σ)

4.2 Turingmaschinen, linear beschränkte Automaten

Ziel: ℒ_{0}(Σ) = ℒ (Σ, TM) ℒ_{1}(Σ) = ℒ (Σ, LBA)

Modell einer Turingmaschine (TM): besteht aus einem unendlichen Band, welches größtenteils mit Blanks beschriftet ist, sowie wenige Symbole. Weiterhin gibt es eine endliche Kontrolle welche aus endlichen Quintupel besteht.

4.2.1 Nicht deterministisch erkennende TM

Definition: Seien die folgenden nicht-leeren, endlichen Menge gegeben:

Q Zustandsmenge Σ Eingabealphabet Γ Arbeitsalphabet mit Σ ⊆ Γ Ferner: q_{0} ∈ Q Anfangszustand □ ∈ Γ\Σ Blank F ⊆ Q Endzustandsmenge und die Transitionsfunktion δ : Q × Γ → 𝔭(Q × Γ × {L, N, R})

Dann heißt 𝔄 =< Q, Σ, Γ, q_{0}, □, F, δ > eine nicht-deterministische erkennende Turingmaschine. Bezeichnung: 𝔄 ∈ TM(Σ).

4.2.2 Semantik

Konfigurationsmenge: \underline{Conf}(𝔄) := Q × Γ^{∗} × Γ × Γ^{∗}

Einzelschrittrelation: ⊢_{𝔄}⊆ \underline{Conf}(𝔄)^{2} sei definiert wie folgt:

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

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

δ(q, X) ∋ (q′, X′, L) ↷ (q, ε, X, β) ⊢ (q′, ε, □, X′β)

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

δ(q, X) ∋ (q′, X′, R) ↷ (q, α, X, ε) ⊢ (q′, αX′, □, ε)

Bemerkung: beiderseits unendliches Band, fast überall stehen Blanks (□’s).

Anfangskonfiguration: w ∈ Σ^{∗}

𝔎(w) := \{ \begin{matrix}(q_{0}, ε, a, v) & , falls w = av \\ (q_{0}, ε, □, ε) & , falls w = ε \end{matrix}

Endkonfiguration: (q, α, X, β) , q ∈ F

Die von 𝔄 erkannte Sprache: L(𝔄) := {w ∈ Σ^{∗}|𝔎(w) ⊢_{𝔄}^{∗} (q, α, X, β), q ∈ F }

Beachte: Erreichen von q ∈ F genügt. Ein Anhalten der Turingmaschine ist nicht gefordert.

Die Klasse der durch TM erkennbaren Sprachen: ℒ (Σ, TM)

Satz: ℒ (Σ, TM) = ℒ_{0}(Σ)

Beweis:

4.2.3 I. ℒ (Σ, TM) ⊆ ℒ_{0}(Σ)

𝔄 =< Q, Σ, Γ, q_{0}, □, F, δ >∈ TM(Σ) Simulation von 𝔄 durch eine Typ 0-Grammatik. Idee: Erzeugen einer beliebigen Anfangskonfiguration mit hinreichend vielen Blanks an den Rändern (bei Ableitungen sind Ränder nicht erkennbar). Wir benutzen zwei Spuren: Die erste Spur hält die Eingabe für die Erzeugung und die zweite Spur simuliert die Turingmaschine.

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 : Erzeugen von (*)

S → (ε, □)S|q_{0}C_{1}

C_{1} → (a, a)C_{1}|C_{2} (a ∈ Σ)
C_{2} → (ε, □)C_{2}|ε

Simulation der Turingmaschine:

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)

löschen von q durch 2. Spur, ursprünglicher Wert bleibt übrig:

q → ε falls q ∈ F

(a, X) → a (a ∈ Σ_{ε}

Es folgt: L(G) = L(𝔄).

4.2.4 II. ℒ_{0}(Σ) ⊆ ℒ (Σ, TM)

L ∈ ℒ_{0}(Σ) werde erzeugt von der Typ 0-Grammatik G =< N, Σ, P, S >. Simulation von G durch 𝔄 ∈ TM(Σ): neben Eingabewort Ableitungen von G simulieren und anschließend vergleichen.

Form der Berechnung:

q_{0}w Anfangskonfiguration ↓ ∗ [w][s_{q_{G}}] Beginn der Simulation von G ↓ [w][s_{q_{i}}] Wahl der i-ten Regel ↓ ∗ [w][α_{q_{G}}] Simulation der i-ten Regel beendet ↓ ∗ [w][v_{q_{v}}] Vergleich w = v? ↓ ∗ q_{erk}[□ … □]

Konstruktion von 𝔄 ∈ TM(Σ) für die Typ 0-Grammatik G =< N, Σ, P, S > mit s Regeln der Form X_{1} … X_{n} → Y_{1} … Y_{m} (n ≥ 1, m ≥ 0) 𝔄 =< Q, Σ, Γ, q_{0}, F, □, δ > sei definiert durch

Q = {q_{0}, q_{0}^{1}, …, q_{0}^{n}} (Anfangsphase)

∪{q_{G}, q_{1}, …, q_{s}} (Simulations von G, Regelauswahl)

∪{q_{i}^{Z_{1}...Z_{k}}, q_{i_{Z_{1}...Z_{l}}} |1 ≤ k ≤ n, 0 ≤ l ≤ m, Z_{μ} ∈ X ∪ {]}}

für alle 1 ≤ i ≤ s (Simulation von X_{1} … X_{n} → Y_{1} … Y_{m})

∪{q_{v}, q^{a}, q_{a}, q^{→}, q_{erk}|a ∈ Σ ∪ {[}} (Vergleichsphase)

Γ := Σ ·∪ N ·∪ {□, [,]} F := {q_{erk}} δ : Q × Γ → 𝔭_{f}(Q × Γ × {−1, 0, 1})

sei mit Quintupeln dargestellt: statt δ(q, X) ∋ (q′, X′, p) schreibt man qXX′pq′

\begin{matrix}q_{0}aaLq_{0} (a ∈ Σ) \\ q_{0}□[Rq_{0}^{1} \\ q_{0}^{1}aaRq_{0}^{1} \\ q_{0}^{1}□]Rq_{0}^{2} \\ q_{0}^{2}□[Rq_{0}^{3} \\ q_{0}^{3}□SRq_{0}^{4} \\ q_{0}^{4}□]Nq_{G} \end{matrix} \} Anfangsphase erzeugt [w][s_{q_{G}}]

\begin{matrix}q_{G}]]Nq_{i} & (nichtdeterministisch) \\ q_{i}]□Lq_{i}^{]} \\ q_{i}^{Z_{1}...Z_{k}}Z□Lq_{i}^{ZZ_{1}...Z_{k}}  (1 ≤ k < n, Z, Z_{μ} ∈ X ∪ \{]\}) \\ q_{i}^{Z_{1}...Z_{n}}ZZ_{n}Lq_{i}^{ZZ_{1}...Z_{n−1}} & (ND) \\ q_{i}^{X_{1}...X_{n}}ZZRq_{i_{Y_{1}...Ym}} & (ND) \\ q_{i_{Z_{1}...Zm}} ZZ_{1}Rq_{i_{Z_{2}...ZmZ}} \\ q_{i_{Z_{1}...Z_{l}}} □Z_{1}q_{i_{Z_{2}...Z_{l}}} & (1 ≤ l ≤ m) \\ q_{i_{ε}}□□Lq_{G} \\ q_{i_{ε}}ZZRq_{i_{ε}} & (fallsm = 0) \end{matrix} \} Simulation

\begin{matrix}q_{G}]]Nq_{V} & (ND) \\ q_{V}]□Lq_{V} \\ q_{V} a]Lq^{a} & (a ∈ Σ ∪ \{[\}) \\ q^{a}bbLq^{a} & (b ∈ Σ ∪ \{[, □\}) \\ q^{a}]□Lq_{a} \\ q_{a}a]R q^{→} & (a ∈ Σ) \\ q^{→}bbR q^{→} & (b ∈ Σ ∪ \{[, □\}) \\ q^{→}]]Nq_{V} \\ q_{[}[[Nq_{erk} & (q_{erk}[□ … □]) \end{matrix} \} Erkennungsphase

□

4.2.5 Platzbedarf für Turingmaschinen

Definition: Sei 𝔄 ∈ TM(Σ), γ = (κ_{0} ⊢ κ_{1} ⊢ … ⊢ κ_{n}) eine Berechnung und w ∈ L(𝔄). Dann ist

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

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

• \underline{bv}_{𝔄}(w) := \underline{min}\{\underline{bv}_{𝔄}(γ)|γ erkennt w\}

der Bandverbrauch von 𝔄 für γ, bzw. w.

Definition: 𝔄 ∈ TM heißt linear beschränkt (𝔄 ∈ lbTM), wenn p ≥ 1 existiert, so daß für alle w ∈ L(𝔄)\ε

\underline{bv}_{𝔄}(w) ≤ p · |w|

Korollar: ℒ_{1}(Σ) = ℒ (Σ, lbTM). Grund: Simulationen erhalten linearen Platzbedarf/Bandverbrauch.

Definition: 𝔄 ∈ LBA(Σ) (”linear beschränkter Automat“): ↶ ↷𝔄 ∈ lbTM mit p = 1, d.h. nur Eingabefelder werden benutzt.

Satz: ℒ_{1}(Σ) = ℒ (Σ, LBA) Beweis: (Idee) Kompression des benutzten Bandbereichs durch Vergrößerung des Arbeitsalphabets Γ′ := Γ^{P}.

□

4.2.6 Deterministische TM, k-Band-TM

Reduktion nicht-deterministische TM auf deterministische TM in 2 Schritten:

1. Simulation einer nicht-deterministischen TM durch eine 3-Band-deterministische-TM.

2. Reduktion von k-Band-deterministischen-TM auf 1-Band-deterministische-TM.

deterministische k-Band-TM

Definition: 𝔄 =< Q, Σ, Γ, q_{0}, □, F, δ >∈ k − dTM, wenn: δ : Q × Γ^{k} −−→ Q × (Γ × {L, N, R})^{k} und sonst wie TM.

Konfiguration: Q × (Γ^{∗} × Γ × Γ^{∗})^{k}

Einzelschrittfunktion: simultanes Arbeiten auf k Bändern gemäß δ.

Anfangskonfiguration: für w ∈ Σ^{∗} :

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

L(𝔄) := {w ∈ Σ^{∗}|κ_{w} ⊢^{∗} (q, …) mit q ∈ F }

Satz: Zu jedem 𝔄 ∈ TM läßt sich ein äquivalentes 𝔄′ ∈ 3 − dTM konstruieren.

Beweis: Für δ_{𝔄} : Q × Γ → 𝔭_{f}(Q × Γ × \{L, N, R\}), gelte r := \underline{max}\{|δ(q, X)|(qX) ∈ Q × Γ\} Bezeichnung der Alternativen von 𝔄 durch Elemente von [r] := {1, …, r}.

Berechnung von 𝔄 bestimmt ζ ∈ [r]^{∗}.

Umgekehrt: Auswahl einer Berechnung durch ein solches ζ als Steuerwort.

Band 1: Eingabe, wiederholtes Lesen.

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

Band 3: Simulation von 𝔄 gemäß Band 2.

Sukzessive Berechnung aller ζ ∈ [r]^{∗}. Für jedes ζ Kopie der Eingabe auf Band 3. Dann Simulation gemäß Band 2.

□

Satz: Zu jedem 𝔄 ∈ k − dTM läßt sich eine äquivalente 𝔄′ ∈ 1 − dTM konstruieren.

Beweis: Simulation von k Bändern durch 1 Band mit 2k Spuren für k Bänder und Kopfpositionen. Arbeitsalphabet Γ′ := (Γ × {□, k})^{k}. Simulation eines Arbeitsschrittes von 𝔄 :

Lesephase: Suchen der k gelesenen Symbole, speichern in endlicher Kontrolle. Problem: iter Kopf rechts oder links vom Hauptkopf (Simulationskopf)? Lösung: Positionsvektor {l, r}^{k} in endlicher Kontrolle.

Q′ := \underbrace{Q × Γ^{k}}_{δ−Argument} ×\{l, r\}^{k} × \{1, …, k\}

Schreibphase: analog zur Lesephase.

□

Korollar: ℒ (Σ, TM) = ℒ (Σ, dTM). Bemerkung: Für LBA’s ist diese Frage offen: das LBA-Problem.

4.3 Aufzählbare und entscheidbare Sprachen

Intuitiv: L ⊆ Σ^{∗} ist aufzählbar, wenn es ein effektives Verfahren (Programm) gibt, welches genau die Elemente von L erzeugt (aufzählbar = rekursiv aufzählbar). Präzisierung durch TM mit Ausgabe:

𝔄 =< Q, Σ, Γ, q_{0}, F, □, δ >∈ dTM(Σ)

𝔄 berechnet f_{𝔄} : Σ^{∗} −−→ Σ^{∗} mit f_{𝔄}(w) = v : ↶ ↷q_{0}w□ ⊢^{∗} αqv□βi ⊬

Bezeichnung: Konfiguration statt (q, α, X, β) kurz: αqXβ. Endkonfiguration κ ⊬ ↶ ↷κ hat keine Folgekonfiguration.

Beachte: Endzustände ohne Bedeutung.

4.3.1 Aufzählbare Sprachen

Definition: L ⊆ Σ^{∗} heißt aufzählbar, wenn 𝔄 ∈ dTM(Σ) existiert mit \underline{Def}(f_{𝔄}) = Σ^{∗} und \underline{Bild}(f_{𝔄}) = L oder wenn L = ∅.

Bemerkung: Aufzählung von Σ^{∗} (etwa der Länge nach), es gibt eine Aufzählung von L.

Satz: Für L ⊆ Σ^{∗} gilt: L aufzählbar ↶ ↷L ∈ ℒ (Σ, TM).

Beweis: (Idee)

1. L = ∅: L aufzählbar
L ∈ ℒ (Σ, TM), zB. 𝔄 mit F = ∅

2. L ≠ ∅ ”↷“ 𝔄 ∈ dTM(Σ) mit f_{𝔄} total und \underline{Bild}(f_{𝔄}) = L. Konstruktion von 𝔄′ ∈ dTM(Σ) mit L(𝔄′) = L. Idee: Eingabe von w ∈ Σ^{∗} speichern, L aufzählbar und jedes aufgezähltes Wort mit w vergleichen; bei Übereinstimmung Endzustand, andernfalls weiter aufzählen.

”↶“ 𝔄 ∈ dTM(Σ) mit L(𝔄) = L.

Konstruktion von 𝔄′′ ∈ dTM(Σ) mit f_{𝔄′′} total mit \underline{Bild}(f_{𝔄′′}) = L.

Idee:

(a) 𝔄 so modifizieren, daß Eingabe bei Erkennung ausgegeben wird. Dann gilt: \underline{Def}(f_{𝔄′}) = \underline{Bild}(f_{𝔄′}) = L.

(b) Damit 𝔄′ bei jeder Eingabe ein Wort aus L ausgibt, folgender Trick: Teil der Eingabe als Zähler zur Beschränkung der Berechnungslänge.

Σ = {a_{1}, a_{2}, …, a_{r}} mit r ≥ 2

Eingabe hat immer die Form:

(∗) a_{1}^{n}a_{i}w bzw. a_{1}^{n} mit i ≠ 1 und n ∈ ℕ

𝔄′′ simuliert dann 𝔄′ mit Eingabe w, bzw. ε und höchstens n Schritten. Eine Ausgabe von 𝔄′ ist auch Ausgabe von 𝔄′′. Wurde nach n Schritten keine Ausgabe berechnet, so wird irgendein v ∈ L als Ausgabe berechnet: 𝔄′ mit Längenbeschränkung und Eingabe von ε, a_{1}, a_{2}, … bis zur ersten Ausgabe laufen lassen

Es folgt: f_{𝔄′′} total mit \underline{Bild}(f_{𝔄}) = L.
□

Satz: ℒ_{0}(Σ) ⫋ 𝔭(Σ^{∗}). Beweis: Die Menge der Typ 0-Grammatiken über Σ läßt sich nach ihrer Größe abzählen. Also ist ℒ_{0}(Σ) abzählbar (d.h. gleichmächtig mit ℕ). 𝔭(Σ^{∗}) ist jedoch überabzählbar (Diagonalverfahren nach Cantor).

Einfachster Fall: |Σ| = 1, Σ^{∗} = ℕ 3 = aaa. L ⊆ Σ^{∗} ↦ \underline{char}_{L} : ℕ → \{0, 1\}, \underline{char}_{L}(n) = 1 ↶ ↷ n ∈ L. Angenommen, 𝔭(ℕ) wäre abzählbar. Dann gäbe es eine Funktion f : ℕ^{2} → {0, 1} mit f(i, j) = 1 ↶ ↷ \underline{char}_{L_{i}}(j) = 1

0 1 2 3 4 5 6 …
0 0 1 0 0 1 0
1 1 0 1 0 0 0
2 0 1 1 1 0 0
3 1 1 1 0 1 0
4  ...
⋮

Definiere L_{dia} ⊆ ℕ durch

\underline{char}_{L_{dia}}(j) := 1 − f(j, j)

Dann kann L_{dia} nicht in der Abzählung vorkommen.

□

4.3.2 Entscheidbare Sprachen

Eine aufzählbare Sprache L ⊆ Σ^{∗} kann zwar durch ein 𝔄 ∈ dTM(Σ) als L(𝔄) erkannt werden. Da aber die Berechnung von 𝔄 bei Eingabe von w ∈ Σ^{∗} nicht terminieren muß, läßt sich im allgemeinen auch nicht entscheiden, ob w ∈ L oder w ∉ L.

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

Präzisierung durch eine dTM mit Ausgabe

Definition: L ⊆ Σ^{∗} heißt entscheidbar: ↶ ↷ es gibt 𝔄 ∈ dTM(Σ) mit \underline{Def}(f_{𝔄}) = Σ^{∗} und L = f_{𝔄}^{−1}(ε)

Satz: Für L ⊆ Σ^{∗} gilt: L entscheidbar ↶ ↷L und Σ^{∗}\L aufzählbar.

Beweis:

”↷“ L entscheidbar, 𝔄 ∈ dTM mit f_{𝔄} total und L = f_{𝔄}^{−1}(ε).

Konstruiere 𝔄′ mit L(𝔄′) = L und 𝔄′′ mit L(𝔄′′) = Σ^{∗}\L durch passende Wahl der erkennenden Endzustände.

”↶“ 𝔄_{i} ∈ dTM(Σ), f_{𝔄_{i}} total, \underline{Bild}(f_{𝔄_{1}}) = L, bzw. \underline{Bild}(f_{𝔄_{2}}) = Σ^{∗}\L.

Konstruiere ”Endscheidungs-Turingmaschine“ nach Reißverschlußprinzip:

w ∈ Σ^{∗}, berechne f_{𝔄_{1}}(ε), f_{𝔄_{2}}(ε), f_{𝔄_{1}}(a_{1}), f_{𝔄_{2}}(a_{1}), …

bis f_{𝔄_{i}}(v) = w.

□

Satz: DEC(Σ) := {L ⊆ Σ^{∗}|L entscheidbar } ⫋ ℒ_{0}(Σ)

Beweis: (Idee) Die ”Selbstanwendungsmenge“ ist nicht entscheidbar (Diagonalisierungsprinzip).

□

Satz: Jede Typ 1-Sprache über Σ ist entscheidbar. Beweis: Sei G eine Typ 1-Grammatik über Σ und w ∈ Σ^{∗}.

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

Fall 2: w ≠ ε, w ∈ L ↶ ↷ ∃ Ableitung S ⇒ α_{1} ⇒ … ⇒ α_{n} = w mit |α_{i}| ≤ |w|. Nur endlich viele solcher Ableitungen (können einfach durchgetestet werden).

□

Unentscheidbare Probleme

Ziel: Die folgenden Probleme sind unentscheidbar:

• Das Wortproblem für Typ 0-Beschreibungen (Haltproblem für Turingmaschinen, siehe Vorlesung ”Berechenbarkeit und Komplexität“).

• Das ∅-Problem für Typ 1-Beschreibungen.

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

Bemerkung: Das Äquivalenzproblem für DPDA’s wurde kürzlich als entscheidbar nachgewiesen. Hilfsmittel: Das Postsche Korrespondenzproblem (vgl. ”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. Dann heißt (i_{1}, …, i_{k}) ∈ {1, …, n}^{k} eine Lösung von PCP(w, v), fall w_{i_{1}}w_{i_{2}} … w_{i_{k}} = v_{i_{1}}v_{i_{2}} … v_{i_{k}}. Es gilt: Das PCP ist unentscheidbar. Beweis: (Idee) Reduktion des Haltproblems für TM auf das PCP.

5.1 Das ∅-Problem von lbTM

Satz: Das ∅-Problem von lbTM ist unentscheidbar.

Beweis: Reduktion des PCP auf das ∅-Problem von lbTM. Sei w = (w_{1}, …, w_{n}), v = (v_{1}, …, v_{n}) ∈ (Σ^{∗})^{n}. Konstruktion von 𝔄(w, v) ∈ lbTM mit

PCP(w, v) lösbar ↶ ↷ L(𝔄(w, v)) ≠ ∅

𝔄(w, v) erzeugt bei Eingabe von u ∈ Σ^{+} alle Indexfolgen (i_{1}, …, i_{k}) ∈ {1, …, n}^{k} mit k ≤ |u|. (Idee: Eingabe als Zähler verwenden) und prüft jeweils, ob w_{i_{1}}w_{i_{2}} … w_{i_{k}} = v_{i_{1}}v_{i_{2}} … v_{i_{k}}. 𝔄 erkennt u, falls eine solche Indexfolge auftritt. Platzbedarf linear in |u|. Wäre ∅-Problem für lbTM entscheidbar, so auch PCP: Widerspruch.

□

5.2 Schnittproblem für kontextfreie Grammatiken

Satz: Es ist nicht entscheidbar, ob für G_{1}, G_{2} ∈ CFG gilt: L(G_{1}) ∩ L(G_{2}) = ∅. Beweis: Reduktion des PCP auf dieses Schnittproblem. Sei w = (w_{1}, …, w_{n}) und v = (v_{1}, …, v_{n}) ∈ (Σ^{∗})^{n}. Konstruiere G_{w}, G_{v} ∈ CFG, so daß

PCP(w, v) lösbar ↶ ↷ L(G_{w}) ∩ L(G_{v}) ≠ ∅

Σ̃ := Σ ·∪ {b_{1}, …, b_{n}} ”Indexsymbole“ G_{w} := S_{w} → w_{i}S_{w}b_{i}|w_{i}b_{i} (1 ≤ i ≤ n) G_{v} analog

Es folgt: L_{w} := L(G_{w}) = {w_{i_{1}} … w_{i_{k}}b_{i_{k}} … b_{i_{1}}|k ≥ 1, 1 ≤ i_{μ} ≤ 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_{1_{k}} … b_{i_{1}}

also w_{i_{1}} … w_{i_{k}} = v_{i_{1}} … v_{i_{k}} ↶ ↷ PCP(w, v) lösbar.

□

Korollar: Das Schnittproblem für DPDA’s ist nicht entscheidbar. Beweis: G_{w} und G_{v} sind durch deterministische Kellerautomaten simulierbar. Idee: w_{i}’s in den Keller lesen und dann mit den b_{i}’s löschen.

□

5.3 Äquivalenzproblem für CFG

Satz: Es ist nicht entscheidbar, ob für G_{1}, G_{2} ∈ CFG gilt:

L(G_{1}) = L(G_{2})

Beweis: Reduktion des Schnittproblems für DPDA’s auf das Äquivalenzproblem von CFG. Beachte:

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

2. Zu 𝔄 ∈ PDA(Σ) läßt sich G_{𝔄} ∈ CFG(Σ) konstruieren mit L(G_{𝔄}) = L(𝔄).

3. Zu G_{1}, G_{2} ∈ CFG(Σ) läßt sich G_{∪} ∈ CFG(Σ) konstruieren mit L(G_{∪}) = L(G_{1})∪L(G_{2}).

Hieraus folgt für 𝔄_{1}, 𝔄_{2} ∈ DPDA(Σ):

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

Die Entscheidbarkeit der Äquivalenzproblems für CFG würde somit die Entscheidbarkeit des ∩-Problems von DPDA’s implizieren.

□

5.4 Mehrdeutigkeitsproblem

Satz: Es ist nicht entscheidbar, ob ein G ∈ CFG mehrdeutig ist, oder nicht. Beweis: Reduktion des PCP auf das Mehrdeutigkeitsproblem. Seien w = (w_{1}, …, w_{n}) und v = (v_{1}, …, v_{n}) ∈ (Σ^{∗})^{n}, Σ̃ := Σ ·∪ {b_{1}, …, b_{n}}. Konstruktion von

G_{(w,v)} = S → A_{w}|A_{v}
A_{w} → w_{i}A_{w}b_{i}|w_{i}b_{i} (1 ≤ i ≤ n)
A_{v} → v_{i}A_{v}b_{i}|v_{i}b_{i} (1 ≤ i ≤ n)

Es folgt:

(i_{1}, …, i_{k}) löst PCP(w, v) ↶ ↷ w_{i_{1}} … w_{i_{k}} = v_{i_{1}} … v_{i_{k}}
↶ ↷ w_{i_{1}} … w_{i_{k}}b_{i_{k}} … b_{i_{1}} = v_{i_{1}} … v_{i_{k}}b_{i_{k}} … b_{i_{1}} = Z
↶ ↷ S ⇒ A_{w} ⇒^{∗} Z und S ⇒ A_{v} ⇒^{∗} Z
↶ ↷ G_{(w,v)} mehrdeutig

□

Zusammenfassung siehe Folie 4.4

5.5 Komplexität der entscheidbaren Probleme

5.5.1 Äquivalenzproblem bei Typ 3-Beschreibungen

DFA: ρ(n^{2})

NFA/RegE: exponentiell, NP-hart, PS-vollständig

52  5.5 Komplexität der entscheidbaren Probleme

5.5.2 Wortproblem

DFA: linear CFG: ρ(n^{3}) CSG: exponentiell, NP-hart, PS-vollständig

Index

ε-Hülle, 9 ε-frei, 23–25 k-äquivalent, 15 uvwxy-Theorem, 27 äquivalent, 14

Ableitung, 13 Ableitungsautomat, 13 Ableitungsbaum, 20 Ableitungsrelation, 19, 35 Ableitungsschritt, 19 Algorithmus von Thompson, 11 Anfangszustand, 8, 29, 40 Arbeitsalphabet, 40 aufzählbar, 45, 46 Automat, 8, 9, 11, 17 Automaten, Mealy, 16 Automaten, Moore, 16 Automaten, zustandsminimale, 14

Bandverbrauch, 44 Blank, 40

Cantor, 46 Chomsky-Grammatik, 35 Chomsky-Normalform, 25

deterministisch, 31 deterministischer endlicher Automat, 8 Diagonalisierungsprinzip, 48 Diagonalverfahren, 46

eindeutig, 20 Eingabealphabet, 8, 40 Eingabesymbol, 29 einseitig linear, 21 Einzelschrittrelation, 29 endliche Kontrolle, 40 Endscheidungs-Turingmaschine, 47 Endzustandsmenge, 8, 40 entscheidbar, 47 Entzustandsmenge, 29 erkannte Sprache, 9 Erkenungslauf, 12 erreichbar, 14, 23 erweiterte CFG, 33 erweiterte Transitionsfunktion, 9 erzeugte Sprache, 20

Faktorautomat, 14

Grammatik, 23

Grammatik, äquivalent/reduziert, 23 Greibach-Normalform, 25

Iterationslemma, 12 Iterationszustand, 12

Kellerautomat, 29 Kellerspeicher, 29 Kellerstartsymbol, 29 Kellersymbolen, 29 Kettenregel, 24 Konfigurationsmenge, 29 kontextfreie Grammatik, 19 kontextsensitiv, 36

LBA-Problem, 45 linear beschränkt, 44 linear beschränkter Automat, 44 Linksableitung, 20 Linksableitungsschritt, 20 linkslinear, 21 Linksrekursion, 25, 26 linksrekursiv, 26 linksrekursiver, 26

mehrdeutig, 20

nicht deterministischer Automat, 9 nicht erreichbar, 23 \underline{54 INDEX}

nicht produktiv, 23 nicht-deterministischer endlicher Automat,

9 normiert, 36

Platzbedarf, 38 produktiv, 23 Pumping-Eigenschaften, 28 Pumping-Index, 12, 28, 31 Pumping-Lemma, 12, 26, 27 push down store, 29

Quintupel, 40

Rechtsableitung, 20 Rechtsableitungsschritt, 20 rechtslinear, 21 reduziert, 23 Regelbaum, 20 reguläre Ausdrücke, 7, 17 regulären Sprachen, 8 Reißverschlußprinzip, 47 rekursiver endlicher Automat, 33

Schleifenkonfiguration, 32 Selbstanwendungsmenge, 48 Semantik, 9 Substitutionsabbildung, 26, 27, 31, 37 Substitutionssatz, 26 Substitutionssprachen, 27

Thompson, Algorithmus von, 11 Transitionsfunktion, 8, 29, 40 Turingmaschine, 11

Vorgängerabschluß, 22 Vorgängermenge, 22

wachsender Länge, 38, 39

Zustand, 29 Zustandsmenge, 8, 40 Zustandsreduktion, 13, 14