Automaten und Sprachen

Skript zur Vorlesung

Prof. Peter H. Starke

Lehrstuhl für Automaten- und Systemtheorie

27. Oktober 1994

Inhaltsverzeichnis

1 Einleitung 1 1.1 Algebra der Wörter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Automaten 8 2.1 Der Zustandsbegriff in der Systemtheorie . . . . . . . . . . . . . . . 8 2.2 Der Automatenbegriff . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Erweiterung von δ und λ auf Wörter über X . . . . . . . . . . . . . 10 2.4 Äquivalenz von Zuständen und Automaten . . . . . . . . . . . . . . 11 2.5 Berechnung der Äquivalenzklassen . . . . . . . . . . . . . . . . . . . 14 2.6 Eingabe-/Ausgabeverhalten . . . . . . . . . . . . . . . . . . . . . . . 15

3 Regelsprachen und Automaten 21 3.1 Akzeptoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 Berechenbarkeit 45 4.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 Mathematische Charakterisierung der Berechenbarkeit . . . . . . . . 48

Kapitel 1

Einleitung

1.1 Algebra der Wörter

Definition 1.1.1

1. Ein Alphabet X ist eine endliche, nichtleere Menge (die Elemente nennt man Buchstaben).

2. p ist ein Wort über X, wenn p eine endliche Folge von Elementen von X ist, d. h. es gibt eine natürliche Zahl n, so daß p : {0, …, n − 1} → X (leer falls n = 0).

3. Das Wort e : ∅ → X heißt das leere Wort.

4. Die Zahl n wird als Länge l (p) des Wortes p bezeichnet.

5. W (X) bezeichnet die Menge aller Wörter über X.

Wir haben l : W (X) → N. Die Abbildung l ist nicht umkehrbar, falls card (X) ≥ 2.

Um von einer Algebra zu sprechen, definieren wir eine Operation auf W (X)

Definition 1.1.2 (Verkettung) Es sei p : {0, …, n − 1} → X, q : {0, …, m − 1} → X. Dann ist p^{⌢}q : {0, …, m + n − 1} →

X mit p^{⌢}q (i) := \{ \begin{matrix}p (i) , & i ≤ n − 1 \\ q (i − n) , & n ≤ i ≤ m + n − 1. \end{matrix}

Was hat diese Operation für Eigenschaften:

Satz 1.1.3 [W (X) ,^{⌢}, e] ist eine Halbgruppe mit dem Einselement e.

Beweis: Man rechnet leicht nach:

1. p^{⌢}(q^{⌢}r) = (p^{⌢}q)^{⌢}r

2. p^{⌢}e = p = e^{⌢}p für jedes p ∈ W (X).

Übungsaufgabe Wir kennen bereits folgende Halbgruppe: [N, +, 0]. Frage: Haben beide etwas Gemeinsames? Sind beide homomorph? (Standardfrage in der Mathematik in solchem Fall)

Definition 1.1.4 f ist Homomorphismus von der Halbgruppe [M, ∘, 1] in [N, ·, 1] wenn gilt:

1. f : M → N

2. f (1_{M}) = 1_{N}

3. f (m_{1} ∘ m_{2}) = f (m_{1}) · f (m_{2})

Folgerung 1.1.5 l ist ein Homomorphismus von [W (X) ,^{⌢}, e] auf [N, +, 0].

Bemerkung: Wenn card (X) = 1, so ist l umkehrbar eindeutig, (folglich bijektiv).

Wir werden die Schreibweise vereinfachen, indem wir Struktureigenschaften benutzen (z. B. Erzeugendes Element)

Definition 1.1.6 E ist Erzeugendensystem für [W (X) ,^{⌢}, e], wenn:

1. e ∉ E ⊆ W (X)

2. Zu jedem p ∈ W (X)\{e} gibt es Elemente r_{1}, …, r_{k} ∈ E mit p = r_{1}^{⌢}r_{2}^{⌢}…^{⌢}r_{k}.

Man sucht natürlich einfache Elemente als erzeugende Elemente. Hierfür bieten sich Buchstaben an (sie sind keine Wörter! Deshalb:) Für x ∈ X sei \underline{x} := \{[0, x]\} — Wort der Länge 1.

Damit haben wir die Buchstaben auf das Nivau Wort gebracht. Später werden wir auslassen.

Satz 1.1.7 \underline{X} := \{\underline{x}|x ∈ X\} ist ein Erzeugendensystem für [W (X) ,^{⌢}, e].

Beweis p ∈ W (X); p : \{0, …, n − 1\} → X. Offenbar ist p = \underline{p (0)}^{⌢}\underline{p (1)}^{⌢}…^{⌢}\underline{p (n − 1)}, da p (i) ∈ X.

Beispiel:

1. [N^{+}, ·, 1] ist eine Halbgruppe. Erzeugendensystem ist Pz – die Menge der Primzahlen. z. B. 6 = 2 · 3 = 3 · 2

2. [N, +, 0] ist Halbgruppe. Erzeugendensystem ist {1} z. B. 3 = 1 + 1 + 1.

Unterschied zwischen beiden Halbgruppen ist, daß die Elemente in 1) in mehreren Weisen erzeugbar und in 2) nur auf einer Weise. Die Erzeugung von 2) ist frei von nichttrivalen Gleichungen.

Definition 1.1.8 G = [M, ·, 1, E] sei eine Halbgruppe mit Erzeugendensystem E. G heißt frei erzeugt (frei von nichttrivialen Gleichungen), wenn aus m_{1} · m_{2} · · · · · m_{k} = m′_{1} · m′_{2} ⋯ m′_{n} stets k = n und m_{1} = m′_{1}, …, m_{k} = m′_{k} folgt (für m_{i}, m′_{i} ∈ E).

Folgerung 1.1.9 [W (X) ,^{⌢}, e, \underline{X}] ist freie Halbgruppe.

Satz 1.1.10 Alle freien Halbgruppen mit derselben Zahl von erzeugenden Elementen sind isomorph.

Beweis: Idee: Erzeugende Elemente sind nicht zerlegbar. Erzeugende aufeinander abbilden. Seien [M_{1}, ∘_{1}, 1, E_{1}], [M_{2}, ∘_{2}, \underline{1}, E_{2}] Halbgruppen, card (E_{1}) = card (E_{2}).

Es sei f : E_{1} → E_{2} bijektiv. Weiter definiert man den Homomorphismus folgendermaßen: f (1) = \underline{1}. Sei m ∈ M_{1}. m besitzt genau eine Darstellung m = r_{1} ∘_{1} r_{2} ∘_{1} ⋯∘_{1} r_{k} (r_{i} ∈ E_{1}). Dann sei f (m) := f (r_{1})∘_{2} f (r_{2})∘_{2} ⋯ ∘_{2}, f (r_{k}). Daß f ein Homomorphismus ist, ist klar. Es bleibt zu zeigen, daß f^{−1} : M_{2} → M_{1} eindeutig ist. Sei m′ ∈ M_{2}. Wenn m′ = \underline{1}, so f^{−1} (m′) = f^{−1} (m′_{1}) ∘_{1} ⋯ ∘_{1} f^{−1} (m′_{k}) und f^{−1} (m′_{i}) ∈ E_{1}. Weil f^{−1} (m′) genau eine Darstellung hat, ist dieser Wert eindeutig bestimmt.

Merke: f : X → Y induziert immer einen Homomorphismus von [W (X) , ∘, e] auf [W (Y) ,^{⌢}, e] Allgemein kann man sogar schreiben f : X → W (Y).

Folgerung 1.1.11 Jede freie Halbgruppe mit endlichen Erzeugendensystem ist isomorph zu einer Worthalbgruppe.

[N, +, 0, {1}] ist eine Halbgruppe mit genau einem Erzeugenden und ist isomorph zu [W (\{/\}) ,^{⌢}, e, \{\underline{/}\}]. [N, +, 0, \{1\}] ist kommutativ, also [W (\{/\}) , 1, e, \{\underline{/}\}] auch; folglich ist jede freie Halbgruppe mit genau einem Erzeugenden kommutativ.

Es ist bekannt, daß man bei der Übermittlung von Nachrichten mit 2 Zeichen auskommen kann (z. B. Computer: 0, 1). Frage, warum nicht mit einem Zeichen? Der Grund liegt in der Kommutativität, denn es gibt Halbgruppen, die nicht kommutativ sind.

Satz 1.1.12 (Hauptsatz der Kodierungstheorie) In der freien Halbgruppe [W {a, b} ,^{⌢}, e, {a, b}] mit genau zwei Erzeugenden existiert zu jedem k ≥ 1 eine freie Unterhalbgruppe mit genau k Erzeugenden.

Beweis: Sei k gegeben. E_{k} := \{a \underbrace{b}_{1} a, …, a \underbrace{b … b}_{k} a\} Sei E_{k}^{⋆} die Menge aller

Wörter, die durch endlich oftmaliges Verketten von Elementen aus E_{k} entstehen. H_{k} = [E_{k}^{⋆},^{⌢}, e, E_{k}] ist frei.

1.1.1 Induktive Beweise in [W (X) ,^{⌢}, e, X]

Beispiel [N, +, 0, {1}]. Um zu zeigen, daß eine Aussage H (n) für alle n aus N gilt, genügt es zu zeigen:

A) H (0)

I) Wenn H (n), so H (n + 1).

Verallgemeinern dieser Aussage für Halbgruppen:

Induktionstheorem: Um zu zeigen, daß eine Aussage H auf alle Elemente p einer Halbgruppe [M, ∘, 1, E] mit dem Erzeugendensystem E zutrifft, genügt es zu zeigen

A) H (1)

I) Wenn H (r) und x ∈ E, so H (r ∘ x) mit x Erzeugendes (bzw: Wenn H (r) und x ∈ E , so H (x ∘ r) mit x Erzeugendes

Beweis des Induktionstheorems erfolgt indirekt.

Nehmen wir an, daß es Elemente q ∈ M gibt, auf die H nicht zutrifft. Unter diesen Elementen kommt das Einselement nicht vor, weil H (1) gilt (Anfangsschritt). Jedes dieser Elemente besitzt also eine Darstellung

q = q_{1} ∘ q_{2} ∘ ⋯ ∘ q_{k}

aus Erzeugenden q_{i} ∈ E. Es sei q^{⋆} ein Element mit einer kürzesten Darstellung q^{⋆} = q_{1}^{⋆} ∘ ⋯ ∘ q_{k^{⋆}}^{⋆} (k^{⋆} minimal). Wir setzen q^{⋆⋆} = q_{1}^{⋆} ∘ ⋯ ∘ q_{k^{⋆}−1}^{⋆} falls k^{⋆} ≥ 2 und q^{⋆⋆} = 1 falls k^{⋆} = 1. Wegen der Minimalität von k^{⋆} gilt H (q^{⋆⋆}) und es ist

q^{⋆} = q^{⋆⋆} ∘ q_{k}^{⋆} q_{k^{⋆}}^{⋆} ∈ E

Aus 1) erhalten wir damit H (q^{⋆}); Widerspruch.

Auch das Prinzip der Ordnungstheoretischen Induktion kann auf freie Halbgruppen übertragen werden:

Ordnungstheoretische Induktion [N, ≤]. Um zu zeigen, daß eine Aussage H für alle n ∈ N gilt g.z.z: Wenn H auf alle k < n zutrifft, so trifft H auf n zu.

Definition 1.1.13 (Halbordnung in W (X))

1. p \underline{in} q := dw es gibt Wörter r, s mit q = rps

2. p ⊑ q (p ist Anfangsstück von q) := dw Es gibt s mit q = ps

3. p ⊒ q (p ist Endstück von q) := dw Es gibt r mit q = rp

Satz 1.1.14 [W (X) , \underline{in}], [W (X) , ⊑], [W (X) , ⊒] sind reflexive Halbordnungen.

Beweis

• reflexiv: p \underline{in} p (r, s = e)

• transitiv: p \underline{in} q und q \underline{in} r, so p ∈ q

• antisymetrisch: p \underline{in} q und q \underline{in} p so p = q

Folgerung 1.1.15 Wenn p \underline{in} q so l (p) ≤ l (q). Wenn p ⊑ q so l (p) ≤ l (q). Wenn p ⊒ q so l (p) ≤ l (q).

Ordnungstheoretische Induktion in W (X): Um zu zeigen, daß eine Aussage H auf alle p ∈ W (X) zutrifft, genügt es zu zeigen, daß für alle p gilt:

Wenn für alle r mit r \underline{in} p (bzw. r ⊑ p bzw. r ⊒ p) und r ≠ p stets H (r)

gilt, so gilt H (p).

Nehmen wir an, daß H nicht für alle p ∈ W (X) gilt, dann existiert ein kürzestes Wort p so, daß H nicht auf p zutrifft. Alle r mit r \underline{in} p (bzw. r ⊑ p bzw. r ⊒ p) und r ≠ p sind aber echt kürzer als p, d. h. H trifft auf alle Wörter r zu; folglich trifft H auf p zu. Widerspruch.

Induktion in Algebren: Wir betrachten eine beliebige Algebra [M, Φ, E] mit Erzeugendensystem E. Hierbei ist M eine Menge, Φ ist eine Menge von Abbildungen ϕ : M × ⋯ × M → M und E ist eine Teilmenge von M derart, daß jedes Element von M aus Elementen von E durch Anwendung von Funktionen aus Φ erzeugt werden kann.

Beispiel: [𝔐fin, {+a|a ∈ E} , {∅}], dabei ist die Funktion +a für a ∈ E (Allmenge erster Stufe); N ∈ 𝔐fin definiert als +a (N) := N ∪ {a}. Es ist also zum Beispiel

{a, b, c} = +c (+b (+a (∅))) .

1.1.2 Induktionsbeweise in [M, Φ, E]

Um zu zeigen, daß H (m) für alle m ∈ M gilt, genügt es zu zeigen, daß

1. H (x) für alle Erzeugenden x ∈ E gilt (Anfangsschritt)

2. Für alle ϕ^{n} ∈ Φ, a_{1} …, a_{n} ∈ M mit H (a_{1}) , …, H (a_{n}) gilt H(\underbrace{ϕ^{n} (a_{1}, … a_{n})}_{∈M})

1.1.3 Induktive Definitionen

Eine induktive Definition einer Funktion f im Bereich der natürlichen Zahlen folgt dem Schema

\begin{matrix}f (x_{1}, ⋯, x_{k}, 0) & = & g (x_{1}, ⋯, x_{k}) \\ f (x_{1}, ⋯, x_{k}, n + 1) & = & h (x_{1}, …, x_{k}, n, f (x_{1}, …, x_{k}, n)) \end{matrix} \} (⋆)

Die Definition ist implizit, da f auf der rechten und auf der linken Seite vorkommt. Eine implizite Definition muß gerechtfertigt werden.

Satz 1.1.16 (Dedekindscher Rechtfertigungssatz) Sind g, h Funktionen, so gibt es genau eine Funktion f, die (⋆) erfüllt.

Wir zeigen

1. es existiert eine Funktion f

2. es existiert genau eine Funktion f.

Beweis.

Einzigkeit: Es seien f_{2}, f_{2} Funktionen, die das Gleichungssysthem (⋆) erfüllen. Wir zeigen durch Induktion über i, daß für alle x_{1}, …, x_{k}, i

f_{1} (x_{1}, …, x_{k}, i) = f_{2} (x_{1}, …, x_{k}, i)

ist.

Im Anfangsschritt ist i = 0, also

f_{1} (x_{1}, …, x_{k}, i) = f_{1} (x_{1}, …, x_{k}, 0)
= g (x_{1}, …, x_{k})
= f_{2} (x_{1}, …, x_{k}, 0)
= f_{2} (x_{1}, …, x_{k}, i)

Im Induktionschritt schließen wir von i auf i + 1:

f_{1} (x_{1}, …, x_{k}, i + 1) = h (x_{1}, …, x_{k}, i, f_{1} (x_{1}, … x_{k}, i))
= h (x_{1}, …, x_{k}, i, f_{2} (x_{1}, … x_{k}, i)) (Induktionsvoraussetzung)
= f_{2} (x_{1}, …, x_{k}, i + 1)

Existenz: Zum Beweis der Lösbarkeit des Gleichungssystems lösen wir die induktive Definition in eine unendliche Folge von expliziten Definitionen auf:

f_{0} (x_{1}, …, x_{k}, j) := \{ \begin{matrix}g (x_{1}, …, x_{k}) , & falls j = 0 \\ nicht definiert, & sonst \end{matrix}

f_{1} (x_{1}, …, x_{k}, j) := \{ \begin{matrix}f_{0} (x_{1}, …, x_{k}, j) , & falls j < 1 \\ h (x_{1}, …, x_{k}, 0, f_{0} (x_{1}, … x_{k}, 0)) , & falls j = 1 \\ nicht definiert, & sonst \end{matrix}

⋮
f_{i+1} (x_{1}, …, x_{k}, j) := \{ \begin{matrix}f_{i} (x_{1}, …, x_{k}, j) , & falls j < i + 1 \\ h (x_{1}, …, x_{k}, i, f_{i} (x_{1}, … x_{k}, i)) , & falls j = i + 1 \\ nicht definiert, & sonst \end{matrix}

⋮

Diese sind alles explizite Definitionen, die Funktionen f_{i} existieren also gemäß Mengenbildungsaxiomen. Folglich existiert auch f mit

f (x_{1}, …, x_{k}, i) := f_{i} (x_{1}, …, x_{k}, i)

und es gilt

f (x_{1}, …, x_{k}, 0) = f_{0} (x_{1}, …, x_{k}, 0) = g (x_{1}, …, x_{k})

sowie

f (x_{1}, …, x_{k}, i + 1) = f_{i+1} (x_{1}, …, x_{k}, i + 1)
= h (x_{1}, … x_{k}, i, f_{i} (x_{1}, …, x_{k}, i))
= h (x_{1}, … x_{k}, i, f (x_{1}, …, x_{k}, i))

d. h. f erfüllt das Gleichungssystem (⋆).

Dieses Definitionsprinzip kann auf Worthalbgruppen verallgemeinert werden (also auf beliebige freie Halbgruppen), aber nicht auf beliebige Halbgruppen oder gar auf beliebig erzeugte Algebren.

Es seien 𝔛, 𝔜 beliebige Mengen X ein Alphabet. Um eine Abbildung f : 𝔛 × W (X) → 𝔜 zu definieren genügt es anzugeben

• eine Abbildung g : 𝔛 → 𝔜

• zu jedem x ∈ X eine Abbildung h_{x} : 𝔛 × W (X) × 𝔜 → 𝔜

Die Definition von f sieht dann so aus:

\begin{matrix}f (𝔵, e) & = & g (𝔵) \\ f (𝔵, px) & = & h_{x} (𝔵, p, f (𝔵, p)) \end{matrix} \} \begin{matrix}𝔵 ∈ 𝔛 \\ p ∈ W (X) \\ x ∈ X \end{matrix}

Dieses Gleichungssystem (bestehend aus card (X) + 1 Gleichungen) wird von genau einer Funktion f : 𝔛 × W (X) → 𝔜 erfüllt.

Automaten

2.1 Der Zustandsbegriff in der Systemtheorie

Systeme, deren Reaktion auf einen vorliegenden Reiz nicht nur von diesem aktuellen Reiz sondern auch von früheren Aktionen an ihrer Eingabe abhängt, verfügen demnach über ein Gedächtnis, mit dessen Hilfe sie sich an die relevanten früheren Eingabesignale erinnern, d. h. ihr künftiges Verhalten vom Vorliegen bzw. Nichteintreten dieser Reize abhängig machen.

In diesem Sinne versteht man unter einem (globalen) Systemzustand die Zusammenfassung der Werte aller Parameter, die Einfluß auf das künftige Verhalten haben. Welches diese Parameter sind und was Einfluß bedeutet, hängt natürlich von der Abstraktionsebene ab, auf der das System beschrieben wird.

Bei einem Taschenrechner im normalen Betrieb wird die Temperatur des Gerätes keinen Einfluß auf die Funktionsweise, also nicht als Zustandsparameter gelten. Das ändert sich natürlich bei extremer Kälte oder Hitze.

Wir werden hier nur sogenannte ”diskrete“ Systeme betrachten, d. h. solche, bei denen alle Parameter nur wohlunterscheidbare Werte annehmen können. Ein schwingendes Pendel ist in diesem Sinne kein diskretes System, seine Auslenkung kann kontinuierlich variieren.

Viele informationsverarbeitende Systeme, um die es in der Informatik ja geht, sind aber diskrete Systeme oder können hinreichend genau durch solche approximiert werden.

Beispiele:

• einfacher Fahrkartenautomat

Eingabe eine Münze

Ausgabe eine Fahrkarte oder die Münze

Zustand die Zahl der im Automaten noch vorhandenen Fahrkarten

• Taschenrechner

Eingabe ein Tastendruck

Ausgabe ein Bild auf dem Display

Zustand gegeben durch Belegung der Register und Speicher, i. a. aber nicht durch die Batteriespannung

Der Zustandsbegriff ermöglicht eine exakte globale Beschreibung von Systemen und ihrem Verhalten, die einer theoretischen Behandlung zugänglich ist. Der Nachteil dieses Ansatzes besteht darin, daß die Strukturiertheit des Systems, das ja aus einzelnen Teilsystemen, die sogar zeitweilig unabhängig voneinander arbeiten können, nicht berücksichtigt wird. Die Zahl der Zustände der Telefonvermittlungstechnik einer Stadt oder eines Landes ist zu groß, um noch bei praktischen Problemen berücksichtigt zu werden. Für die Beschreibung ”kleinerer“ Systeme hat sich der Zustandsbegriff bewährt.

2.2 Der Automatenbegriff

Zur Beschreibung eines diskreten Systems, das taktweise arbeitet, wobei die Taktung sowohl durch eine innere Uhr erzeugt als auch durch die Eingabesignale aufgeprägt sein kann, verwenden wir den Begriff des abstrakten Automaten.

Wir versammeln alle Werte, Reize, Signale, Einwirkungen, die auf das System ausgeübt werden können, in einer Menge X, die Menge der Eingabesignale (inputs) genannt wird. Wir verlangen, daß die Menge X nicht leer und endlich ist, denn mit physikalischen Mitteln können nur endlich viele Werte unterschieden werden. Endliche nichtleere Mengen werden auch als Alphabet bezeichnet, dementsprechend wird X auch Eingabealphabet genannt.

Analog wird die Menge Y der Ausgabesignalwerte (das Ausgabealphabet) bestimmt.

Wir gehen davon aus, daß das System in jedem Arbeitstakt genau ein Eingabesignal x∈X entgegennimmt und zu genau einem Ausgabesignal y∈Y verarbeitet.

In welches Ausgabesignal y das eingegebene Signal x transformiert wird, hängt vom Zustand des Systems ab.

Beispiel: Wenn der Fahrkartenautomat eine Münze erhält, gibt er eine Fahrkarte aus, außer er ist in dem Zustand ”ausverkauft“, dann gibt er die Münze wieder aus.

Weil das betrachtete System diskret ist, können wir die Menge Z aller Zustände im oben beschriebenen Sinne bilden. Bei einem realen System ist diese Menge ebenfalls endlich.

Wir wollen uns aber auch mit dem Entwurf von Systemen beschäftigen, z. B. mit der Lösung von Automatisierungsaufgaben. Dabei geht es ja darum, zu einer verbalen Beschreibung des Eingabe- und Ausgabeverhaltens des Systems eine formale Beschreibung als abstrakter Automat zu finden, die man dann nach bestimmten Verfahren in eine konkrete Schaltung umsetzen kann. Dabei erweist es sich häufig als zweckmäßig, auch mit unendlichen Zustandsmengen gedanklich zu spielen, z. B. um die Unlösbarkeit der Aufgabe frühzeitig zu erkennen (was ein unendlicher Automat nicht kann, kann auch kein endlicher).

Definition 2.2.1 𝔄 = [X, Y, Z, δ, λ] ist ein Automat, wenn

1. X, Y Alphabete

2. Z eine nichtleere Menge

3. δ : Z × X → Z (Überführungsfunktion)

4. λ : Z × X → Y (Ergebnisfunktion)

Die Überführungsfunktion δ des Automaten 𝔄 hat als Wert δ(z, x) den Zustand, in den 𝔄 übergeht, wenn 𝔄 im Zustand z das Eingabesignal x erhält; die Ergebnisfunktion λ von 𝔄 hat als Wert λ(z, y) das Ausgabesignal, das von 𝔄 im Zustand z bei Eingabe von x ausgegeben wird.

Wenn also 𝔄 in einem Takt sich im Zustand z_{3} befindet, das Eingabesignal x_{7} eingegeben wird, δ(z_{3}, x_{7}) = z_{2} und λ(z_{3}, x_{7}) = y_{0} ist, so wird 𝔄 y_{0} ausgeben und im nächsten Takt im Zustand z_{2} angetroffen.

2.3 Erweiterung von δ und λ auf Wörter über X

Durch die Automatendefinition ist das Eingabe- und Ausgabeverhalten eines Automaten 𝔄 = [X, Y, Z, δ, λ] explizit für einen Takt gegeben. Im allgemeinen interessiert aber das Verhalten über mehrere Arbeitstakte hinweg, also welche Folge von Ausgabesignalen bei einem gegebenen Anfangszustand und Eingabe einer gewissen Folge p∈W (X) ausgegeben wird und in welchem Zustand sich 𝔄 danach befindet.

Wir erweitern daher den Definitionsbereich von δ und λ von Z×X auf Z×W (X).

Für z∈Z und p∈W (X) soll δ(z, p) der Zustand sein, in dem 𝔄 angetroffen wird, wenn 𝔄 im Zustand z das Wort p verarbeitet hat. Folgende induktive Definition leistet das Verlangte:

Anfangsschritt: δ(z, e) := z

Induktionsschritt: p→xp

δ(z, xp) := δ(δ(z, x), p)

Man zeigt leicht durch Induktion über p, daß für alle p, r∈W (X) gilt:

δ(z, pr) = δ(δ(z, p), r)

Für z∈Z und p∈W (X) soll λ(z, p) das Wort aus W (Y) sein, das 𝔄 bei Start im Zustand z und Eingabe von p ausgibt. Folgende induktive Definition leistet das Verlangte:

Anfangsschritt: λ(z, e) := e

Induktionsschritt: p→xp

λ(z, xp) := λ(z, x)λ(δ(z, x), p)

Man zeigt leicht durch Induktion über p, daß für alle p, r∈W (X) gilt:

λ(z, pr) := λ(z, p)λ(δ(z, p), r)

Ein Automat 𝔄 = [X, Y, Z, δ, λ] wird endlich genannt, wenn Z eine endliche Menge ist (X und Y als endlich vorausgesetzt). Bei einem endlichen Automaten kann man (X, Y und Z als angeordnet vorausgesetzt) die Überführungsfunktion δ und die Ergebnisfunktion λ als Tabellen übergeben.

Beispiel: 𝔄 = [X, Y, Z, δ, λ] mit X = {0, 1}, Y = {0, 1}, Z = {1, 2, 3, 4}

\begin{matrix}δ & 1 & 2 & 3 & 4 & λ & 1 & 2 & 3 & 4 \\ 0 & 2 & 4 & 2 & 3 & 0 & 1 & 0 & 1 & 1 \\ 1 & 3 & 3 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix}

Eine sehr anschauliche Möglichkeit ”kleine“ Automaten anzugeben, besteht darin, den Zustandsgraphen zu zeichnen. Die Zustände des Automaten werden durch Kreise dargestellt (mit der Bezeichnung des Zustandes im Innern), sie bilden die Knotenpunkte des Graphen. Vom Knoten z geht für jedes x∈X ein Bogen zum Knoten δ(z, x), der mit x/λ(z, x) beschriftet ist, also dem diesen Übergang bewirkenden Eingabesignal x und dem dabei ausgegebenen Signal λ(z, x).

Der Zustandsgraph des oben angegebenen Automaten kann wie folgt

aussehen: [figure: 3; 1; 4; 2; 1/0; 1/0; 1/0; 0/1; 0/1; 0/1; 0/0; 1/0]

2.4 Äquivalenz von Zuständen und Automaten

Zwei Zustände z_{1}, z_{2} eines Automaten 𝔄 wird man gleichwertig oder äquivalent nennen, wenn sich das Verhalten von 𝔄 im Zustand z_{1} nicht von dem Verhalten von 𝔄 im Zustand z_{2} unterscheidet, d. h. in beiden Fällen jedes Eingabewort p in dasselbe Ausgabewort λ(z_{1}, p) = λ(z_{2}, p) transformiert wird. Hierbei führen also verschiedene Werte z_{1}, z_{2} des inneren Parameters ”Zustand“ zu demselben Verhalten, d. h. man kann eventuell einen Zustand einsparen. Methoden zur Zustandsreduktion wollen wir in diesem Abschnitt besprechen.

Definition 2.4.1 Es seien 𝔄 = [X, Y, Z, δ, λ] und 𝔄′ = [X, Y, Z′, δ′, λ′] Automaten, z∈Z, z′∈Z′.

1. z, z′ werden äquivalent genannt (z∼z′), wenn für alle p∈W (X) gilt: λ(z, p) = λ′(z′, p′).

2. 𝔄, 𝔄′ werden äuqivalent genannt (𝔄∼𝔄′), wenn zu jedem Zustand z∈Z ein äquivalenter Zustand z′∈Z′ und umgekehrt zu jedem z′∈Z′ ein äquivalenter Zustand z∈Z existiert.

3. 𝔄 heißt reduziert, wenn für alle z_{1}, z_{2}∈Z gilt: wenn z_{1}∼z_{2}, so z_{1} = z_{2}

4. 𝔄′ wird als Reduzierter von 𝔄 bezeichnet, wenn 𝔄′ reduziert und 𝔄∼𝔄′ ist.

Man überlege sich, daß folgendes gilt:

Folgerung 2.4.2 Wenn z_{1}∼z_{2}, so ist für alle p∈W (X) δ(z_{1}, p)∼δ(z_{2}, p).

Unser Ziel besteht also darin, ein Verfahren zu finden, nach dem zu 𝔄 ein Reduzierter gefunden werden kann. Wenn 𝔄 schon reduziert ist, dann ist (wegen 𝔄∼𝔄′) 𝔄 natürlich ein Reduzierter von sich selbst.

2.4.1 Methode 1: Eliminierung von Zuständen

Gegeben sei ein Automat 𝔄 = [X, Y, Z, δ, λ] und Zustände z_{1}, z_{2} mit z_{1} ≠ z_{2}, z_{1}∼z_{2}.

Wir eliminieren den Zustand z_{2}, d. h. wir gehen über zu dem Automaten 𝔄′ = [X, Y, Z′, δ′, λ′] mit:

Z′ := Z \ {z_{2}}
δ′(z′, x) := \{ \begin{matrix}δ(z′, x), & falls δ(z′, x) ≠ z_{2} \\ z_{1} , & sonst \end{matrix}
λ′(z′, x) := λ(z′, x),

für alle x∈X, z′∈Z′.

Offenbar ensteht 𝔄′ aus 𝔄, indem in 𝔄 der Zustand z_{2} gestrichen wird und alle Bögen des Zustandsgraphen, die in z_{2} einmünden, nach z_{1} umgelenkt werden.

Man zeigt, daß 𝔄′∼𝔄 ist, indem man zeigt, daß für jedes z′∈Z′ der Zustand z′ in 𝔄′ äquivalent zum Zustand z′ in 𝔄 ist; für alle z′∈Z, p∈W (X):

λ′(z′, p) = λ(z′, p)

Weil z_{1}∼z_{2} ist also z_{1} ein zu z_{2} äquivalenter Zustand von 𝔄.

In unserem Beispiel ist 1∼3; wenn wir den Zustand 3 eliminieren, erhal-

ten wir [figure: 1; 4; 2; 1/0; 0/1; 0/1; 1/0; 0/0; 1/0]

Diese Methode kann natürlich nur dann zu einem Reduzierten führen, wenn in 𝔄 nur endlich viele Paare z_{1}, z_{2} mit z_{1}∼z_{2} existieren; wenn dagegen 𝔄 unendlich viele Zustände hat, aber einen endlichen Reduzierten 𝔄′, so werden wir 𝔄′ nicht in endlich vielen Eliminationsschritten finden können.

Wenn wir den Fall betrachten, daß drei Zustände z_{1}, z_{2}, z_{3} paarweise äquivalent sind und keiner der übrigen Zustände zu z_{1} oder z_{2} oder z_{3} äquivalent ist (d. h. {z_{1}, z_{2}, z_{3}} ist eine volle Äquivalenzklasse von ∼ in Z), dann können wir in zwei aufeinanderfolgenden Eliminationsschritten z_{3} und z_{2} eliminieren, es bleibt z_{1} übrig als Repräsentant der Klasse {z_{1}, z_{2}, z_{3}}. Dabei ist die Wahl von z_{1} zufällig, wir hätten auch z_{2}, z_{1} eliminieren können. Diese Operation kann man sich auch als Verschmelzen aller Zustände einer Äquivalenzklasse zu einem neuen Zustand vorstellen, die Basis der folgenden allgemeinen algebraischen Reduktion.

2.4.2 Methode 2: Algebraische Reduktion

Zu jeder Äquivalenzrelation in Z, also auch zur Zustandsäquivalenz in 𝔄 = [X, Y, Z, δ, λ], existiert genau eine Zerlegung von Z in Äquivalenzklassen. Die Äquivalenzklasse, in welcher der Zustand z liegt, bezeichnen wir mit

[z] := {z′| z′ ∈ Z ∧ z′ ∼ z}

und die Zerlegung von Z mit

Z/_{∼} := {[z]| z ∈ Z}

Wir betrachten den Automaten \overline{𝔄} = [X, Y, \overline{Z}, \overline{δ}, \overline{λ}] mit

\overline{Z} := Z/_{∼}

und für [z] ∈ \overline{Z}, x ∈ X

\overline{δ}([z], x) := [δ(z, x)]
\overline{λ}([z], x) := λ(z, x)

Für diese Definitionen muß die Unabhängigkeit vom Repräsentanten z der Klasse [z] bewiesen werden:

Wenn [z] = [z′], so [δ(z, x)] = [δ(z′, x)] und λ(z, x) = λ(z′, x). Nun ist [z] = [z′] genau dann, wenn z ∼ z′ ist. Aus z ∼ z′ folgt λ(z, x) = λ(z′, x) nach Definition der Zustandsäquivalenz und δ(z, x) ∼ δ(z′, x) (vgl. Folgerung 2.4.2) daraus wiederum [δ(z, x)] = [δ(z′, x)].

Wir zeigen jetzt durch Induktion über p, daß für alle z ∈ Z gilt:

λ(z, p) = \overline{λ}([z], p)

d. h. der Zustand z von 𝔄 ist äquivalent zum Zustand [z] in \overline{𝔄}.

Anfangsschritt: p = e Die Gleichung λ(z, e) = \overline{λ}([z], e) ist trivial.

Induktionsschritt: p → xp Es ist

λ(z, xp) = λ(z, x) λ(δ(z, x), p)  (Induktionsdefinition von λ)
= \overline{λ}([z], x) λ(δ(z, x), p)  (Definition von \overline{λ})
= \overline{λ}([z], x) \overline{λ}([δ(z, x)], p) (Induktionsvoraussetzung)
= \overline{λ}([z], x) \overline{λ}(\overline{δ}([z], x), p)  (Definition von \overline{δ})
= \overline{λ}([z], xp)  (Induktionsdefinition von \overline{λ})

Die Automaten 𝔄 und \overline{𝔄} sind also äquivalent, es bleibt zu zeigen, daß \overline{𝔄} reduziert ist; das ergibt sich wie folgt: Ist [z_{1}] ∼ [z_{2}] in \overline{𝔄}, so ist z_{1} ∼ [z_{1}] ∼ [z_{2}] ∼ z_{2}, also z_{1} ∼ z_{2} in 𝔄, d. h. [z_{1}] = [z_{2}].

2.5 Berechnung der Äquivalenzklassen

Um zu einem endlichen Automaten 𝔄 = [X, Y, Z, δ, λ] einen Reduzierten konstruieren zu können, benötigen wir (sowohl bei der Methode 1 als auch bei der Methode 2) eine Übersicht über die Äquivalenzklassen, d. h. Z/_{∼}. Nach Definition sind z, z′ ∈ Z äquivalent, wenn für alle unendlich vielen p ∈ W (X) stets λ(z, p) = λ(z′, p) ist. Weil der Automat 𝔄 nur endlich viele Zustände hat, besteht aber die Hoffnung, daß dies schon gilt, wenn die Gleichung für alle p ∈ W (X) einer gewissen Länge gilt.

Definition 2.5.1 Sei i ≥ 1 Zustände z, z′ ∈ Z heißen i-äquivalent (z ∼_{i} z′), wenn für alle p ∈ W (X) mit l(p) ≤ i gilt: λ(z, p) = λ(z′, p).

In unserem Beispiel sind die Zustände 1 und 4 offenbar 1-äquivalent, denn für alle x ∈ {0, 1} ist λ(1, x) = λ(4, x). Man zeigt nun, daß folgendes gilt:

1. Wenn z ∼_{i+1} z′, so z ∼_{i} z′ (d. h. jede Klasse aus Z/_{∼_{i+1}} ist Teilmenge einer Klasse

aus Z/_{∼_{i}} ).

2. Wenn z ∼_{i+1} z′, so ist für alle x ∈ X stets δ(z, x) ∼_{i} δ(z′, x) (d. h. bei jedem x ∈ X ist das δ-Bild einer KLasse aus Z/_{∼_{i+1}} ganz in einer Klasse Z/_{∼_{i}} enthalten).

3. Wenn z ∼_{i} z′ und für alle x ∈ X ist δ(z, x) ∼_{i} δ(z′, x), so ist z ∼_{i+1} z′.

4. Wenn ∼_{i} = ∼_{i+1} , so ∼_{i+1} = ∼_{i+2} (d. h. wenn Zustände z, z′ genau dann iäquivalent sind, wenn sie (i + 1)-äquivalent sind, bzw. Z/_{∼_{i}} = Z/_{∼_{i+1}} ist, dann

ist Z/_{∼_{i}} = Z/_{∼_{i+j}} für alle j).

5. z ∼ z′ gdw. für alle i: z ∼_{i} z′.

Es genügt also zu zeigen, daß es eine Zahl j so gibt, daß Z/_{∼_{j}} = Z/_{∼_{j+1}} ist, dann ist

ja Z/_{∼_{j}} = Z/_{∼}.

Wenn im Automaten 𝔄 alle Zustände paarweise 1-äquivalent sind, dann ist Z/_{∼_{1}} =

{Z}, folglich sind nach 3. alle Zustände paarweise 2-äquivalent, d. h. Z/_{∼_{1}} = Z/_{∼_{2}} ,

d. h. j = 1 leistet das Verlangte. Andernfalls hat die Zerlegung Z/_{∼_{1}} wenigstens 2

Klassen. Wenn Z/_{∼_{2}} ≠ Z/_{∼_{1}} ist, so hat Z/_{∼_{2}} wenigstens 3 Klassen, weil jede Klasse

von Z/_{∼_{2}} ganz in einer Klasse von Z/_{∼_{1}} enthalten ist. In dieser Weise schließt man weiter und erhält:

6. Wenn Z/_{∼_{i}} ≠ Z/_{∼_{i+1}} , so hat Z/_{∼_{i}} wenigstens (i + 1) Klassen. Die Zahl der Klassen, in die Z zerlegt werden kann, ist aber durch die Zahl n der Zustände von 𝔄 beschränkt, d. h. es gilt (j = n − 1).

7. Z/_{∼_{n−1}} = Z/_{∼_{n}} .

Damit ist gezeigt, daß z ∼ z′ gdw. für alle p ∈ W (X) mit l(p) ≤ n − 1 gilt λ(z, p) = λ(z′, p).

Diese Überlegungen führen zu folgendem Algorithmus zur Berechnung aller Zweiermengen {z, z′} mit z ∼ z′.

a. Herstellen der Datenstruktur Anhand der Tabelle von λ bestimmen wir alle Zweiermengen {z, z′} von Zuständen von 𝔄 mit z ∼_{1} z′ und schreiben diese in die erste Spalte einer Tabelle. In einer zweiten Spalte dieser Tabelle schreiben wir hinter die Menge {z, z′} der ersten Spalte alle Mengen der Form {δ(z, x), δ(z′, x)}, sofern δ(z, x) ≠ δ(z′, x).

Für unser Beispiel ergibt sich die Tabelle:

0  1
{1, 3} − {1, 3}
{1, 4} {2, 3} {1, 3}
{3, 4} {2, 3} −

b. Abarbeitungsschritt Streiche in der zweiten Spalte alle Mengen, die in der ersten Spalte nicht vorkommen. Streiche danach in der ersten Spalte alle Mengen hinter denen eine Menge gestrichen wurde. Wiederhole dies, bis sich nichts mehr ändert.

Die Mengen, die in der ersten Spalte stehenbleiben, enthalten je zwei äquivalente Zustände. In unserem Beispiel bleibt genau die Menge {1, 3} stehen. Damit ergibt sich

Z/_{∼} = { {1, 3} , {2} , {4} }

2.6 Eingabe-/Ausgabeverhalten

Unter einer Wortfunktion über [X, Y] verstehen wir eine (eindeutige) Abbildung, die jedem Wort p ∈ W (X) (genau) ein Wort q ∈ W (Y) zuordnet. Wenn wir bei einem gegebenen Automaten 𝔄 = [X, Y, Z, δ, λ] einen Zustand z ∈ Z als Anfangszustand fixieren, so berechnet 𝔄 eine solche Wortfunktion: dem Eingabewort p ∈ W (X) wird als Wert das Ausgabewort λ(z, p) zugeordnet.

Definition 2.6.1 Die vom Zustand z ∈ Z in 𝔄 = [X, Y, Z, δ, λ] erzeugte Wortfunktion φ ist gegeben durch

φ(p) := λ(z, p) (für alle p ∈ W (X)).

Viele Aufgaben zur Konstruktion eines Automaten, der ein bestimmtes Verhalten haben soll, gehen von der Beschreibung dieses Verhalten durch eine Wortfunktion aus.

Beispiel: Sequentieller Adder

X = \{\binom{0}{0}, \binom{0}{1}, \binom{1}{0}, \binom{1}{1}\}; Y = \{0, 1\}

φ(x_{1} x_{2} … x_{n}) = φ (\binom{a_{1}}{b_{1}} … \binom{a_{n}}{b_{n}})

= Dualdarstellung von ∑_{i=1}^{n}(a_{i} + b_{i})2^{i−1}

(wobei eventuell der letzte Übertrag verloren geht: φ\binom{1 1}{1 0} = 0 0)

Lösung:

[figure: 0; 1; \binom{1}{1}/0; \binom{0}{0}/1; \binom{0}{0}/0 , \binom{1}{0}/1 , \binom{0}{1}/1; \binom{1}{0}/0 , \binom{0}{1}/0 , \binom{1}{1}/1]

Nicht immer kann man sofort erkennen, daß sich eine Wortfunktion in einem Automaten erzeugen läßt; wir interessieren uns daher für ein Kriterium für diese Eigenschaft.

Es sei φ in 𝔄 durch z erzeugt. Dann gilt

(I) (Längeninvarianz) Für alle p ∈ W (X) ist l(φ(p)) = l(p).

(II) (Sequentialität) Für alle p, r ∈ W (X) ist φ(p) ein Anfangsstück von φ(pr): φ(p) ⊑ φ(pr).

Die Längeninvarianz folgt aus der taktweisen Arbeitsweise von 𝔄; die Sequentialität gilt, weil

φ(pr) = λ(z, pr) = λ(z, p)λ(δ(z, p), r) = φ(p)λ(δ(z, p), r)

ist.

Wir behaupten nun, daß diese beiden Bedingungen nicht nur notwendig, sondern auch hinreichend für die Erzeugbarkeit von φ in einem (i. a. unendlichen) Automaten sind.

Satz 2.6.2 Es sei φ : W (X) → W (Y) eine längeninvariante sequentielle Wortfunktion. Dann gibt es einen Automaten 𝔄_{φ} = [X, Y, Z, δ_{f}, λ_{φ}] und einen Zustand z ∈ Z, der φ in 𝔄_{φ} erzeugt.

Beweis: Wir konstruieren einen sogenannten ”freien Automaten“, genauer einen Automaten, bei dem die Zustandsüberführung frei von nichttrivialen Gleichungen ist:

Wenn δ(z, p) = δ(z, r), so p = r

Die Idee der Konstruktion ist, daß der Automat sich das gesamte Eingabewort p in seinem Zustand merkt und auf der Basis dieser Information und des aktuellen Eingabesignals x den letzten Buchstaben des Wortes φ(px) ausgibt. Wir setzen also:

Z := W (X)  (unendlich!)
für p ∈ Z, x ∈ X : δ_{f}(p, x) := px
λ_{φ}(p, x) := der letzte Buchstabe von φ(px)

Wir zeigen, daß der Zustand z = e die Funktion φ in 𝔄 erzeugt. Dazu beweist man durch Induktion über p, daß für alle p ∈ W (X) gilt:

δ_{f}(e, p) = p  (2.1)

Wir zeigen die Gleichung φ(p) = λ_{φ}(e, p) durch Induktion über p.

Anfangsschritt: p = e

Es ist  φ(e) = e  (weil e das einzige Wort der Länge 0 ist)
= λ_{φ}(e, e) (nach Definition von λ)

Induktionsschritt: p → px

λ_{φ}(e, px) = λ_{φ}(e, p) λ_{φ}(δ_{f}(e, p), x)
= φ(p) λ_{φ}(p, x)  (Induktionsvoraussetzung und (2.1))

= φ(px) (weil φ(p), φ(px) sich nur um einen Buchstaben unterscheiden, λ_{φ}(p, x) dieser Buchstabe ist und φ(px) mit φ(p) anfängt)

Eine Wortfunktion ist demnach genau dann erzeugbar, wenn sie längeninvariant und sequentiell ist. Aus diesen Eigenschaften folgt aber nicht die Erzeugbarkeit in einem endlichen Automaten!

Beispiel: X = {|}, Y = {0, 1}, φ^{∗}(x_{1} ⋯ x_{n}) := y_{1} ⋯ y_{n}, wobei

y_{i} := \{ \begin{matrix}0, & falls i nicht Quadratzahl \\ 1, & falls i Quadratzahl ist \end{matrix}

Es ist also z. B.

φ^{∗}(|||||) = 10010

Offenbar ist φ längeninvariant und sequentiell. Nehmen wir an, daß φ in einem endlichen Automaten mit k Zuständen erzeugbar ist, etwa durch den Zustand z_{1}. Es sei

z_{2} := δ(z_{1}, |)
⋮
z_{i+1} := δ(z_{i}, |)

allgemein

z_{i} := δ(z_{1}, \underbrace{| ⋯ |}_{i−1})

Weil 𝔄 nur k Zustände hat, gibt es Zahlen i < j ≤ k mit z_{i} = z_{j}. Wir wählen i, j minimal. Der Zustandsgraph von 𝔄 hat die folgende Gestalt:

[figure: z_{1}; z_{2}; z_{i−1}; z_{i}; z_{i+1}; z_{j−1}; ⋯; ⋯]

Sobald der Automat ein Eingabewort p mit l(p) > i bekommen hat, arbeitet er im Zyklus z_{i}, z_{i+1}, ⋯, z_{j−1}, z_{i} und gibt folglich periodisch Nullen und Einsen aus, die Menge der Quadratzahlen ist aber nicht periodisch, vielmehr vergrößert sich der Abstand zweier konsekutiver Quadratzahlen laufend.

Gefragt ist also ein Kriterium dafür, daß eine längeninvariante und sequentielle Wortfunktion sogar in einem endlichen Automaten erzeugbar ist.

Um ein solches Kriterium zu finden, stellen wir folgende Überlegung an. Wenn φ in einem endlichen Automaten 𝔄^{∗} = [X, Y, Z^{∗}, δ^{∗}, λ^{∗}] durch z^{∗} erzeugbar ist, dann ist φ auch in 𝔄_{φ} durch e erzeugbar. In welcher Beziehung stehen 𝔄_{φ} und 𝔄^{∗}? Klar ist, daß e in 𝔄_{φ} äquivalent zu z^{∗} in 𝔄^{∗} ist, denn für alle p ∈ W (X) gilt

λ_{φ}(e, p) = φ(p) = λ^{∗}(z^{∗}, p)

Aus e ∼ z^{∗} folgt aber für alle p ∈ W (X)

p = δ_{f}(e, p) ∼ δ^{∗}(z^{∗}, p)

Also existiert zu jedem Zustand p von 𝔄_{φ} ein äquivalenter Zustand (nämlich δ^{∗}(z^{∗}, p)) in 𝔄^{∗}.

Umgekehrt können wir annehmen, daß

a) 𝔄^{∗} reduziert ist

b) jeder Zustand z^{∗∗} ∈ Z^{∗} von 𝔄^{∗} vom Zustand z^{∗} aus erreichbar ist, d. h. die Form δ^{∗}(z^{∗}, r) für ein r ∈ W (X) hat (nicht von z^{∗} erreichbare Zustände können weggelassen werden).

Unter diesen Voraussetzungen ist 𝔄_{φ} ∼ 𝔄^{∗}, d. h. 𝔄^{∗} ist ein Reduzierter von 𝔄_{φ}.

Wir erhalten also

Satz 2.6.3 Es sei φ : W (X) → W (Y) eine längeninvariante und sequentielle Wortfunktion. φ ist genau dann in einem endlichen Automaten erzeugbar, wenn 𝔄_{φ} einen endlichen Reduzierten besitzt.

Gefragt ist also ein Kriterium dafür, daß W (X) durch die Zustandsäquivalenz in 𝔄_{φ} in nur endlich viele Klassen zerlegt wird:

p ∼_{φ} q ↔ ∀ r ∈ W (X) λ_{φ}(p, r) = λ_{φ}(q, r)

Die Zustände p, q sind äquivalent in 𝔄_{φ}, wenn sie in 𝔄_{φ} die gleiche Wortfunktion erzeugen. In welcher Beziehung steht die von p in 𝔄_{φ} erzeugte Wortfunktion zu φ?

Definition 2.6.4

1. Für q, s ∈ W (Y) sei

⊏\frac{q}{s} := \{ \begin{matrix}u , & falls q = su (also s ⊑ q) \\ nicht definiert , & sonst \end{matrix}

( ⊏ \frac{q}{s} ist also das Wort, das aus q durch Weglassen des Anfangsstückes s entsteht).

2. Es sei φ eine sequentielle Wortfunktion, p ∈ W (X). Das zu p gehörige Derivat φ_{p} von φ ist eine Wortfunktion, die wie folgt für r ∈ W (X) definiert ist:

φ_{p}(r) =⊏\frac{φ(pr)}{φ(p)}

Man zeigt sofort

1. φ_{e} = φ

2. (φ_{p})_{r} = φ_{pr}

3. Der Zustand p von 𝔄_{φ} erzeugt das Derivat φ_{p} von φ.

Also besitzt 𝔄_{φ} genau dann einen endlichen Reudzierten, wenn φ die Bedingungen (I), (II) (auf Seite 16) und

(III) {φ_{p}|p ∈ W (X)} ist endlich

erfüllt.

Übung: Man zeige, daß jede sequentielle und längeninvariante Wortfunktion φ : W (X) → W (Y) durch den Zustand φ_{e} = φ in dem Automaten [X, Y, {φ_{p}|p ∈ W (X)}, δ̂, λ̂] erzeugt wird, wobei

δ̂(φ_{p}, x) = φ_{px}
λ̂(φ_{p}, x) = φ_{p}(x)

gesetzt ist.

Wir zeigen nun noch, daß die oben betrachtete Wortfunktion φ^{∗} unendlich viele Derivate hat. Zur Vereinfachung der Schreibweise nutzen wir die Isomorphie zwischen [W ({|}), ·, e] und [N, +, 0], schreiben also einfach j für das Wort der Länge j über dem Alphabet {|}. Wir zeigen

Wenn φ_{i}^{∗} = φ_{j}^{∗}, so i = j

(die Umkehrung ist trivial).

Aus φ_{i}^{∗} = φ_{j}^{∗} folgt für alle k φ_{i}^{∗}(k) = φ_{j}^{∗}(k)

Betrachten wir nun den letzten Buchstaben dieses Wortes, der offenbar genau dann 1 ist, wenn i + k bzw. j + k Quadratzahl ist; es gilt also für alle k: (i + k) ist Quadratzahl gdw. (j + k) Quadratzahl ist.

Es sei l^{2} = i + k. dann ist (l + 1)^{2} = l^{2} + 2l + 1, also (l + 1)^{2} = i + (k + 2l + 1) ist die nächste Quadratzahl. Weil i + k Quadratzahl ist, ist j + k = n^{2} für ein gewisses n, und j+(k+2l+1) muß die nächste Quadratzahl sein, etwa j+(k+2l+1) = (n+1)^{2}. Hieraus folgt

j + k + 2l + 1 = (n + 1)^{2} = n^{2} + 2n + 1 = j + k + 2n + 1

also l = n, d. h. i + k = j + k, also i = j.

Regelsprachen und Automaten

3.1 Akzeptoren

Jede längeninvariante und sequentielle Wortfunktion φ : W (X) → W (Y) ist bereits eindeutig bestimmt durch die Angabe, welches der letzte Buchstabe des Ausgabewortes bei gegebenem nichtleeren Eingabewort ist:

zu φ : W (X) → W (Y) sei
ψ : (W (X) \ {e}) → Y mit
ψ_{φ}(px) := φ_{p}(x) ∈ Y  (p ∈ W (X), x ∈ X)

definiert.

Ist umgekehrt ψ : (W (X) \ {e}) → Y eine Wort–Buchstaben–Funktion, so ist φ_{ψ} : W (X) → W (Y) mit

φ_{ψ}(x_{1}x_{2} ⋯ x_{n}) := ψ(x_{1})ψ(x_{1}x_{2}) ⋯ ψ(x_{1}x_{2} ⋯ x_{n})

eine sequentielle und längeninvariante Wortfunktion und es gilt

ψ_{φ_{ψ}} = ψ

Die sequentiellen und längeninvarianten Wortfunktionen einerseits und die Wort– Buchstaben–Funktionen andererseits sind einander auf diese Weise eindeutig zugeordnet.

Eine Funktion ψ : (W (X) \ {e}) → Y kann offenbar beschrieben werden durch die Zerlegung {L_{y}|y ∈ Y } von W (X) \ {e} mit

L_{y} = {r|r ∈ W (X) \ {e} ∧ ψ(r) = y}

Mit anderen Worten, die Funktion ψ klassifiziert die nichtleeren Wörter r, in eine Klasse fallen alle Wörter, die auf das gleiche Ausgabesignal abgebildet werden. Ein Automat, der die Funktion ψ (bzw. φ_{ψ}) erzeugt, muß dieses klassifikatorische Verhalten ebenfalls realisieren. Eine Aufklärung des klassifikatorischen Verhaltens endlicher Automaten vertieft also unsere Kenntnis der Struktur der Funktionen, die von endlichen Automaten erzeugt werden können.

Akzeptoren sind Automaten, die eine binäre Klassifikation (in zwei Klassen) durchführen, d. h. die für jedes Eingabewort eine ja–nein–Entscheidung treffen. Eine solche Entscheidung trifft jeder Compiler über die ihm vorgelegte Kette von Zeichen einer Programmiersprache, ob sie nämlich ein syntaktisch richtiges Programm ist (dann wird sie übersetzt) oder nicht.

Die Frage, der wir uns jetzt zuwenden, lautet also: Was leisten endliche Automaten als Akzeptoren? Wie ist ihr klassifikatorisches Verhalten charakterisiert?

Ist 𝔄 = [X, Y, Z, δ, λ] ein (eventuell endlicher) Automat, so kann ein zu 𝔄 äquivalenter (endlicher) Moore–Automat 𝔄′ = [X, Y, Z′, δ′, λ′] konstruiert werden (der also dasselbe Eingabe–Ausgabe–Verhalten hat, folglich auch die gleiche Klassifikation durchführt) bei dem eine Abbildung μ′ : Z′ → Y so existiert, daß

λ′(z′, x) = μ′(δ′(z′, x))

stets gilt. Das (letzte) Ausgabesignal hängt also nur von dem Zustand δ′(z′, x) ab, in den der Automat bei der Ausgabe von y übergeht. Ist Y = {ja, nein}, so können wir also die Klasse der akzeptierten Wörter angeben als Menge der Wörter, die den Automaten in einen Zustand z′ versetzen mit μ(z′) = ja. Diese Überlegung führt zur folgenden Definition:

Definition 3.1.1

1. 𝔄 = [X, Z, δ, z_{0}, M] ist ein Akzeptor, wenn

(a) X ≠ ∅ eine endliche Menge (Eingabealphabet)

(b) Z eine Menge von Zuständen mit z_{0} ∈ Z (Anfangszustand)

(c) δ : Z × X → Z die Überführungsfunktion und

(d) M ⊆ Z (Menge der Akzeptierungszustände) ist.

2. Jede Teilmenge L ⊆ W (X) bezeichnen wir als Sprache über X. Die vom Akzeptor 𝔄 akzeptierte Sprache L(𝔄) ist

L(𝔄) := {p|p ∈ W (X) ∧ δ(z_{0}, p) ∈ M}

die Menge aller Eingabewörter, die den Automaten aus seinem Anfangszustand in einen Akzeptierungszustand versetzen.

3. 𝔄 heißt endlich, wenn Z eine endliche Menge ist.

Uns interessieren natürlich besonders die Sprachen, die von endlichen Akzeptoren akzeptiert werden. Um zu einer Charakterisierung zu kommen, gehen wir wie bei Wortfunktionen vor, d. h. wir zeigen

(a) Jede Sprache besitzt einen freien Akzeptor

(b) Eine Sprache besitzt einen endlichen Akzeptor genau dann, wenn der freie Akzeptor einen endlichen Reduzierten hat (wobei diese Aussage dann ohne Bezug auf Akzeptoren formuliert wird). zu (a) Es sei L eine beliebige Teilmenge von W (X). Für den freien Akzeptor 𝔄_{L} = [X, W (X), δ_{f}, e, L] mit

δ_{f}(p, x) := px (p ∈ W (X), x ∈ X)

gilt offensichtlich δ_{f}(e, p) = p für alle p ∈ W (X), so daß

\begin{aligned}L(𝔄) & = & \{p|p ∈ W (X) ∧ δ_{f}(e, p) ∈ L\} \\ & = & \{p|p ∈ W (X) ∧ p ∈ L\} = L \end{aligned}

ist.

Wenn wir 𝔄_{L} reduzieren wollen, müssen wir uns überlegen, wann Zustände p, q von 𝔄_{L} beim Akzeptieren von L gleichwertig (äquivalent) sind. p (bzw. q) ist der Zustand von 𝔄_{L}, bei dem p (bzw. q) bereits eingegeben wurde. Wenn wir diese Zustände identifizieren wollen, d. h. vergessen, ob p oder ob q eingegeben wurde, muß für jede Fortsetzung r ∈ W (X) (die ja den Zustand p in pr und den Zustand q in qr überführt) pr genau dann akzeptiert werden, wenn qr akzeptiert wird (dann können p und q nicht unterschieden werden).

Definition 3.1.2 (Nerode–Äquivalenz ∼_{L}) Die Wörter p, q ∈ W (X) heißen äquivalent bzgl. L (p ∼_{L} q), wenn gilt:

∀r(r ∈ W (X) → (pr ∈ L ↔ qr ∈ L))

Offenbar ist ∼_{L} eine Äquivalenzrelation in W (X) und es gilt:

1. (Rechtsinvarianz)

Wenn p ∼_{L} q und r ∈ W (X) so pr ∼_{L} qr.

2. L ist eine Vereinigung von Äquivalenzklassen der Relation ∼_{L}, d. h. wenn

p ∈ L und p ∼_{L} q (d. h. p, q liegen in der gleichen Äquivalenzklasse), so q ∈ L.

Satz 3.1.3 (von Nerode) Es sei L ⊆ W (X) eine Sprache. Dann sind die folgenden Aussagen gleichwertig:

(i) L besitzt einen endlichen Akzeptor

(ii) Es gibt eine rechtsinvariante Äquivalenzrelation R über W (X), die nur endlich viele Äquivalenzklassen besitzt derart, daß L Vereinigung von Äquivalenzklassen ist.

(iii) ∼_{L} hat nur endlich viele Äquivalenzklassen (ist von endlichem Rang).

Den Beweis führen wir in drei Schritten, wir zeigen (i) → (ii), (ii) → (iii), (iii) → (i).

(i) → (ii): Es sei 𝔄 = [X, Z, δ, z_{0}, M] ein endlicher Akzeptor mit L = L(𝔄). Wir betrachten die Relation R über W (X) mit

p R q ↔ δ(z_{0}, p) = δ(z_{0}, q)

Offensichtlich ist R eine Äquivalenzrelation und rechtsinvariant.

Für z ∈ Z ist L_{z} := {p|δ(z_{0}, p) = z} enweder leer (ein Übergang von z_{0} nach z ist nicht möglich) oder eine Äquivalenzklasse nach R und alle Äquivalenzklassen haben diese Form. Weil Z endlich ist, ist also R von endlichem Rang (hat nur endlich viele Äquivalenzklassen). Ferner ist:

L = ⋃_{z∈M} L_{z}

also eine Vereinigung von Äquivalenzklassen nach R. Damit ist (ii) bewiesen.

(ii) → (iii): Gegeben ist eine rechtsinvariante Äquivalenzrelation R über W (X) von endlichem Rang und L ist Vereinigung von Äquivalenzklassen.

Wir zeigen, daß ∼_{L} höchstens soviele Äquivalenzklassen hat wie R, indem wir beweisen

p R q → p ∼_{L} q

d. h. jede Äquivalenzklasse nach R ist ganz in einer Äquivalenzklasse nach ∼_{L} enthalten.

Es sei also p, q ∈ W (X) mit p R q. Zu zeigen ist für beliebiges r ∈ W (X)

pr ∈ L ↔ qr ∈ L

Aus Symmetriegründen genügt es zu zeigen

pr ∈ L → qr ∈ L

Aus p R q folgt wegen der Rechtsinvarianz von R

pr R qr

Weil L Vereinigung von Äquivalenzklassen nach R ist, folgt aus pr ∈ L und pr R qr stets qr ∈ L, was zu zeigen war.

(iii) → (i): Die Relation ∼_{L} hat nur endlich viele Äquivalenzklassen, wir werden sie als Zustände des Akzeptors benutzen.

Die Äquivalenzklasse von W (X) nach ∼_{L}, in der das Wort p liegt, bezeichnen wir mit [p]. Wir setzen

Z := W (X)/_{∼_{L}} = {[p]|p ∈ W (X)}
z_{0} := [e]
δ([p], x) := [px]
M := {[p]|p ∈ L}
𝔄 = [X, Z, δ, z_{0}, M]  𝔄 ist der Reduzierte von 𝔄_{L}

Zur Rechtfertigung der Definition von δ muß die Unabhängigkeit von Repräsentanten p der Klasse [p] gezeigt werden:

p ∼_{L} q → px ∼_{L} qx

das folgt unmittelbar aus der Rechtsinvarianz von ∼_{L}.

Die Definition von M ist dadurch gerechtfertigt, daß L Vereinigung von Klassen

nach ∼_{L} ist:

p ∼_{L} q → (p ∈ L ↔ q ∈ L)

Man zeigt nun, daß für p ∈ W (X) gilt

δ([e], p) = [p]

Damit ist

L(𝔄) = {p|p ∈ W (X) ∧ δ([e], p) ∈ M}
= {p|p ∈ W (X) ∧ [p] ∈ M}
= {p|p ∈ W (X) ∧ p ∈ L}  = L

Definition 3.1.4 Eine Sprache L ⊆ W (X) heißt regulär, wenn sie einen endlichen Akzeptor besitzt. Mit REG bezeichnen wir die Klasse aller regulären Sprachen.

Eine Sprache L ist also genau dann regulär, wenn die Nerodesche Relation ∼_{L} nur

endlich viele Äquivalenzklassen hat. Diese Charakterisierung ist insofern unhandlich, als wir über die Äquivalenzklassen nach ∼_{L} (i. a. sind das unendliche Mengen) nicht verfügen.

Wir streben daher eine Charakterisierung der Klasse REG aller regulären Sprachen an, die konstruktiv in dem Sinne ist, daß aus einer Konstruktionsbeschreibung einer regulären Sprache ein endlicher Akzeptor für diese Sprache gewonnen werden kann und umgekehrt.

Dazu benötigen wir eine Reihe von (Konstruktions-)Operatoren, die auf reguläre Sprachen angewendet, reguläre Sprachen als Resultat liefern.

Satz 3.1.5 REG ist abgeschlossen gegenüber Durchschnitt, Vereinigung und Komplement.

Beweis: Es ist für L, L′ ∈ REG zu zeigen, daß die Sprachen L ∩ L′, L ∪ L′ und \overline{L} := W (X) \ L regulär sind. Ist L = L(𝔄) mit 𝔄 = [X, Z, δ, z_{0}, M] so ist offenbar \overline{L} = L(\overline{𝔄}) mit \overline{𝔄} = [X, Z, δ, z_{0}, Z \ M]. Weil L ∪ L′ = \overline{\overline{L} ∩ \overline{L′}} ist, genügt es zu zeigen, daß L ∩ L′ regulär ist.

Es sei L′ = L(𝔄′) mit 𝔄′ = [X, Z′, δ′, z′_{0}, M′]. Wir betrachten die Parallelschaltung von 𝔄 und 𝔄′:

𝔄 × 𝔄′ = [X, Z × Z′, δ^{∗}, [z_{0}, z′_{0}], M^{∗}]

mit

δ^{∗}([z, z′], x) := [δ(z, x), δ′(z′, x)]

und

M^{∗} = {[z, z′]|z ∈ M ∧ z′ ∈ M′}

Man zeigt leicht, daß

L(𝔄 × 𝔄′) = L ∩ L′

ist.

Definition 3.1.6 (Produkt von Sprachen) Es seien L_{1}, L_{2} Sprachen. Dann ist

L_{1}L_{2} = {pq|p ∈ L_{1} ∧ q ∈ L_{2}}

Satz 3.1.7 REG ist abgeschlossen gegenüber dem Produkt, d.h. wenn L_{1}, L_{2} ∈ REG, so L_{1}L_{2} ∈ REG.

Beweis: Für i = 1, 2 sei 𝔄_{i} = [X, Z_{i}, δ_{i}, z_{0}_{i}, M_{i}] ein endlicher Akzeptor mit L_{i} = L(𝔄_{i}). Wir konstruieren einen endlichen Akzeptor 𝔄 = [X, Z, δ, z_{0}, M] mit L(𝔄) = L_{1}L_{2} wie folgt:

Z := Z_{1} × 𝔓(Z_{2})
z_{0} = \{ \begin{matrix}[z_{0}_{1}, ∅], falls & e ∉ L_{1} (z_{0}_{1} ∉ M_{1}) \\ [z_{0}_{1}, \{z_{0}_{2}\}], falls & e ∈ L_{1} \end{matrix}

für z_{1} ∈ Z_{1}, N ⊆ Z_{2} sei

δ([z_{1}, N], x) := [δ_{1}(z_{1}, x), \{δ_{2}(z_{2}, x)|z_{2} ∈ N\} ∪ \{ \begin{matrix}\{z_{0}_{2}\}, & falls δ_{1}(z_{1}, x) ∈ M_{1} \\ ∅, & sonst \end{matrix} \}]
M := {[z_{1}, N]|z_{1} ∈ Z_{1} ∧ N ⊆ Z_{2} ∧ N ∩ M_{2} ≠ ∅}

Durch Induktion über p beweist man:

Lemma 3.1.8

δ(z_{0}, p) = [δ_{1}(z_{0}_{1}, p), {δ_{2}(z_{0}_{2}, r)|∃u (p = ur ∧ δ_{1}(z_{0}_{1}, u) ∈ M_{1})}]

Damit erhalten wir

\begin{matrix}p ∈ L(𝔄) ↔ & δ(z_{0}, p) ∈ M \\ ↔ & [δ_{1}(z_{0}_{1}, p), \{δ_{2}(z_{0}_{2}, r)|∃u (p = ur ∧ δ_{1}(z_{0}_{1}, u) ∈ M_{1})\}] ∈ M \\ ↔ & ∃u ∃r (p = ur ∧ δ_{1}(z_{0}_{1}, u) ∈ M_{1} ∧ δ_{2}(z_{0}_{2}, r) ∈ M_{2}) \\ ↔ & ∃u ∃r (p = ur ∧ u ∈ L_{1} ∧ r ∈ L_{2}) \\ ↔ & p ∈ L_{1}L_{2} \end{matrix}

Definition 3.1.9 (Die Kleenesche Hülle ⟨L⟩ einer Sprache L) Es sei L ⊆ W (X). Die Potenzen L^{i} von L werden durch Induktion über i definiert:

L^{0} = {e}
L^{i+1} = L^{i}L
Dann ist ⟨L⟩ := ⋃_{i≥0} L^{i}

Folgerung 3.1.10

1. ⟨∅⟩ = {e}

2. ⟨⟩ hat die folgenden Hülleneigenschaften:

(a) L ⊆ ⟨L⟩ (Einbettung)

(b) Wenn L_{1} ⊆ L_{2} so ⟨L_{1}⟩ ⊆ ⟨L_{2}⟩ (Monotonie)

(c) ⟨⟨L⟩⟩ = ⟨L⟩ (Abgeschlossenheit)

3. ⟨⟩ erfüllt den Endlichkeitssatz:

Wenn p ∈ ⟨L⟩, so existiert eine endliche Teilmenge L^{∗} ⊆ L mit p ∈ ⟨L^{∗}⟩.

Bemerkung: Die Umkehrung von 3 ist wegen 2b trivial.

Beweis von 3: Wenn p ∈ ⟨L⟩ = ⋃ L^{i}, so existiert ein i ≥ 0 mit p ∈ L^{i}. Wenn i = 0 ist, dann ist p = e und L^{∗} = ∅ leistet das Verlangte, bei i = 1 ist p ∈ L^{1} = L, also leistet L^{∗} = {p} das Verlangte. Wenn i ≥ 2, p ∈ L^{i}, so gibt es Wörter r_{1}, r_{2}, …, r_{i} ∈ L mit p = r_{1}r_{2} ⋯ r_{i} ∈ L^{i}. Folglich leistet L^{∗} = {r_{1}, r_{2}, …, r_{i}} das Verlangte.

Folgerung 3.1.11 Für jede Sprache L ist ⟨L⟩ = ⟨L \ {e}⟩.

Satz 3.1.12 REG ist abgeschlossen gegenüber Hüllenbildung, d. h. wenn L ∈ REG, so ⟨L⟩ ∈ REG.

Beweis: Es sei 𝔄 = [X, Z, δ, z_{0}, M] ein endlicher Akzeptor mit L = L(𝔄).

Wir nehmen einen neuen Zustand z_{00} in Z auf

Z′ := Z ∪ {z_{00}} (z_{00} ∉ Z)

und definieren für z′ ∈ Z, x ∈ X

δ′(z′, x) = \{ \begin{matrix}δ(z′, x), falls & z′ ∈ Z \\ δ(z_{0}, x), falls & z′ = z_{00} \end{matrix}

Von dem endlichen Akzeptor 𝔄′ = [X, Z′, δ′, z_{00}, M] wird die Sprache L(𝔄′) = L \ {e} akzeptiert. In 𝔄′ ist z_{00} der Anfangszustand, in den von keinem anderen Zustand aus übergegangen werden kann.

Wir konstruieren jetzt einen Akzeptor 𝔄^{∗} mit L(𝔄^{∗}) = ⟨L(𝔄′)⟩ = ⟨L \ e⟩ = ⟨L⟩.

Z^{∗} := 𝔓(Z′)
für N ⊆ Z′, x ∈ X setzen wir:
δ^{∗}(N, x) := \{δ′(z′, x)|z′ ∈ N\} ∪ \{ \begin{matrix}\{z_{00}\}, & falls ∃z′ (z′ ∈ N ∧ δ′(z′, x) ∈ M) \\ ∅, & sonst \end{matrix}
z_{0}^{∗} := {z_{00}}
M^{∗} := {N|N ⊆ Z ∧ z_{00} ∈ N}
𝔄^{∗} := [x, Z^{∗}, δ^{∗}, z_{0}^{∗}, M^{∗}]

Offenbar gilt

δ^{∗}(z_{0}^{∗}, e) = z_{0}^{∗} = {z_{00}} ∈ M^{∗}

also e ∈ L(𝔄^{∗}).

Wenn p ∈ ⟨L(𝔄′⟩ ist, dann gibt es nichtleere Wörter r_{1}, …, r_{n} ∈ L(𝔄′) mit p = r_{1}r_{2} ⋯ r_{n}, d. h. für i = 1, …, n ist

δ′(z_{00}, r_{i}) ∈ M

Folglich ist für i = 1, …, n

z_{00} ∈ δ^{∗}({z_{00}}, r_{1} ⋯ r_{i})

also δ^{∗}(z_{0}^{∗}, p) ∈ M^{∗} und somit p ∈ L(𝔄^{∗}).

Ist umgekehrt p = x_{1}x_{2} ⋯ x_{n} ∈ L(𝔄^{∗}) und

z_{i}^{∗} := δ^{∗}(z_{0}^{∗}, x_{1} ⋯ x_{i}) (i = 1, …, n)

so ist z_{n}^{∗} = δ^{∗}(z_{0}^{∗}, p) ∈ M^{∗}, d. h. z_{00} ∈ z_{n}^{∗}. Außerdem ist natürlich z_{00} ∈ z_{0}^{∗} = {z_{00}}. Es seien j_{0} < j_{1} < j_{2} < ⋯ < j_{k} alle Zahlen j_{i} mit

z_{00} ∈ z_{j_{i}}^{∗}

es ist also

j_{0} = 0  und  j_{k} = n

Nun ist

z_{00} ∈ z_{j_{1}}^{∗} = δ^{∗}(z_{0}^{∗}, x_{1} ⋯ x_{j_{1}})  und  j_{1} > j_{0} = 0

Weil z_{00} kein Wort von δ′ ist und in den Zuständen z_{1}^{∗}, …, z_{j_{1}−1}^{∗} nicht vorkommt, ist δ′(z_{00}, x_{1} ⋯ x_{j_{1}}) ∈ M (sonst wäre z_{00} ∉ z_{j_{1}}^{∗}), d. h. x_{1} ⋯ x_{j_{1}} ∈ L(𝔄′).

Analog überlegt man sich, daß

x_{j_{i}+1} ⋯ x_{j_{i+1}} ∈ L(𝔄′) (i = 1, …, k − 1)

gilt. Folglich ist p ∈ ⟨L(𝔄′)⟩.

Damit wissen wir, daß insbesondere die Operationen Vereinigung, Produkt und Hülle die Regularität von Sprachen erhalten.

Satz 3.1.13 (von Kleene:) REG ist die kleinste Familie von Sprachen, die die leere Sprache ∅ und alle Einermengen {x} von Buchstaben als Elemente enthält und abgeschlossen ist in bezug auf Vereinigung, Produkt und Hülle.

Beweis: Wir haben zu zeigen

I. REG ist eine Familie der genannten Art, d. h. ∅ ∈ REG, für alle x ∈ X ist {x} ∈ REG und REG ist abgeschlossen gegen ∪, ·, ⟨⟩. Das folgt aus den bereits bewiesenen Sätzen und L(𝔄) = ∅ für jeden endlichen Akzeptor 𝔄 bei dem die Akzeptierungsmenge M = ∅ ist, sowie

L(𝔄_{x_{0}}) = {x_{0}}
für 𝔄_{x_{0}} = [X, {z_{0}, z_{1}, z_{2}}, δ_{x_{0}}, z_{0}, {z_{1}}]
wobei δ_{x_{0}}(z_{0}, x) = \{ \begin{matrix}z_{1}, & falls x = x_{0} \\ z_{2}, & sonst \end{matrix}
und δ_{x_{0}}(z_{1}, x) = δ_{x_{0}}(z_{2}, x) = z_{2} für alle x ∈ X

II. Wenn L ∈ REG, so kann L aus der leeren Sprache und den Einermengen von Buchstaben mit Hilfe der Operationen Vereinigung, Produkt und Hülle aufgebaut werden.

Es sei 𝔄 = [X, Z, δ, z_{1}, M] ein endlicher Akzeptor mit L(𝔄) = L. Die Zustandsmenge Z sei numeriert als Z = {z_{1}, …, z_{n}} wobei der Anfangszustand die Nummer 1 erhält.

Für i, j = 1, …, n betrachten wir die Sprache

L_{i,j} = {p|p ∈ W (X) ∧ δ(z_{i}, p) = z_{j}}

Offenbar ist

L = ⋃_{z_{j}∈M} L_{1j}

d. h. L ist Vereinigung von Sprachen der Form L_{1j}, es genügt also zu zeigen, daß die L_{ij} mittels Produkt, Vereinigung und Hülle aus der leeren Menge und den Einermengen von Buchstaben aufgebaut werden können.

Für z ∈ Z sei num(z) die Nummer von z, d. h. es gilt stets z_{num(z)} = z

Für 1 ≤ i, j ≤ n, 0 ≤ k ≤ n betrachten wir

L_{i,j}^{k} = {p|p ≠ e ∧ δ(z_{i}, p) = z_{j} ∧ ∀r (e ≠ r ⊏ p → num(δ(z_{i}, r)) ≤ k)}

d. i. die Menge aller nichtleeren Wörter p, die den Akzeptor 𝔄 aus dem Zustand z_{i} in den Zustand z_{j} versetzen, wobei die zwischendurch durchlaufenen Zustände Nummern haben, die k nicht übersteigen.

Da es keinen Zustand mit der Nummer ≤ 0 gibt, ist also L_{i,j}^{0} eine endliche Menge von Buchstaben, d. h. eine Vereinigung von Einermengen von Buchstaben. Da alle Zustände Nummern ≤ n haben, ist andererseits

L_{i,j} = L_{i,j}^{n} ∪ \{ \begin{matrix}\{e\}, & falls i = j \\ ∅, & sonst \end{matrix}

Wegen {e} = ⟨∅⟩ genügt es also zu zeigen, daß für alle i, j, k die Sprache L_{i,j}^{k} aus der leeren Menge und den Einermengen von Buchstaben mittels Vereinigung, Produkt und Hülle konstruiert werden kann. Wir beweisen das durch Induktion über k, dabei ist der Anfangsschritt k = 0, wie oben gezeigt, trivial. Im Induktionsschritt k → k + 1 zeigt man

L_{i,j}^{k+1} = L_{i,j}^{k} ∪ L_{i,k+1}^{k} · ⟨L_{k+1,k+1}^{k}⟩ · L_{k+1,j}^{k}

3.2 Grammatiken

Wir haben bisher Akzeptoren für Sprachen betrachtet, also Mechanismen zur Beantwortung der Frage, ob eine vorgelegte Symbolkette (ein Wort) zu einer gegebenen Sprache gehört. Motiviert zur Untersuchung von Akzeptoren hat uns die Feststellung, daß jeder Compiler am Beginn seiner Arbeit einen Test auf syntaktische Richtigkeit durchführt.

Man kann Akzeptoren als Objektivierung bzw. Formalisierung des Hörers einer Sprache ansehen. Damit stellt sich automatisch die Frage nach einer Objektivierung des Sprechers, d. h. die Aufgabe zu beschreiben, wie ein Sprecher dazu in der Lage ist, nur syntaktisch richtige Sätze zu produzieren. Auf Programmiersprachen angewendet ensteht die Frage nach einem formalen Erzeugungsverfahren, mit dessen Hilfe alle Sätze (und nur diese) einer Sprache gebildet werden können.

Aus der Linguistik entlehnen wir dazu den Begriff der Grammatik als eines Systems von Regeln, die die Erzeugung von Sätzen steuern und die sich auf syntaktische Kategorien wie ⟨Satz⟩, ⟨Subjekt⟩, ⟨Objekt⟩, … stützen.

In der Formalisierung erscheinen die grammatischen Regeln als Ersetzungsregeln und die syntaktischen Kategorien als Hilfssymbole.

Es sei Y ein beliebiges endliches Alphabet, p, q ∈ W (Y). Das Paar [p, q] wird dann als Ersetzungsregel bezeichnet und auch p → q geschrieben. Eine Anwendung dieser Regel auf ein Wort w ∈ W (Y) ist möglich, wenn p als Teilwort in w vorkommt und die Anwendung selbst besteht darin, daß ein Vorkommen von p in w durch q ersetzt wird.

Definition 3.2.1 Es sei R ⊆ W (Y) × W (Y) eine Regelmenge, p, q ∈ W (Y). Aus p ist q mittels R in einem Schritt ableitbar (p ⟼_{R}^{1} q), wenn es Wörter u, v, r, s so gibt, daß

p = rus, q = rvs und [u, v] ∈ R

ist.

Durch Induktion definieren wir die Relation ⟼_{R}^{∗} als reflexiv transitive Hülle von

⟼_{R}^{1} :

Anfangsschritt: Wenn p = q, so p ⟼_{R}^{∗} q

Induktinsschritt: Wenn p ⟼_{R}^{∗} q und q ⟼_{R}^{1} r, so p ⟼_{R}^{∗} r.

Beispiel: Es sei R = {a→ ba, baa→ c}. Dann ist aa ⟼_{R}^{1} baa ⟼_{R}^{1} baba ⟼_{R}^{1} bbaba

also aa ⟼^{∗} bbaba und auch aa ⟼^{∗} c.

Definition 3.2.2 (N. Chomsky) 𝔊 = [X, H, R, s] ist eine Grammatik, wenn

1. X eine endliche nichtleere Menge (das Alphabet der erzeugten Sprache)

2. H eine endliche Menge von Hilfssymbolen (syntaktische Kategorien), wobei X ∩ H = ∅ 3. s ∈ H (das Satzsymbol, Startsymbol)

4. R eine endliche Menge von Ersetzungsregeln u → v mit u ∈ W (X∪H)\W (X), v ∈ W (X ∪ H)

ist.

Daß das Erzeugen bzw. Ableiten in 𝔊 sich auf die syntaktischen Kategorien, d. h. die Hilfssymbole stützt, kommt darin zum Ausdruck, daß die linke Seite u jeder Regel u → v wenigstens ein Hilfssymbol enthält: u ∉ W (X), insbesondere ist keine linke Seite leer.

Die von 𝔊 erzeugte Sprache L über X ist die Menge aller aus s ableitbaren Wörter, die kein Hilfssymbol enthalten:

L(𝔊) = {p|p ∈ W (X) ∧ s ⟼^{∗} p}

Beispiel: 𝔊_{1} = [{a, b}, {s, h}, {s → ahb, s → ab, h → ahb, h → e}, s] Offenbar ist

s ⟼_{R}^{1} ahb ⟼_{R}^{1} ab, also ab ∈ L(𝔊_{1})

aber auch

s ⟼^{1} ab

d. h. das Wort ab kann auf zwei Weisen erzeugt werden. Man überlegt sich

L(𝔊_{1}) = {a^{i}b^{i}|i ≥ 1}

Man unterscheidet Grammatiken nach ihrem Typ, der durch Anforderungen an die Regelmenge spezifiziert wird:

Definition 3.2.3 Eine Grammatik 𝔊 hat den Typ i (i = 0, 1, 2, 3), wenn ihre Regelmenge R die Forderung (i) erfüllt:

(0) R = R (jede Grammatik hat den Typ 0)

(1) Wenn u → v ∈ R, so gibt es ein Hilfssymbol h ∈ H und Wörter p, q, r mit

u = phq, v = prq und r ≠ e
oder u = h ∈ H, v = e und h kommt in keiner Regel

auf der rechten Seite vor

(2) Wenn u → v ∈ R, so u = h ∈ H

(3) Wenn u → v ∈ R, so ist u = h ∈ H ein Hilfssymbol und v ∈ W (X) oder v ∈ W (X) · H

Bei Regeln u → v im Typ–1–Grammatiken besteht also die Ersetzung von u durch v im Kern in der Ersetzung eines Hilfssymbols h durch ein nichtleeres Wort r, diese Ersetzung darf aber nicht überall wo h steht vorgenommen werden, sondern nur im Kontext p, r.

Typ–1–Grammatiken werden daher auch als kontext–sensitive Grammatiken bezeichnet, im Gegensatz zu den Typ–2–Grammatiken, die als kontextfrei (alle linken Seiten bestehen aus einem Hilfssymbol ohne Kontext) bezeichnet werden.

Die oben angegebene Grammatik 𝔊_{1} hat den Typ 0, nicht den Typ 1 (h → e ∈ R und h kommt auf der rechten Seite der Regel s → ahb vor), den Typ 2 und nicht den Typ 3 (zum Beispiel enthält die rechte Seite der Regel s → ahb zwar nur ein Hilfssymbol, aber es steht nicht am Ende des Wortes: ahb ∉ W ({a, b}) · H).

Wenn man von dem Typ einer Grammatik (oder einer Sprache, s. unten) spricht, so meint man stets das größte i derart, daß diese Grammatik den Typ i hat.

Offenbar gilt:

(1) Jede Typ–3–Grammatik hat auch den Typ 2

(2) Jede Typ–2–Grammatik hat auch den Typ 0

Eine Sprache L ⊆ W (X) hat den Typ i, wenn sie eine Typ–i–Grammatik besitzt. Es sei für i = 0, 1, 2, 3

𝔏_{i} = {L(𝔊_{i})|𝔊 Grammatik vom Typ i}

Offenbar gilt:

(1) 𝔏_{3} ⊆ 𝔏_{2} ⊆ 𝔏_{0}

(2) 𝔏_{1} ⊆ 𝔏_{0}

Wir wollen zuerst zeigen, daß die Typ–3–Grammatiken den zu endlichen Akzeptoren adäquaten Erzeugungsmechanismus beschreiben, d. h. daß 𝔏_{3} = REG ist.

Satz 3.2.4 REG ⊆ 𝔏_{3}, d. h. zu jedem endlichen Akzeptor 𝔄 = [X, Z, δ, z_{0}, M] existiert ein Grammatik 𝔊 vom Typ 3 mit

L(𝔄) = L(𝔊)

Beweis: Für den gegebenen Akzeptor 𝔄 setzen wir voraus, daß X ∩ Z = ∅ ist. Wir betrachten 𝔊 = [X, Z, R, z_{0}] wobei

R = {z → xδ(z, x)|z ∈ Z, x ∈ X} ∪ {z → e|z ∈ M}

Man überlegt sich, daß für alle p ∈ W (X) gilt

z ⟼_{R}^{∗} pz′ gdw. z′ = δ(z, p)

so daß für p ∈ W (X) gilt

p ∈ L(𝔊) ↔ z_{0} ⟼_{R}^{∗} p
↔ es gibt ein z ∈ M mit z_{0} ⟼_{R}^{∗} pz ⟼_{R}^{1} p
↔ δ(z_{0}, p) ∈ M
↔ p ∈ L(𝔄)

Zu jedem endlichen Akzeptor 𝔄 gehört also eine Typ–3–Grammatik, die die von 𝔄 akzeptierte Sprache generiert. Diese Grammatik hat eine Reihe (zusätzlicher) Eigenschaften, die Typ–3–Grammatiken im allgemeinen nicht haben. Wir müssen daher, um zu einer Typ–3–Grammatik einen Akzeptor zu konstruieren, die Grammatik zunächst umformen, in eine Normalform bringen.

Definition 3.2.5

1. Grammatiken 𝔊, 𝔊′ heißen äquivalent (𝔊 ∼ 𝔊′), wenn L(𝔊) = L(𝔊′) ist

2. Eine Typ–3–Grammatik 𝔊 hat Normalform, wenn alle Regeln eine der Formen h → xh′ oder h → e haben, wobei h, h′ ∈ H, x ∈ X ist.

Satz 3.2.6 Zu jeder Typ–3–Grammatik 𝔊 = [X, H, R, s] existiert eine äquivalente Typ–3– Grammatik in Normalform.

Beweis: Bei der Konstruktion der Normalform gehen wir schrittweise vor, wir ersetzen die Regeln, die in der Normalform nicht zugelassen sind, durch Mengen neuer Regeln. Dabei erweitern wir auch die Menge der Hilfsymbole.

(1) Regeln der Form h → p, p ∈ W (X), p ≠ e Ist p = x_{1}x_{2} … x_{n}, n ≥ 1 so führen wir neue Hilfssymbole

h_{x_{2}···x_{n}}, h_{x_{3}···x_{n}}, …, h_{x_{n}}, h_{e}

ein und ersetzen die Regel h → p durch

h → x_{1}h_{x_{2}···x_{n}}, h_{x_{2}···x_{n}} → x_{2}h_{x_{3}···x_{n}}, …, h_{x_{n}} → x_{n}h_{e}, h_{e} → e

Weil die Hilfssymbole h_{r} neu sind, können diese nach Anwenden der Regel h → x_{1}h_{x_{2}···x_{n}} nur durch Anwendung der weiteren Regeln h_{xr} → xh_{r} bzw. h_{e} → e beseitigt werden.

(2) Regeln der Form h → ph′ mit l(p) ≥ 2 werden analog zu (1) behandelt.

Nach den Schritten (1) und (2) enthält unsere Grammatik außer in der Normalform zugelassenen Regeln eventuell noch Regeln der Form h → h′. Diese werden mit der folgenden Konstruktion en bloc beseitigt:

Für h ∈ H sei U(h) = {h′|h ⟼_{R}^{∗} h′}

Eine Ableitung in 𝔊, bei der Regeln h → h′ benutzt werden, sieht etwa so aus

s ⟼_{R}^{∗} ph ⟼_{R}^{∗} ph′ ⟼^{1} pxh′′

wobei zuletzt die Regel h′ → xh′′ benutzt wird. Nehmen wir jetzt die Regel h → xh′′ auf, so können wir die Ableitung h ⟼_{R}^{∗} h′ einsparen:

s ⟼_{R}^{∗} ph ⟼_{R′}^{1} pxh′′

Dementsprechend setzen wir

R′ := (R \ {h → h′|h, h′ ∈ H})∪
{h → xh′′|∃h′ (h′ ∈ U(h) ∧ h′ → xh′′ ∈ R}∪
{h → e|∃h′ (h′ ∈ U(h) ∧ h′ → e ∈ R}

Die so erhaltene Grammatik 𝔊′ ist eine zu 𝔊 äquivalente Normalform.

Beispiel: 𝔊 = [{a, b}, {s, h}, R, s] mit R = {s → h, h → abh, h → e} Nach Schritt (2) ist

R = {s → h, h → ah^{∗}, h^{∗} → bh, h → e}

Es ist U(s) = {h}, also

R′ = {h → ah^{∗}, h^{∗} → bh, h → e, s → ah^{∗}, s → e}

Satz 3.2.7 𝔏_{3} ⊆ REG, d. h. zu jeder Typ–3–Grammatik 𝔊 existiert ein endlicher Akzeptor 𝔄 mit L(𝔄) = L(𝔊).

Beweis: Wir können annehmen, daß 𝔊 = [X, H, R, s] in Normalform ist. Wir konstruieren 𝔄 = [X, Z, δ, z_{0}, M] wie folgt:

Z := 𝔓(H)
z_{0} := {s}
δ(N, x) = {h′|∃h (h ∈ N ∧ h → xh′ ∈ R}
M := {N|N ⊆ H ∧ ∃h (h ∈ N ∧ h → e ∈ R}

Man zeigt leicht, daß

L(𝔄) = L(𝔊)

ist.

Für die zuletzt betrachtete Grammatik ergibt sich der folgende Akzeptor:

[figure: {h}; {h^{∗}}; {s}; ∅; ⇓; b; a; a; b; b; a; a; b]

Wir geben noch einen Satz an, der nützlich sein kann, wenn man beweisen möchte, daß eine Sprache keine Typ–3–Grammatik besitzt:

Satz 3.2.8 (qru–Theorem) Zu jeder regulären Sprache L existiert eine Zahl k > 0 derart, daß für alle Wörter p ∈ L mit l(p) > k eine Zerlegung p = qru mit r ≠ e so existiert, daß für alle i ∈ N gilt:

qr^{i}u ∈ L

(k ist die Zustandszahl eines L akzeptierenden Akzeptors oder die Zahl der Hilfssymbole einer L erzeugenden Grammatik in Normalform)

Als Anwendungsbeispiel zeigen wir

L = {a^{i}b^{i}|i ≥ 1} ∉ 𝔏_{3}

Wir nehmen das Gegenteil an: L ∈ 𝔏_{3}, dann existiert nach Satz 3.2.8 eine Zahl k mit den angegebenen Eigenschaften. Wir betrachten p = a^{k}b^{k} ∈ L mit l(p) = 2k > k. Das Wort p kann also in p = qru mit r ≠ e so zerlegt werden, daß qr^{i}u ∈ L ist. Wenn r ∈ W ({a}) ist, (nur aus a’s besteht), dann enthält qr^{2}u mehr a’s als b’s, ist demnach nicht in L, ebenso scheidet der Fall aus, daß r ∈ W ({b}) ist. Bei r = a^{n}b^{m} mit n ≥ 1, m ≥ 1 ist aber qr^{2}u = a^{k}b^{m}a^{n}b^{k} ∉ L, Widerspruch. Andererseits ist L ∈ 𝔏_{2}, also haben wir

𝔏_{3} ⊂ 𝔏_{2}

Wenn auch Teilsprachen von Programmiersprachen (z. B. die Menge der Bezeichner) regulär sind, so wird die Syntax von Programmiersprachen doch im allgemeinen durch eine kontextfreie Grammatik (in BNF) gegeben und durch zusätzliche Kontextbedingungen wieder eingeschränkt. Die Vorteile der kontextfreien Grammatiken bestehen u. a. in

• der guten Handhabbarkeit der Regeln

• relativ einfache Analyse von Wörtern auf Ableitbarkeit (durch Kellerautomaten, siehe 3.3)

• Beschreibung von (Links–)Ableitungen durch Ableitungsbäume (die im Spezialfall der Typ–3–Grammatiken zu einem ”Ast“ entarten)

Wir wollen nun einige wichtige Eigenschaften von kontextfreien Sprachen diskutieren. Zunächst beschäftigen wir uns mit der Beziehung zwischen 𝔏_{2} und 𝔏_{1}.

Satz 3.2.9 𝔏_{2} ⊆ 𝔏_{1}, d. h. zu jeder Typ–2–Grammatik 𝔊 kann eine äquivalente Typ–2–Grammatik 𝔊′ konstruiert werden, die auch den Typ 1 hat.

Beweis: Wenn in 𝔊 = [X, H, R, s] keine Regeln der Form h → e vorkommen, dann hat 𝔊 schon den Typ 1 und wir sind fertig.

Andernfalls betrachten wir die Menge

H^{∗} = {h|h ⟼_{R}^{∗} e}

Diese Menge enthält nicht nur Hilfssymbole h derart, daß h → e ∈ R ist, es kann z. B. auch sein

h ⟼^{1} h_{1}h_{2} ⟼^{1} h_{2} ⟼^{1} e

wenn etwa h → h_{1}h_{2}, h_{1} → e, h_{2} → e Regeln sind. Wir gestalten die Regelmenge jetzt so um, daß wir auf die Anwendung von Regeln der Form h → e bei der Ableitung eines nichtleeren Wortes verzichten können.

R′ = (R \ {h → e|h ∈ H})∪
{h → q|q ≠ e ∧ ∃p (h → p ∈ R ∧

q entsteht aus p durch Streichen einiger h^{∗} ∈ H^{∗})} Beispiel R = {s → h_{1}h_{2}, h_{1} → ah_{1}, h_{2} → bh_{2}, h_{1} → e, h_{2} → e} Dann ist H^{∗} = H und

R′ = {s → h_{1}h_{2}, s → h_{1}, s → h_{2},
h_{1} → ah_{1}, h_{1} → a,
h_{2} → bh_{2}, h_{2} → b}

Für die entstandene Grammatik 𝔊′ gilt L(𝔊′) = L(𝔊) \ {e}. Wenn e ∉ L(𝔊) (d. h. s ∉ H^{∗}) ist, also L(𝔊′) = L(𝔊), dann sind wir fertig, andernfalls führen wir ein neues Satzsymbol s^{∗} und die Regeln s^{∗} → e, s^{∗} → s in die Grammatik ein.

Die erhaltene Grammatik 𝔊^{∗} ist vom Typ 1 mit L(𝔊^{∗}) = L(𝔊).

Zur Vervollständigung der Konstruktion müssen wir noch H^{∗} berechnen. Dazu betrachten wir

H_{1} := {h|h → e ∈ R}
H_{i+1} := H_{i} ∪ {h|∃q (q ∈ W (H_{i}) ∧ h → q ∈ R}

In unserem Beispiel ist

H_{1} = {h_{1}, h_{2}}, H_{2} = {h_{1}, h_{2}, s} = H_{3} = …

Für die Folge der H_{i} gilt

(1) H_{1} ⊆ H_{2} ⊆ ⋯ ⊆ H_{i} ⊆ ⋯ ⊆ H

(2) Wenn H_{i} = H_{i+1}, so H_{i+1} = H_{i+2}

(3) h ∈ H^{∗} gdw. es ein i mit h ∈ H_{i} gibt

Weil H_{i} ⊆ H und H endlich ist, so gibt es ein i ≤ card(H) mit H_{i} = H_{i+1} (= H^{∗}). Also kann H^{∗} berechnet werden.

Aus dem Beweis folgt:

Eine Sprache L ist kontextfrei genau dann, wenn die Sprache L \ {e} kontextfrei ist.

Wir haben gesehen, daß die Sprachfamilie 𝔏_{3} abgeschlossen ist gegenüber den Operationen Vereinigung, Durchschnitt, Komplement, Produkt und Hülle. Auch 𝔏_{2} besitzt Abgeschlossenheitseigenschaften, aber nicht alle diese:

Satz 3.2.10 𝔏_{2} ist abgeschlossen gegenüber Vereinigung, Produkt und Hülle^{1}.

Zum Beweis geben wir Konstruktionen an, die aus zwei Typ–2–Grammatiken 𝔊_{1}, 𝔊_{2} kontextfreie Grammatiken 𝔊_{3}, 𝔊_{4}, 𝔊_{5} konstruieren mit

\begin{matrix}L(𝔊_{3}) = & L(𝔊_{1}) ∪ L(𝔊_{2}) \\ L(𝔊_{4}) = & L(𝔊_{4}) · L(𝔊_{2}) \\ L(𝔊_{5}) = & ⟨L(𝔊_{1})⟩ \end{matrix}

Es seien 𝔊_{i} = [X, H_{i}, R_{i}, s_{i}] (i = 1, 2) kontextfreie Grammatiken, wir können annehmen, daß H_{1} ∩ H_{2} = ∅ ist. Dann setzen wir

𝔊_{3} = [X, H_{1} ∪ H_{2} ∪ {s^{∗}}, R_{1} ∪ R_{2} ∪ {s^{∗} → s_{1}, s^{∗} → s_{2}}, s^{∗}]

1Auch 𝔏_{0} und 𝔏_{1} besitzen diese Abgeschlossenheitseigenschaften.

wobei s^{∗} ∉ H_{1} ∪ H_{2} ein neues Hilfssymbol ist;

𝔊_{4} = [X, H_{1} ∪ H_{2} ∪ {s^{∗}}, R_{1} ∪ R_{2} ∪ {s^{∗} → s_{1}s_{2}}, s^{∗}]

und

𝔊_{5} = [X, H_{1}, R_{1} ∪ {s^{∗} → s_{1}s^{∗}, s^{∗} → e}, s^{∗}]

Man überlegt sich leicht, daß 𝔊_{3}, 𝔊_{4}, 𝔊_{5} die gewünschten Eigenschaften haben.

Um die Struktur von kontextfreien Sprachen genauer studieren zu können, geben wir auch für kontextfreie Grammatiken eine Normalform an:

Definition 3.2.11 (Chomsky–Normalform) Eine Grammatik ist in Chomsky–Normalform, wenn alle Regeln eine der Formen

h → h_{1}h_{2} oder h → x

mit h, h_{1}, h_{2} ∈ H, x ∈ X haben.

In einer Chomsky–Normalform kann das leere Wort nicht abgeleitet werden, denn es existiert keine Regel mit leerer rechter Seite. Wir können also zu einer beliebigen Typ–2–Grammatik 𝔊 höchstens eine Chomsky–Normalform finden, die L(𝔊) \ {e} erzeugt.

Satz 3.2.12 Zu jeder Typ–2–Grammatik 𝔊 = [X, H, R, s] existiert eine Chomsky–Normalform 𝔊^{∗} mit

L(𝔊^{∗}) = L(𝔊) \ {e}

Beweis: Wie oben konstruieren wir aus 𝔊 zunächst die Grammatik 𝔊′ mit L(𝔊′) = L(𝔊) \ {e}, wobei 𝔊′ keine Regeln der Form h → e enthält.

Anschließend nehmen wir für jedes x ∈ X ein neues Hilfssymbol h_{x} und die Regel h_{x} → x in die Regelmenge auf. Gleichzeitig ersetzen wir in den alten Regeln jedes vorkommende x durch h_{x}.

Damit haben alle Regeln die Formen

h → x oder h → h_{1} ⋯ h_{n}

Die Regeln der Form h → h_{1} beseitigen wir wie oben in Typ–3–Grammatiken, die Regeln h → h_{1} ⋯ h_{n} mit n ≥ 3 ersetzen wir unter Einführung neuer Hilfssymbole durch

h → h_{1}h_{h_{2}···h_{n}}
h_{h_{2}···h_{n}} → h_{2}h_{h_{3}···h_{n}}
⋮
h_{h_{n−1}h_{n}} → h_{n−1}h_{n}

Wir formen als Beispiel die Grammatik

𝔊_{1} = [{a, b}, {s, h}, {s → ahb, s → ab, h → ahb, h → e}, s]

in eine Chomsky–Normalform um.

Es ist H^{∗} = {h}, also

R′ = {s → ahb, s → ab, h → ahb, h → ab}

mit L(𝔊′) = L(𝔊_{1}) \ {e} = L(𝔊_{1}).

Durch Separieren erhalten wir

R′′ = {h_{a} → a, h_{b} → b, s → h_{a}hh_{b}, s → h_{a}h_{b}, h → h_{a}hh_{b}, h → h_{a}h_{b}}

Regeln der Form h → h′ kommen nicht vor. Im weiteren ergibt sich

R^{∗} = {s → h_{a}h_{b}, s → h_{a}h^{∗}, h^{∗} → hh_{b},
h → h_{a}h_{b}, h → h_{a}h^{∗∗}, h^{∗∗} → hh_{b},
h_{a} → a, h_{b} → b}

Jede Ableitung s ⟼^{∗} p in einer Chomsky–Normalform kann sehr anschaulich durch einen sogenannten Ableitungsbaum dargestellt werden, dessen Knoten mit Hilfssymbolen und Buchstaben aus X beschriftet sind. Die Wurzel des Baumes ist mit dem Satzsymbol s beschriftet, ein Knoten der mit h ∈ H beschriftet ist, hat einen oder zwei Nachfolger, jenachdem ob eine Regel h → x oder eine Regel h → h_{1}h_{2} in der Ableitung auf h angewendet worden ist. Wir verzichten auf eine formale Definition und geben stattdessen ein

Beispiel: Wir betrachten die Ableitung

\begin{aligned}s & ⟼^{1} h_{a}h^{∗} ⟼^{1} ah^{∗} ⟼^{1} ahh_{b} ⟼^{1} ah_{a}h^{∗∗}h_{b} ⟼^{1} aah^{∗∗}h_{b} ⟼^{1} aahh_{b}h_{b} \\ & ⟼^{1} aah_{a}h_{b}h_{b}h_{b} ⟼^{1} aaah_{b}h_{b}h_{b} ⟼^{1} aaabh_{b}h_{b} ⟼^{1} aaabbh_{b} ⟼^{1} aaabbb \end{aligned}

Dies ist eine sogenannte Linksableitung, weil beim Ableiten stets das am weitesten links stehende Hilfssymbol ersetzt wurde. Der zugehörige Ableitungsbaum sieht so aus:

[figure: a; b; h_{a}; h_{b}; b; a; h; h_{b}; h_{a}; h^{∗∗}; b; a; h; h_{b}; h_{a}; h^{∗}; s]

Für die Länge l des längsten Weges in einem solchen binären Baum, der bei der Wurzel beginnt, gilt offenbar

2^{l−1} ≥ n

wobei n die Länge des abgeleiteten Wortes ist. Hier ist l = 6 = n und 2^{5} = 32 ≥ 6.

Wir nutzen diesen Zusammenhang beim Beweis des Lemmas von Bar–Hillel, das auch qruvw–Theorem genannt wird:

Lemma 3.2.13 Zu jeder kontextfreien Sprache L existiert ein Zahl k > 0, so daß zu jedem p ∈ L mit l(p) > k eine Zerlegung p = qruvw mit rv ≠ e so existiert, daß für alle i ∈ N gilt:

qr^{i}uv^{i}w ∈ L

Ohne Beschränkung der Allgemeinheit können wir annehmen, daß L ∈ 𝔏_{2} durch eine Grammatik in Chomsky–Normalform gegeben ist. Dann behaupten wir, daß k = 2^{card(H)} das Verlangte leistet.

Sei also p ∈ L(𝔊) = L mit l(p) > k = 2^{card(H)}, für eine beliebige Ableitung s ⟼^{∗} p von p in 𝔊 betrachten wir einen längsten Weg im Ableitungsbaum von der Wurzel zu einem Blatt. Für dessen Länge l gilt

2^{l−1} ≥ l(p) > k = 2^{card(H)}

also l − 1 ≥ card(H).

Von den l + 1 Knoten auf diesem Weg sind l Knoten mit Hilfssymbolen beschriftet, das sind mehr als es verschiedene Hilfssymbole gibt. Folglich gibt es zwei Knoten auf diesem Weg, die mit dem gleichen Hilfssymbol h_{1} beschriftet sind.

In unserem Beispiel sind zwei Knoten mit h beschriftet.

Daraus ergibt sich, daß die Ableitung s ⟼^{∗} p wie folgt umgeschrieben werden kann:

s ⟼^{∗} qh_{1}w ⟼^{∗} qrh_{1}vw ⟼^{∗} qruvw = p

wobei gilt:

h_{1} ⟼^{∗} rh_{1}v , h_{1} ⟼^{∗} u , rv ≠ e

In unserem Beispiel ist

\begin{matrix}s ⟼^{∗} ahb ⟼^{∗} aahbb ⟼^{∗} aaabbb \\ h ⟼^{∗} ahb , h ⟼^{∗} ab , ab ≠ e \end{matrix}

Es ist nun leicht zu sehen, daß für alle i ∈ N

\begin{matrix}s ⟼^{∗} qh_{1}w ⟼^{∗} quw (i = 0) \\ s ⟼^{∗} qh_{1}w ⟼^{∗} qr^{i}h_{1}v^{i}w ⟼^{∗} qr^{i}uv^{i}w \end{matrix}

Das qruvw–Theorem kann angewendet werden, um zu zeigen, daß die Sprache

L = {a^{n}b^{n}a^{n}|n ≥ 1}

nicht kontextfrei ist. Dazu nehmen wir an, daß L ∈ 𝔏_{2} ist, dann gibt es die bewußte Zahl k und wir betrachten das Wort p = a^{k}b^{k}a^{k}. Man führt nun die möglichen Fälle der Zerlegung von p in qruvw mit rv ≠ e zum Widerspruch dazu, daß qr^{2}uv^{2}w in L ist.

Die Sprache L ist aber der Durchschnitt zweier kontextfreier Sprachen:

\begin{aligned}L_{1} & = & \{a^{n}b^{n}a^{m}|n, m ≥ 1\} \\ L_{2} & = & \{a^{n}b^{m}a^{m}|n, m ≥ 1\} \\ L & = & L_{1} ∩ L_{2} \end{aligned}

Folglich ist 𝔏_{2} weder abgeschlossen gegen Durchschnitt noch gegen Komplementbildung.

Mann kann zeigen, daß die Sprache L aus 𝔏_{1} ist. Daraus folgt

𝔏_{3} ⊂ 𝔏_{2} ⊂ 𝔏_{1}

3.3 Kellerautomaten

Zu den Typ–2–Grammatiken als Generatoren von Sprachen, d. h. als Formalisierung des Sprechers, führen wir nun einen zugehörigen Akzeptorbegriff (als Formalisierung des Hörers) ein. Wir wissen bereits, daß endliche Akzeptoren nicht ausreichen, um kontextfreie Sprachen zu akzeptieren, daß aber unendliche Akzeptoren beliebige Sprachen akzeptieren können. Wir werden daher endliche Akzeptoren betrachten, die mit einem potentiell unendlichen zusätzlichen Speicher ausgerßtet sind, der eine besondere Zugriffsstruktur hat: Nur das jeweils zuletzt eingespeicherte Zeichen ist zugänglich. Ein solcher Speicher wird auch Keller (stack) genannt.

Ein Kellerautomat ist ein nicht–deterministischer Automat, d. h. ein System, bei dem es in einer gegeben Situation i. a. mehrere Möglichkeiten zur Fortsetzung der Arbeit gibt. Zugleich kann der Kellerautomat sich in jeder Situation entscheiden, ob er ein Zeichen von der Eingabe lesen will oder ob er nur mit dem Inhalt des Kellerspeichers arbeiten will. Das von der Eingabe gelesene Wort gilt als akzeptiert, wenn bei seiner Abarbeitung eine Situation erreicht werden kann, wo der Keller leer ist.

Definition 3.3.1 𝔎 = [X, K, Z, k_{0}, z_{0}, f] ist ein Kellerautomat, wenn

(1) X,K und Z nichtleere Mengen (der Eingabezeichen, Kellerzeichen bzw. Zustände) sind

(2) k_{0} ∈ K (das Anfangskellerzeichen) ist

(3) z_{0} ∈ Z (der Anfangszustand) ist

(4) f : Z ×K ×(X ∪{e}) → 𝔓fin(Z ×W (K)) eine Abbildung ist, die jedem Tripel [z, k, ξ] mit ξ ∈ X ∪ {e} eine endliche Teilmenge von Z × W (X) zuordnet.

Der Kellerautomat 𝔎 arbeitet wie folgt: Im ersten Fall befindet er sich im Zustand z_{0} und in seinem Keller befindet sich genau das Zeichen k_{0} ∈ K.

Es sei 𝔎 im Zustand z und k sei das oberste Kellerzeichen (zuletzt eingespeichert). Wenn der Keller leer ist, also kein oberstes Kellerzeichen existiert, dann kann 𝔎 nicht weiterarbeiten. Wenn f(z, k, e) ≠ ∅ ist, dann kann 𝔎 darauf verzichten, ein Zeichen von der Eingabe zu lesen (vielleicht liegt dort auch kein Zeichen mehr an) und sein Arbeit fortsetzen, indem ein Paar [z′, w] ∈ f(z, k, e) gewählt wird. Sodann wird im Keller das letzte Zeichen, nämlich k, gestrichen und das Wort w wird an das im Keller stehende Wort angehängt (wenn w ≠ e ist, ist der letzte Buchstabe von w jetzt das oberste Kellerzeichen) und der Zustand z′ angenommen.

Es sei x ∈ X das an der Eingabe anliegende Zeichen. Wenn f(z, k, x) ≠ ∅ ist, dann kann 𝔎 dieses Zeichen einlesen und ein Paar [z′, w] ∈ f(z, k, x) zur Fortsetzung seiner Arbeit auswählen. Sodann wird verfahren wie oben.

Eine Situation eines Kellerautomaten ist also bestimmt durch ein Tripel [p, z, r], wobei p das an der Eingabe noch anliegende Wort, z der aktuelle Zustand und r das Wort im Keller ist.

Beim Prüfen, ob das Wort p akzeptiert werden kann, liegt also die Anfangssituation [p, z_{0}, k_{0}] vor.

Der Kellerautomat 𝔎 kann von der Situation [p, z, r] in einem Schritt die Situation [p′, z′, r′] erreichen ([p, z, r] ⟼_{𝔎}^{1} [p′, z′, r′], wenn gilt:

Es gibt ein k, r_{0} mit r = r_{0}k und einer der beiden Fälle:

I. p = p′ und es gibt ein q mit r′ = r_{0}q, [z′, q] ∈ f(z, k, e)

II. es gibt ein q und ein x ∈ X mit p = xp′, r′ = r_{0}q, [z′, q] ∈ f(z, k, x)

tritt ein.

Wie üblich bezeichnen wir die reflexiv transitive Hülle der Relation ⟼_{𝔎}^{1} mit ⟼_{𝔎}^{∗} . Wir definieren

L(𝔎) = {p|p ∈ W (X) ∧ ∃z (z ∈ Z ∧ [p, z_{0}, k_{0}] ⟼_{𝔎}^{∗} [e, z, e])}

Ein Wort p gilt also als akzeptiert, wenn es eine Möglichkeit für 𝔎 gibt aus der Anfangssituation [p, z_{0}, k_{0}] in eine Situation der Form [e, z, e] (wo das Wort p eingelesen und der Keller leer ist) überzugehen.

Satz 3.3.2 Zu jeder kontextfreien Sprache L existiert ein Kellerautomat 𝔎 mit L(𝔎) = L.

Beweis: Es sei 𝔊 = [X, H, R, s] eine beliebige Typ–2–Grammatik. Wir setzen K := X ∪ H und betrachten den Kellerautomaten 𝔎 = [X, K, {z}, s, z, f] mit genau einem Zustand und dem Satzsymbol von 𝔊 als Anfangskellerzeichen, wobei

f(z, k, e) := {[z, q^{←}] | k → q ∈ R}
f(z, k, x) := \{ \begin{matrix}\{[z, e]\} , & falls k = x \\ ∅ , & sonst \end{matrix}

Dabei ist q^{←}, die Inversion von q, induktiv definiert durch

\begin{matrix}e^{←} = & e \\ qx^{←} = & x q^{←} \end{matrix}

Es gilt also uv^{←} = v^{←} u^{←}.

Wir zeigen zuerst L(𝔎) ⊆ L(𝔊).

Wenn p ∈ L(𝔎) ist, so existieren

ξ_{0}, ξ_{1}, …, ξ_{n} ∈ X ∪ {e} , r_{1}, …, r_{n} ∈ W (K)

mit p = ξ_{0} ⋯ ξ_{n} und

[ξ_{0}ξ_{1} ⋯ ξ_{n}, z, s] ⟼_{𝔎}^{1} [ξ_{1} ⋯ ξ_{n}, z, r_{1}] ⟼_{𝔎}^{1} ⋯ ⟼_{𝔎}^{1} [ξ_{n}, z, r_{n}] ⟼_{𝔎}^{1} [e, z, e]

Wir zeigen, daß es ein m > 0 derart gibt, daß für alle i ≤ m gilt:

r^{←}_{i} ⟼_{R}^{∗} ξ_{i} ⋯ ξ_{m}

Wenn das gezeigt ist, so erhalten wir für i = 0

s = s^{←} = r^{←}_{0} ⟼_{R}^{∗} ξ_{0} ⋯ ξ_{n} = p

d. h. p ∈ L(𝔊).

Wir überlegen uns zunächst, daß ein j mit 0 ≤ j ≤ n − 1 mit ξ_{j} = e existiert.

Wäre ξ_{0}, ξ_{1}, …, ξ_{n−1} ≠ e, so gilt wegen

[ξ_{n−1}ξ_{n}, z, r_{n−1}] ⟼_{𝔎}^{1} [ξ_{n}, z, r_{n}] , ξ_{n−1} ≠ e

daß r_{n−1} = r_{n}ξ_{n}, folglich wegen

[ξ_{n−2}ξ_{n−1}ξ_{n}, z, r_{n−2}] ⟼_{𝔎}^{1} [ξ_{n−1}ξ_{n}, z, r_{n−1}] , ξ_{n−2} ≠ e

r_{n−2} = r_{n−1}ξ_{n−2} = r_{n}ξ_{n−1}ξ_{n−2}, usw. Wir erhalten schließlich r_{0} = r_{n}ξ_{n−1} ⋯ ξ_{0} ≠ s, Widerspruch. Es gibt also ein j mit 0 ≤ j ≤ n − 1 und ξ_{j} = e, d. h.

m := max{j|j ≤ n − 1 ∧ ξ_{j} = e}

existiert. Dabei ist ξ_{m+1}, …, ξ_{n−1} ≠ e. Es gilt [ξ_{n}, z, r_{n}] ⟼_{𝔎}^{1} [e, z, e]. Dabei ist entweder r_{n} = ξ_{n} ∈ X oder ξ_{n} = e, r_{n} = h ∈ H, h → e ∈ R; in beiden Fällen gilt aber

r_{n} ⟼_{R}^{∗} ξ_{n}

Wegen ξ_{m+1}, …, ξ_{n−1} ≠ e ergibt sich wie oben

r_{m+1} = r_{n}ξ_{n−1}ξ_{n−2} ⋯ ξ_{m+1}

also

r^{←}_{m+1} ⟼_{R}^{∗} ξ_{m+1} ⋯ ξ_{n−1}ξ_{n}

Nun ist ξ_{m} = e und

[ξ_{m} ⋯ ξ_{n}, z, r_{m}] ⟼_{𝔎}^{1} [ξ_{m+1} ⋯ ξ_{n}, z, r_{m+1}]

d. h. es gibt r′_{m}, h mit

\begin{matrix}r_{m} = & r′_{m}h, h ∈ H, h → q ∈ R \\ r_{m+1} = & r′_{m} q^{←} \end{matrix}

Folglich

r^{←}_{m} = h r^{←}′_{m} ⟼_{R}^{1} q r^{←}′_{m} = r^{←}_{m+1} ⟼_{R}^{∗} ξ_{m+1} ⋯ ξ_{n} = ξ_{m}ξ_{m+1} ⋯ ξ_{n}

Damit haben wir unsere Behauptung für i = m schon bewiesen. Wir zeigen:

Wenn i ≥ 1 und r^{←}_{i} ⟼_{R}^{∗} ξ_{i} ⋯ ξ_{n} , so r^{←}_{i−1} ⟼_{R}^{∗} ξ_{i−1}ξ_{i} ⋯ ξ_{n}

Wir haben

[ξ_{i−1}ξ_{i} ⋯ ξ_{n}, z, r_{i−1}] ⟼_{𝔎}^{1} [ξ_{i} ⋯ ξ_{n}, z, r_{i}]

Wenn ξ_{i−1} ∈ X ist, so r_{i−1} = r_{i}ξ_{i−1}, also

r^{←}_{i−1} = ξ_{i−1} r^{←}_{i} ⟼_{R}^{∗} ξ_{i−1}ξ_{i} ⋯ ξ_{n}

andernfalls ist ξ_{i−1} = e, also existieren r′_{i−1}, h, q mit r_{i} = r′_{i−1} q^{←}, h → q ∈ R, r_{i−1} = r′_{i−1}h und folglich

r^{←}_{i−1} = h r^{←}′_{i−1} ⟼_{R}^{1} q r^{←}′_{i−1} = r^{←}_{i} ⟼_{R}^{∗} ξ_{i} ⋯ ξ_{n} = ξ_{i−1}ξ_{i} ⋯ ξ_{n}

Damit ist L(𝔎) ⊆ L(𝔊) erzeugt.

Wir zeigen nun L(𝔊) ⊆ L(𝔎). Sei p ∈ L(𝔊), d. h. es gibt eine Linksableitung von p in 𝔊, also

\begin{aligned}s = & h_{0} ⟼_{R}^{1} u_{1}h_{1}w_{1} ⟼_{R}^{1} u_{1}u_{2}h_{2}w_{2} ⟼_{R}^{1} ⋯ \\ & ⟼_{R}^{1} u_{1} ⋯ u_{n−1}h_{n−1}w_{n−1} ⟼_{R}^{1} u_{1} ⋯ u_{n} & = p \end{aligned}

wobei u_{1}, …, u_{n} ∈ W (X), h_{0}, …, h_{n} ∈ H, w_{1}, …, w_{n} ∈ W (X ∪ H) und h_{i} → q_{i} ∈ R mit

\begin{matrix}q_{i}w_{i} = & u_{i+1}h_{i+1}w_{i+1} \\ q_{n−1}w_{n−1} = & u_{n} \\ w_{0} = & e \end{matrix}

Folglich ist

[p, z, s] = [u_{1} ⋯ u_{n}, z, h_{0}] ⟼_{𝔎}^{1} [u_{1} ⋯ u_{n}, z, q^{←}_{0}]
= [u_{1} ⋯ u_{n}, z, w^{←}_{1}h_{1} u^{←}_{1}] ⟼_{𝔎}^{∗} [u_{2} ⋯ u_{n}, z, w^{←}_{1}h_{1}] ⟼_{𝔎}^{1} [u_{2} ⋯ u_{n}, z, w^{←}_{1} q^{←}_{1}]
= [u_{2} ⋯ u_{n}, z, w^{←}_{2}h_{2} u^{←}_{2}] ⟼_{𝔎}^{∗} [u_{3} ⋯ u_{n}, z, w^{←}_{2}h_{2}] ⟼ ⋯
⋮
= ⋯ ⟼ [u_{n}, z, w^{←}_{n−1} q^{←}_{n−1}]
= [u_{n}, z, u^{←}_{n}] ⟼_{𝔎}^{∗} [e, z, e]

also ist p ∈ L(𝔎).

Satz 3.3.3 Ist 𝔎 = [X, K, {z}, k_{1}, z, f] ein Kellerautomat mit genau einem Zustand, dann ist L(𝔎) ∈ 𝔏_{2}.

Ohne Beschränkung der Allgemeinheit können wir annehmen, daß X ∩ K = ∅ ist. Wir betrachten die Grammatik 𝔊 = [X, K, R, k_{0}] mit

R = {k → ξ w^{←}|[z, w] ∈ f(z, k, ξ), k ∈ K, ξ ∈ X ∪ {e}}

Offenbar ist 𝔊 vom Typ 2. Wie beim Beweis des Satzes 3.3.2 zeigt man

L(𝔊) = L(𝔎)

Kellerautomaten mit genau einem Zustand können also bereits alle kontextfreien Sprachen akzeptieren. Durch Vergrößerung der Zustandszahl erhöhen sich die Akzeptierungsfähigkeiten nicht:

Satz 3.3.4 Zu jedem Kellerautomaten mit l Zuständen und m Kellerzeichen gibt es einen Kellerautomaten mit nur einem Zustand und l^{2}m+1 Kellerzeichen, der dieselbe Sprache akzeptiert.

Die Beweisidee besteht darin, den aktuellen Zustand ebenfalls im Keller zu speichern.

Abschließend machen wir noch eine Bemerkung über kontextsensitive Sprachen. Wir wissen bereits, daß 𝔏_{3} ⊂ 𝔏_{2} ⊆ 𝔏_{1} gilt und daß die Sprache L = {a^{n}b^{n}a^{n}|n ≥ 1} ∉ 𝔏_{2} ist, obwohl sie Durchschnitt zweier kontextfreier Sprachen ist.

Man überzeugt sich leicht, daß L = {a^{n}b^{n}a^{n}|n ≥ 1} von der Grammatik 𝔊 = [{a, b}, {s, h_{1}, h_{2}}, R, s] erzeugt wird, wobei

R = {s → ash_{1}, s → ah_{2}, h_{2} → ba, h_{1}h_{2} → bh_{2}a, ah_{1} → h_{1}a}

ist. Allerdings erfüllen die letzten beiden Regeln nicht die für Typ–1–Grammatiken gestellte Forderung; vielmehr ist 𝔊 eine sogenannte beschränkte Grammatik:

Definition 3.3.5 Eine Grammatik 𝔊 = [X, H, R, s] heißt beschränkt, wenn für alle Regeln u → v ∈ R gilt l(u) ≤ l(v) mit Ausnahme von Regeln h → e, wobei aber h ∈ H auf keiner rechten Seite einer Regel vorkommen darf.

Die Sprache L = {a^{n}b^{n}a^{n}|n ≥ 1} besitzt also eine beschränkte Grammatik. Es gilt aber:

Satz 3.3.6 Zu jeder beschränkten Grammatik 𝔊 kann eine äquivalente Typ–1–Grammatik konstruiert werden.

Also ist L = {a^{n}b^{n}a^{n}|n ≥ 1} ∈ 𝔏_{1}, d. h. 𝔏_{3} ⊂ 𝔏_{2} ⊂ 𝔏_{1} ⊆ 𝔏_{0}.

Auch die letzte Inklusion in dieser Kette ist echt; wir beweisen das hier nicht, sondern zeigen, daß alle kontextsensitiven Sprachen entscheidbar sind.

Satz 3.3.7 Es gibt einen Algorithmus, der für jede beschränkte Grammatik 𝔊 und jedes Wort p ∈ W (X) in endlich vielen Schritten entscheidet, ob p ∈ L(𝔊) ist.

Beweis: Es ist p ∈ L(𝔏) genau dann, wenn es eine Zahl n und Wörter w_{1}, …, w_{n} ∈ W (X ∪ H) so gibt, daß

s = w_{0} ⟼_{R}^{1} w_{1} ⟼_{R}^{1} w_{2} ⟼_{R}^{1} ⋯ ⟼_{R}^{1} w_{n} = p

gilt. Weil 𝔊 beschränkt ist, ist daher l(w_{i}) ≤ l(w_{i+1}) also l(w_{i}) ≤ l(p). Ferner können wir voraussetzen, daß für i ≠ j stets w_{i} ≠ w_{j} ist, sonst könnten wir die Teilableitung w_{i} ⟼^{∗} w_{j} einsparen und gleich w_{i} = w_{j} ⟼^{1} w_{j+1} fortsetzen. Ist also m die Zahl der Wörter w ∈ W (X ∪ H) mit l(w) ≤ l(p), so muß n ≤ m sein. Um zu entscheiden, ob p ∈ L(𝔊) ist, genügt es also für i = 1, …, m alle i-Tupel von Wörtern u ∈ W (X ∪ H) mit l(u) ≤ l(p) daraufhin zu überprüfen, ob sie eine Ableitung von p bilden. Das kann in endlich vielen Schritten durchgeführt werden.

Berechenbarkeit

4.1 Einführung

Mit dem Satz 3.3.7 sind wir bereits in den Bereich der Algorithmentheorie gekommen, mit dem wir uns abschließend beschäftigen wollen — die Frage nach der Existenz von Algorithmen zur Lösung von Problemen wie dem Entscheidbarkeitsproblem für kontextsensitive Grammatiken.

Was ist ein Problem? Als Problem bezeichnen wir eine Familie von Aufgaben, die von einem oder mehreren Parametern abhängen. Dabei unterscheiden wir Berechnungsprobleme

{f(x_{1}, …, x_{n}) =? | x_{1}, …, x_{n} ∈ N}

und Entscheidungsprobleme, wie z. B.

{p ∈ L(𝔊)|p ∈ W (X), 𝔊 Typ–1–Grammatik}

in dem einen Fall geht es um die Berechnung eines Wertes (z. B. einer natürlichen Zahl), im anderen um die Bestimmung eines Wahrheitswertes.

Das Berechnungsproblem {f(x_{1}, …, x_{n}) =? | x_{1}, …, x_{n} ∈ N} der Funktion f heißt lösbar bzw. die zahlentheoretische Funktion f heißt berechenbar, wenn es einen Algorithmus gibt, der für jedes x_{1}, …, x_{n} ∈ N folgendes leistet:

Wenn f für [x_{1}, …, x_{n}] definiert ist, dann stoppt die Anwendung des Algorithmus auf [x_{1}, …, x_{n}] nach endlich vielen Schritten mit dem Wert f(x_{1}, …, x_{n}) als Resultat; wenn f für [x_{1}, …, x_{n}] nicht definiert ist, dann stoppt die Anwendung des Algorithmus niemals.

Wir verlangen also nicht, daß der Algorithmus erkennt, daß f für [x_{1}, …, x_{n}] nicht definiert ist und mit einer Fehlermeldung stoppt.

Was ein Algorithmus ist, bleibt an dieser Stelle offen; wir gehen zunächst davon aus, daß jeder ein Gefühl dafür hat, was ein algorithmisches Verfahren ist. Sicher ist, daß ein Algorithmus durch einen endlichen Text gegeben sein muß, damit er mitteilbar ist. Schon aus dieser Tatsache kann abgeleitet werden, daß es nicht–berechenbare Funktionen gibt!

Wir nennen eine Menge abzählbar unendlich, wenn sie eineindeutig auf die Menge N der natürlichen Zahlhen abgebildet werden kann.

Ist X ein endliches Alphabet, so ist W (X) offenbar abzählbar unendlich (die Wörter können abgezählt werden). Umfaßt X alle Zeichen im ASCII–Zeichensatz, so kommen unter den Wörtern aus W (X) auch alle Texte vor, die Algorithmen zur Berechnung zahlentheoretischer Funktionen mitteilen. Es gibt also nur abzählbar unendlich viele berechenbare Funktionen.

Andererseits gibt es überabzählbar viele einstellige zahlentheoretische Funktionen, die total, d. h. für alle x ∈ N definiert, sind. Das zeigt man durch das Cantorsche Diagonalverfahren:

Angenommen, (f_{i})_{i∈N} ist eine Abzählung aller einstelligen zahlentheoretischen Funktionen, dann betrachten wir die Funktion f^{∗} mit

f^{∗}(i) = f_{i}(i) + 1

Diese Funktion kommt in der Abzählung nicht vor, denn hätte sie die Nummer j (f_{j} = f^{∗}), so wäre

f_{j}(j) = f^{∗}(j) = f_{j}(j) + 1, Widerspruch.

Es gibt also keine Folge, in der alle einstelligen zahlentheoretischen Funktionen vorkommen, d. h. die Menge dieser Funktionen ist überabzählbar, d. h. es gibt nicht berechenbare Funktionen.

Mit diesem Beweis ist natürlich nichts darüber gesagt, ob es auch praktisch interessante Probleme (Klassen von Aufgaben) gibt, die algorithmisch unlösbar sind. Wir werden sofort ein solches Problem präsentieren, schicken aber voraus, daß ein Nichtexistenzbeweis auf der Basis eines intuitiven Algorithmenbegriffs nur schwer geführt werden kann, jedenfalls ist es einfacher einen Algorithmus zur Lösung eines Problems anzugeben und zu verifizieren. Die Nichtexistenz kann exakt nur auf der Basis einer Präzisierung, einer mathematischen Formalisierung, bewiesen werden.

Wir betrachten das sogenannte Halteproblem:

Gibt es einen Algorithmus A, der angewendet auf

(1) die textliche Beschreibung eines Algorithmus P

(2) einen Datensatz D

nach endlich vielen Schritten abbricht, und zwar mit dem Resultat ”TRUE“, wenn P ausgeführt mit D zum Ende kommt, und mit ”FALSE“, wenn die Ausführung von P mit D nicht abbricht.

Einen solchen Algorithmus zu kennen, wäre beim Test eines Programmes sicher vorteilhaft, wenn man im Zweifel ist, ob die Ausführung sehr lange läuft oder ob man durch einen Fehler in eine Schleife geraten ist, die nie verlassen wird.

Wir nehmen an, daß ein solcher Algorithmus existiert und führen diese Annahme zum Widerspruch. Wir präzisieren den Ansatz durch die Forderung, daß alle unsere Algorithmen als MODULA2–Programme gegeben sein sollen. Unsere Annahme bedeutet dann, daß eine Prozedur

PROCEDURE StoppTest (P: anyProcedure; D: file): BOOLEAN;

geschrieben werden kann, die die Datei D öffnet und entscheidet, ob die Prozedur P, wenn sie mit den Daten von D (einen Strom von Bits) beliefert wird, jemals verlassen wird.

Es sei D(P) eine Datei, auf der der MODULA–Text von P steht. Wir betrachten die Prozedur PROCEDURE SelfStoppTest(P: anyProcedure): BOOLEAN; BEGIN

RETURN StoppTest(P,D(P)); END SelfStoppTest;

Offenbar liefert SelfStoppTest für eine Pozedur P den Wert TRUE, wenn P auf D(P) stoppt, und sonst FALSE; kommt also immer zum Ende.

Wir betrachten nun die Prozedur

PROCEDURE Luegner(P: anyProcedure): BOOLEAN; VAR B : BOOLEAN; BEGIN

IF SelfStoppTest(P) THEN

LOOP

B := NOT B; END;

ELSE

RETURN TRUE END;

END Luegner;

die für eine Prozedur P genau dann stoppt (und zwar mit dem Wert TRUE), wenn P auf D(P) nicht stoppt.

Was passiert nun, wenn wir den Aufruf

Luegner(Luegner);

ausführen? Man sieht, daß die Ausführung Luegner(Luegner) genau dann stoppt, wenn sie nicht stoppt. Der erhaltene Widerspruch zeigt, daß die Prozedur StoppTest nicht existieren kann, mit andren Worten: Das Halteproblem ist unentscheidbar.

Bei unserer letzten Schlußfolgerung haben wir implizit eine weitere Annahme verwendet, daß sich nämlich alle Algorithmen in Form einer MODULA–Prozedur darstellen lassen. Diese Annahmen ist berechtigt, aber nicht bewiesen. Kann man sie überhaupt beweisen?

Man kann es nicht, weil es nicht möglich ist, Beweise über einen mathematisch nicht präzisierten Begriff zu führen. Wir können aber Vertrauen in diese These (die als Churchsche These bezeichnet wird) setzen, indem wir den Berechenbarkeitsbegriff auf verschiedene Weisen präzisieren (aus verschiedenen Ansätzen heraus) und diese Ansätze als gleichwertig nachweisen. Wir verfolgen hier zwei Ansätze

(1) einen mathematischen (axiomatischen Ansatz)

(2) einen maschinen–orientierten Ansatz

4.2 Mathematische Charakterisierung der Berechenbarkeit

Definition 4.2.1 ANF = Menge der folgenden Funktionen

(1) N (x) = x + 1 (Nachfolgerfunktion)

(2) C_{i}^{n} (x_{1}, …, x_{n}) = i (n-stellige Konstanten)

(3) I_{k}^{n} (x_{1}, …, x_{n}) = x_{k} (Argumentauswahl)

Satz 4.2.2 Alle Funktionen aus ANF sind berechenbar (und total definiert).

Definition 4.2.3 (Substitution) Die Funktion ϕ^{(n)} entsteht durch Substitution aus ψ^{(m)} und χ_{1}^{(n)}, …, χ_{m}^{(n)} gdw. ϕ (x_{1}, …, x_{n}) = ψ (χ_{1}^{(n)} (x_{1}, …, x_{n}) , …, χ_{m}^{(n)} (x_{1}, …, x_{n})). (χ müssen nicht überall definiert sein.)

Satz 4.2.4 Sind ψ und χ_{1}, …, χ_{m} berechenbare Funktionen und entsteht ϕ durch Substitution von ψ und χ_{1}, …, χ_{m}, so ist ϕ berechenbar.

C_{i}^{n} (x_{1}, … x_{n}) = N^{i} (C_{0}^{n} (x_{1}, …, x_{n}))

Definition 4.2.5 (Induktive Definition, die primitive Rekursion) Die Funktion ϕ^{(n+1)} entsteht durch primitive Rekursion aus ψ^{(n)} und χ^{(n+2)}, wenn ϕ die Lösung des folgenden Gleichungssystems ist:

(⋆) \{ \begin{matrix}ϕ (x_{1}, …, x_{n}, 0) & = & ψ (x_{1}, … x_{n}) \\ ϕ (x_{1}, … x_{n}, i + 1) & = & χ (x_{1}, … x_{n}, i, ϕ (x_{1}, … x_{n}, i)) . \end{matrix}

Satz 4.2.6 Sind ϕ und ψ gegebene Funktionen, so existiert genau ein ϕ mit (⋆).

Satz 4.2.7 Sind ψ, χ berechenbar und ϕ entsteht durch primitive Rekursion aus ψ und χ, so ist ϕ berechenbar.

Beweis

Geg: x_{1}, …, x_{n}, j

Ges: ϕ (x_{1}, …, x_{n}, j)

• 𝔄_{ψ} [x_{1}, …, x_{n}] → ϕ (x_{1}, …, x_{n}, 0)

– falls j = 0, so fertig

– sonst:weiter:

• 𝔄_{χ} [x_{1}, …, x_{n}, 0, ϕ (x_{1}, … x_{n}, 0)] → ϕ (x_{1}, …, x_{n}, 1)

4.2. MATHEMATISCHE CHARAKTERISIERUNG DER BERECHENBARKEIT49

– falls j = 1, so fertig

– sonst: weiter

Definition 4.2.8 (primitiv-rekursive Funktionen) PRM = die kleinste Klasse von zahlentheoretischen Funktionen, die ANF enthält und abgeschlossen bezüglich Substitution und primitiver Rekursion ist.

Beispiel Add + (m, n) + (m, 0) = I_{1}^{1} (m) + (m, m + 1) = N (I_{3}^{3} (m, i, + (n, i)))

Satz 4.2.9 Die primitiv-rekursiven Funktionen sind total

Offensichtlich sind die primitiv-rekursiven Funktionen nicht alle berechenbaren, denn z.B. die partiellen Funktionen gehören nicht zu PRM

Peterfunktion:

P : N × N → N
P (0, n) = n + 1
P (m + 1, 0) = P (m, 1)
P (m + 1, n + 1) = P (m, P (m + 1, n)))

z.z P berechenbar; betrachten:

PROCEDURE Peter(m, n:CARDINAL ):CARDINAL BEGIN

IF m = 0 THEN RETURN(m + 1); ELSE IF n = 0 THEN RETURNPeter(m − 1, 1); ELSE RETURNPeter(m − 1, Peter(m, n − 1)); END;

END; END Peter;

Lemma 4.2.10 Zu jeder einstelligen primitiv-rekursiven Funktion ϕ gibt es eine Zahl m derart, daß für alle n ∈ N gilt ϕ (n) < p (m, n).

Beweis: siehe Peter: ”Rekursive Funktionen“.

Konsequenz: P nicht primitiv-rekursiv, denn sonst

Q (n) = P (I_{1}^{1} (n) , I_{1}^{1} (n)) = P (n)

→Q primitiv-rekursiv.

Nach Lemma: ∃m^{⋆}: Q (n) < P (m^{⋆}, n). →Q (m^{⋆}) < P (m^{⋆}, m^{⋆}) = Q (m^{⋆}). ^{/}

→Erweiterung nötig, um alle berechenbaren Funktionen zu bekommen:

Erweitern um Suche nach Wert →Minimum-Operator Definition 4.2.11 (Minimum-Operator) Es sei ψ eine (n + 1)-stellige zahlentheoretische Funktion. Die partielle Funktion ϕ entsteht durch Anwenden des Minimum-Operators auf Ψ, wenn

ϕ (x_{1}, …, x_{n}) = μ_{j} (ψ (x_{1}, …, x_{m}, j)) = { das kleinste j ∈ N, mit ψ (x_{1}, … x_{n}, j) = 0 und ∀i < j ist ψ (x_{1}, …, x_{m}, i) definiert, falls solches existiert. nicht definiert, sonst

(Das ist Formalisierung des Systematischen Probierens.)

Satz 4.2.12 Ensteht ϕ durch Anwendung des Minimum-Operators auf ψ und ist ψ berechenbar, so ist ϕ berechenbar.

Beweis:

PROCEDURE PHI(x_{1}, … x_{n}:CARDINAL ):CARDINAL ; VAR i, j:CARDINAL ; BEGIN

i := 0 LOOP

j := PSI(x_{1}, …, x_{n}, i); IF j = 0 THEN RETURN; ELSE INC(i) END

END END PHI;

Definition 4.2.13 (partiell-rekursive Funktionen) PREK ist die kleinste Klasse von Funktionen, die ANF enthält und abgeschlossen ist bezüglich Substitution, primitiver Rekursion und Anwendung des Minimum-Operators.

Folgerung: PRM ⊆ PREK.

Definition 4.2.14 (allgemein-rekursive (rekursive) Funktionen REK)

REK = PREK ∩ TOTAL.

PRM{⊆ \atop ≠}REK{⊆ \atop ≠}TOTAL

Churchsche These: Eine zahlentheoretische Funktion ist genau dann berechenbar, wenn sie partiellrekursiv ist.

[figure: Zuständen; endlich vielen; ⋯; ⋯; Kopf; Programm mit]

Abbildung 4.1: Turing Maschine

Was ist Rechnen • Rechnen ist, was Maschinen tun.

• Turing

• Manipulation von Wörtern

• Beweisen von Gleichungen der Form y = ϕ (x_{1}, …, x_{n})

• Gödel

• Markowscher Algorithmenbegriff

• Postscher Algorithmenbegriff

A. M. Turing 1936

• Band, beidseitig unbegrenzt

• eingeteilt in Felder

• in jedem Feld ein Zeichen aus einem endlichen Alphabet oder Leerzeichen

Definition 4.2.15 T = [X, Z, z_{0}, δ] ist Turing-Maschine, wenn:

(1) X endliches Alphabet ⋆(Leerzeichen) ∉ X

(2) Z endliche Menge von Zuständen

(3) δ : Z × (X ∪ {⋆}) → (X ∪ {⋆}) × B × Z, wobei B = {R, L, N, S}

Arbeitsweise

(1) T arbeitet taktweise, in Takt 1 ist T im Zustand z_{0}.

(2) Ist z_{i−1} der Zustand von T im Takt i und x das Zeichen im betrachteten Feld und δ (z_{i−1}, x) = [y, b, z], so wird y in das betrachtete Feld geschrieben. Dann wird die Kopfbewegung b ausgeführt (bei b = S wird gestoppt) und in den Zustand z_{i} übergegangen.

Definition 4.2.16 (Turing-berechenbar) Sei ϕ : X_{n} N → N eine Zahlentheoretische funktion.

ϕ heißt Turing-berechenbar, wenn es eine TM T = [{|} , Z, z_{0}, δ] so gibt, daß für alle x_{1}, x_{2}, …, x_{n} ∈ N gilt:

Wenn [x_{1}, …, x_{n}] ∈ D_{ϕ} und T wird in der Situation ⋯ ⋆ ⋆ \underbrace{| ⋯ |}_{x_{1}+1} ⋆ \underbrace{| ⋯ |}_{x_{2}+1} ⋆ ⋯ ⋆

\underbrace{| ⋯ |}_{x_{n}+1} ⋆⋆ ; △ ; z gestartet, so stoppt T nach endlich vielen Takten in der Situation

⋯ ⋆ ⋆ \underbrace{| ⋯ |}_{x_{1}+1} ⋆ \underbrace{| ⋯ |}_{x_{2}+1} ⋆ ⋯ ⋆ \underbrace{| ⋯ |}_{x_{n}+1} ⋆ \underbrace{| ⋯ |}_{ϕ(x_{1},...,x_{n})} ⋆ ; △ ; z_{0} .

Wenn [x_{1}, …, x_{n}] ∉ D_{ϕ}, so kommt T nicht zum Stop.

Wir verlangen noch zusätzlich, daß der Kopf bei der Berechnung nicht über das zweite leere Feld links von den Argumenten hinausläuft.

Ziel: ϕ Turing-berechenbar gdw. ϕ partiell-rekursiv.

Bausteine (für die Turing-Maschine)

• X = {|}–fest.

• ”Gehe ein Feld nach rechts“

\begin{matrix}r & ⋆ & | \\ 1 & ⋆R2 & |R2 \\ 2 & ⋆S & |S \end{matrix}

• ”Gehe ein Feld nach links“

\begin{matrix}l & ⋆ & | \\ 1 & ⋆L2 & |L2 \\ 2 & ⋆S & |S \end{matrix}

• ”Schreibe | auf das Betrachtete Feld“

\begin{matrix}”|“ & ⋆ & | \\ 1 & |N2 & |N2 \\ 2 & |S & |S \end{matrix}

• ”bedingter Sprung“

\begin{aligned}& [figure: |; ⋆] & ⋆ & | \\ 1 & & ⋆N2 & |N3 \\ 2 & & ⋆S & – \\ 3 & & – & |S \end{aligned}

• Verkettung: P_{1}; P_{2} P_{1} → P_{2}

– P_{1} habe Zustände 1, …, l

– P_{2} habe Zustände 1, …, k

– In P_{2} alle Adressen um l erhöhen: l + 1, …, l + k – In P_{1} alle Stoppanweisungen ersetzen durch ⋆Nl+1 bzw. |Nl+1 (Übergang

in den Anfangszustand von P_{2})

• ”Nach rechts auf den ersten ⋆ gehen“:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; r; |; ⋆]
”R“ ⋆  |
1 ⋆N2  |N3
2 ⋆S  –
3 –  |S↔N4
4 ⋆R5  |R5
5 ⋆S↔N1 |S↔N1

wobei ↔:= ”ersetzen“ – für beliebig.

• n ≥ 1 R_{n}: ”Gehe nach rechts auf den n-ten ⋆, der ⋆ unter dem Kopf mitgezählt.

– R_{1} := R

– R_{n} := (Rr)^{n−1}R

• L_{n}: ”Gehe nach links …“

– L_{1} = L

– L_{n} = (Ll)^{n−1} L.

• K_{n}: ”Kopiere die n-te Strichfolge links von Kopf“

d.h. ⋆ \underbrace{| ⋯ |}_{k_{n}} ⋆ ⋯ ⋆ \underbrace{| ⋯ |}_{k_{n}} ⋆ ⋯ ⋆ →

⋆ \underbrace{| ⋯ |}_{k_{n}} ⋆ ⋯ ⋆ \underbrace{| ⋯ |}_{k_{n}} ⋆ \underbrace{| ⋯ |}_{k_{1}} {⋆ \atop △} ⋆ ⋯ ⋆

k_{1} = 0 erlaubt

[figure: ⋆R_{n+2}|L_{n+1}|; R_{n+1}; K_{n} = L_{n+1}r; ⋆; |]

Satz 4.2.17 Alle Anfangsfunktionen sind Turing-berechenbar

Beweis: ANF:

(1) N (x) = x + 1: ⋆ ⋆ \underbrace{| ⋯ |}_{x+1} {⋆ \atop △} ⋯ →star \underbrace{| ⋯ |}_{x+1} ⋆ ⋆ \underbrace{| ⋯ |}_{x+2} {⋆ \atop △}

→N = K_{1}r.

(2) C_{i}^{n} (x_{1}, …, x_{n}) = i ⋆ ⋆ x_{1} ⋆ x_{2} ⋆ ⋯ ⋆ x_{n}{⋆ \atop △} ⋯

→(r|)^{i+1} r.

(3) I_{k}^{n} (x_{1}, …, x_{n}) = x_{k}. →K_{n−k+1} Löschprogramm Lö [figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; L_{2}lLl; ⋆; |; ⋆; |; |r|Rl; r|; r|Rl⋆; ⋆r|Rl ⋆ L_{2}]

Satz 4.2.18 Wenn ϕ durch Substitution aus ψ und χ_{1}, …, χ_{m} entsteht und ψ, χ_{1}, …, χ_{m} sind Turing-berechenbar, so ist ϕ Turing-berechenbar.

Beweis: ϕ (x_{1}, …, x_{n}) = ψ (χ_{1} (x_{1}, …, x_{n}) , …, χ_{m} (x_{1}, …, x_{n}))

Sei H_{i} berechne χ_{i} P berechne ψ

Behauptung F = r|r (K_{n+1})^{n} L_{n+1}l⋆R_{n+2}H_{1} (K_{n+1})^{n} H_{2} ⋯ (K_{n+1})^{n} H_{m}K_{(m−1)n+m}K_{(m−2)n+m} ⋯ K_{m}P Lö

Satz 4.2.19 Entsteht ϕ durch primitive Rekursion aus ψ und χ und sind ψ, χ Turing-berechenbar, so ist ϕ Turing-berechenbar.

Beweis: Sei P berechne ψ H berechne χ.

F berechnet ϕ

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; F = r|rK_{2} (K_{n+3})^{n} L_{n+3}r ⋆ R_{n+3}P r|r; l|R_{n+3}l; L_{n+4}r ⋆ r; Lö; ⋆; R_{n+3}|k_{n+4}L_{n+6}|R_{n+5} (K_{n+4})^{n} K_{n+2}K_{n+4}; ⋆; |; ⋆; |]

Satz 4.2.20 Entsteht ϕ durch Anwendung des ν-Operators auf ψ und ψ ist Turing- berechenbar, so ist ψ Turing-berechenbar.

Beweis: F berechne ϕ; P berechne ψ

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; ⋆l; F = r|rP l ⋆ l; |; ⋆; |; ⋆; |; ⋆; |; ⋆]

Folgerung: Alle partiell-rekursiven Funktionen sind Turing-berechenbar.

Satz 4.2.21 Jede Turing-berechenbare Funktion ist partiell-rekursiv.

Hierzu beweist man durch ”Gödelisierung“:

Satz 4.2.22 (Kleenescher Darstellungssatz) Es gibt eine primitiv-rekursive Funktion α derart, daß für jede Stellenzahl n eine (n + 2)-stellige primitiv-rekursive Funktion β so existiert, daß zu jeder Turing– berechenbaren Funktion f eine Zahl t existiert so, daß für alle [a_{1}, …, a_{n}] gilt:

f (a_{1}, …, a_{n}) = α (μ_{j} (β (t, a_{1}, …, a_{n}, j) = 0)) .