close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

15 Wie ist der bisherige Stand der Erkenntnis?

EinbettenHerunterladen
15 Wie ist der bisherige Stand der Erkenntnis?
Nach den bisherigen Ausführungen stellen sich die Beziehungen zwischen den behandelten
Sprachfamilien über einem Alphabet Σ wie folgt dar, wobei außerdem noch der Sachverhalt
angedeutet ist, dass es weitere Sprachfamilien gibt, hier kursiv geschrieben:
Überblick über die Sprachfamilien
Bezüglich der semientscheidbaren / rekursiv aufzählbaren Sprachen werden wir einen interessanten Automatentypen kennen lernen, die Turing-Maschinen, die mehr können als Kellerautomaten, die z.B. die Sprache {anbncn | n$1}- und noch komplexere- erkennen oder wie wir
auch sagen werden “entscheiden” können.
Zu den Typ1-Grammatiken korrespondiert ein eher uninteressanter Automatentyp, die Linear
Beschränkten Automaten LBAen.
Die Potenzmenge (Σ*) über einem Alphabet Σ ist überabzählbar unendlich. Dies lässt sich
durch das Cantorsche Diagonalverfahren beweisen. Da es aber nur abzählbar unendlich viele
Typ0-Grammatiken gibt (man kann sie sich lexikographisch angeordnet und dann durchnummeriert denken), muss es Zeichenkettenmengen, also Sprachen, geben, für die es keine Charakterisierung mittels Typ0-Grammatiken gibt.
119
Mit den Typ0-Grammatiken und den Turing-Maschinen kommen wir zu der wichtigen Fragestellung, ob es Probleme gibt, zu denen wir grundsätzlich keinen Algorithmus angeben, also
kein Programm schreiben können. Dabei wird von solchen “Nebensächlichkeiten” wie unbeschränkte/r aber endliche/r Rechenzeit/Speicherbedarf abstrahiert.
Zunächst im Folgenden noch eine kurze Zusammenfassung der wichtigsten bisherigen Erkenntnisse und ein Ausblick auf die Turing-Maschinen.
Weil Sprachen Mengen sind, haben wir schon wiederholt im Zusammenhang mit
mengentheoretischen Operationen eine Reihe von Fragen angesprochen, wie z.B. “Ist die Vereinigung / der Durchschnitt / das Produkt zweier Sprachen vom Typ i wieder eine Sprache vom
Typ i ?” oder “Ist das Komplement von / die Sternoperation auf einer Sprache vom Typ i wieder
eine solche ?”
Weitere Fragestellungen im Hinblick auf entscheidbare Eigenschaften - was das genau ist, wird
in späteren Kapiteln noch erklärt - von Sprachen und Grammatiken haben wir ebenfalls angesprochen, z.B.: Ist es entscheidbar, ob zwei Grammatiken G1 und G2 äquivalent sind, d.h. ob
L(G1) = L(G2) ist, oder m.a.W. die gleiche Sprache erzeugen? Ist das Wortproblem für eine
vorgelegte Grammatik entscheidbar? Ist entscheidbar, ob L(G) leer oder ob sie endlich ist? U.s.w.
120
Wörtermenge,
definiert
durch/als
Maschine(n)
AutomatenÄquivalenz
abgeschlossen
unter
entscheidbar
bzw.
unentscheidbar
Anwendungsbereich \
Sonstiges
reguläre Sprache
& Typ 3-Grammatik bzw. reguläre Grammatik &
regulärer Ausdruck
endlicher Automat &
nichtdeterministischer
endlicher Automat &
nichtdeterministischer
endlicher Automat mit
g-Übergängen
ja, alle
Vereinigung &
Produkt / Konkatenation
& Kleene- /
Sternoperation &
Durchschnitt &
Komplement & Differenz & Spiegelsprachebildung
Äquivalenz? ja!
Leerheit? ja!
Endlichkeit? ja!
Wortproblem? ja!
einfache Reihenfolgeprobleme;
“endliches” Zählen (modulo)
\
“uvw-Lemma” (“PumpingLemma”); Lemma von Jaffe;
Satz von Nerode
(allgemeine)
kontextfreie
Sprache &
Typ 2-Grammatik bzw.
kontextfreie
Grammatik
Kellerautomaten (mit
Erkennung durch leerem Keller oder durch
Endzustände)
ja (aber nicht
zwischen deterministisch
und nichtdeterministisch!)
Vereinigung &
Produkt/Konkatenation
& Kleene-/Sternoperation & Spiegelung
(aber nicht die anderen
von oben!)
Äquivalenz? nein!
Leerheit? ja!
Wortproblem? ja!
komplexe Reihenfolgeprobleme
wie ("Klammersprachen")
\
“uvwxy-Lemma”; Satz von
Chomsky und Schützenberger
deterministische
kontextfreie
Sprachen
det. Kellerautomat mit
Erkennung durch leerem Keller << det.
Kellerautomat mit Erk.
durch Endzustände
nein
Komplement (nicht aber
die anderen von oben!)
\
regSpr 1 detKfrSpr =
detKfrSpr
diverse Bezüge zu
regulären Sprachen
121
Vieles ist aber
nicht entscheidbar,
s. u.
Programmiersprachendefinition
(Erkennung in linearer Zeit
möglich!) \ Äquivalenz zwischen Präfixeigenschaft und
Erkennen mit leerem Keller
Für (allgemeine) kontextfreie Grammatiken ist z.B. auch nicht entscheidbar, ob
>
>
>
>
>
zwei Grammatiken dieselbe Sprache generieren; nicht einmal, ob sie ein gemeinsames
Wort generieren,
eine Grammatik mehrdeutig ist, d.h. zu einem Wort verschiedene Syntaxbäume existieren,
zu einer Grammatik ein deterministischer Kellerautomat existiert,
das Komplement einer kontextfreien Sprache wieder kontextfrei ist,
ob es Wörter gibt, die eine kontextfreie Grammatik nicht (!) generieren kann.
Wie oben angedeutet, kommt ein neuer Typ von Automat, die Turing-Maschine (und mit ihr
einige Variationen), im Folgenden hinzu. Mit ihm/ihr kann man die Begriffe “entscheidbar /
berechenbar” präzisieren. Dieser Sachverhalt gliedert sich in das o.a. Schema wie folgt ein:
Wörtermenge,
definiert
durch/als
Maschine(n)
Automaten Äquivalenz
abgeschlossen
unter
entscheidbar
bzw.
unentscheidbar
Anwendungsbereich \
Sonstiges
allgemeine Regelsprache
&
rekursiv aufzählbare Sprache
&
Typ-0-Grammatik
Turing-Maschine
&
Registermaschine
&
Kellerautomat
mit zwei Kellern
&
n-Band-Turing-Maschine
ja
Vereinigung
Wortproblem? nein!
Produkt /
Konkatenation
Sternoperation
(Und auch
sonst ist
nicht viel
entscheidbar, z.B.
nicht das
Präzisierung des
"Algorithmus"-Begriffes
Durchschnitt
Halteproblem .)
122
16 Wie kann man allgemeine Regelsprachen noch charakterisieren ?
Analog zu den Automatenmodellen bei einseitig linearen / regulären Sprachen (Endlicher
Automat) und bei den (allgemeinen) kontextfreien Sprachen (nichtdeterministischer Kellerautomat, der mit ausgezeichnetem Zustand oder mit leerem Keller erkennt) werden im folgenden
Automaten angegeben, die das Analyseprobleme für Typ-0-Grammatiken erledigen können.
Diese Aufgabe wird aber nicht mit der Vollständigkeit wie bei EA oder KA durchgeführt, d.h.
es gibt, salopp gesagt, nicht immer ein klares “ja” oder “nein” sondern manchmal eine Art “weiß
es noch nicht, bin noch am Schaffen”.
16.1
>
Das Basismodell: die Turing-Maschine
Historischer Hintergund: Die Bemühung, logisches Schließen ("Folgern", "Ableiten") als
"Rechnen"12 zu begreifen.
>
Leibniz (1686): "Calculemus"
>
Frege (1876): "Ganzes von Regeln, die den Übergang beschreiben"
>
Hilbert (ab 1900) (& Bernays (angeblich noch bis 1934)): "Jede Aussage ist
verifizierbar bzw. falsifizierbar", als Entscheidungsproblem bekannt.
>
Gödel (1931): "In hinreichend komplexen Kalkülen wie der Arithmetik, gibt es
wahre Aussagen, für die kein Beweis existiert."
>
Turing (1936): "On Computable Numbers with an Application to the Entscheidungsproblem". Er führte ein abstraktes Maschinenmodell ein, das ihm zu Ehren TuringMaschine genannt wurde.13
>
Grammatiken kamen erst 1956 (Chomsky).
>
Church'sche / Turing’sche [Hypo]These (1941): "Die Turingmaschine und die ihr
äquivalenten Modelle (rekursive Funktionen, Postsche Systeme, λ-Kalkül, Registermaschine, etc.) sind eine äquivalente Formulierung des Algorithmenbegriffs."
12
Hier im Sinne eines mechanischen - an sich sinnentleerten Umgangs - mit Zeichen.
13
Proc. of the London Math. Society, (2) 42 (1937); Korr. ebd. 43 (1937).
123
>
Turing betrachtet das Rechnen mit Stift und Papier, bei dem Folgendes passieren kann:
>>
Symbole werden auf Papier geschrieben und ggf. wieder gelöscht. Es dürfen nur
endlich viele Symbole verwendet werden, aber, wenn nötig, kann beliebig (“potentiell unendlich”, aber immer endlich) viel Papier zur Verfügung gestellt werden.
>>
Das Papier wird in Zellen (Felder) unterteilt. So kann aus einem zweidimensionalen Papier leicht ein (eindimensionaler) Streifen werden. Man betrachtet nur
immer ein/e Feld/Zelle, in dem/der immer nur ein Symbol steht. Man kann sich es
auch modellhaft so vorstellen, dass ein Lese/Schreibkopf über das Band geführt
wird.
>>
Man kann der Reihe nach immer nur den aktuellen und danach den jeweiligen linken oder rechten Nachbarn betrachten.
>>
Die “rechnende” Person/Maschine hat endlich viele “Geisteszustände”.
>>
In Abhängigkeit des aktuellen (Geistes)-Zustands und dem aktuellen Symbol auf
dem Band kann (muss also nicht):
>>>
der Inhalt der aktuellen Zelle geändert, und dann
>>>
in einen neuen Zustand übergegangen,
>>>
ggf. der Lese/Schreibkopf (bzw. das Band) nach links oder rechts bewegt
werden.
>>
Die Berechnung beginnt, und dann gibt es nach einer gewissen Zeitspanne zwei
Möglichkeiten. Das Gerät stoppt oder (noch) nicht. Im letzten Fall sind wieder 2
Möglichkeiten zu unterscheiden: Der Stopp kommt später oder überhaupt nicht!
124
>
Anschaulich kann man sich eine Turing-Maschine als ein (Ton-)Bandgerät vorstellen, bei
dem das Band in Felder unterteilt ist. Oder auch: Eine Turing-Maschine ist ein endlicher
Automat mit einem zusätzlichen Bandmechanismus, der über die Kellerautomaten-Möglichkeiten insofern hinausgeht, dass der Unterschied zwischen Eingabeband und Keller
aufgehoben wird und beide zu einem Band verschmolzen werden. Die Beschränkung
beim Keller, dass nur immer “oben” gelesen werden darf, wird auch aufgegeben.
Modell einer Turing-Maschine
Definition:
Eine deterministische Turing-Maschine (abgek.: DTM) oder Turing-Automat T ist ein 6-Tupel
T=
(
G
Γ
Q
q0
F
δ
Eingabealphabet,
Bandalphabet, mit G f Γ; also alles, was auf dem Band stehen
darf, wobei das Leerzeichen nicht als Element von G betrachtet
wird
Menge der Zustände,
Anfangszustand,
Menge der Endzustände mit FfQ,
Zustandübergangsfunktion
)
wobei gilt: δ : (Q \ F) × Γ 6 Q × Γ × {6, 7, 9}
Der Ausdruck δ(q, a) = (q', a', 6) bedeutet: “Sieht die Maschine im Zustand q ein a auf dem
Band, geht sie in den Zustand q' über, schreibt ein a' (das gleich a sein kann, de facto also nichts
verändert) und geht auf das rechte Feld.” Analoges gilt für die anderen Symbole, also 7 für links
und 9für stehen bleiben.
Die Funktion δ nennt man auch das Turing-Maschinenprogramm von T.
Ê
125
Beispiel:
Addition zweier Zahlen, die durch Strichlisten dargestellt sind. Z.B. wird 1 + 2 zu ||+||| oder zu
||$|||.
Idee: Auf dem Band steht anfangs
...
#
|
|
$
|
|
|
#
...
Das Ergebnis jeder Berechnung zweier Zahlen ist z.B. dadurch zu bekommen, dass man
zunächst $ durch | ersetzt. Jetzt hat man zwei Striche zu viel, die rechts weggenommen, also
durch # ersetzt werden.
δ:
(q0, #)
(q0, |)
(q0, $)
(q1, |)
(q1, #)
(q2, |)
(q3, |)
|
|
|
|
|
|
|
(q0, #, 6)
(q0, |, 6)
(q1, |, 6)
(q1, |, 6)
(q2, #, 7)
(q3, #, 7)
(qh, #, 9)
Neben einer naheliegenden Darstellung von δ, in der man die zwei Tupel in einem zusammenfasst, also z.B. statt wie oben
δ : (q0, #) | (q0, #, 6) oder δ(q0, #) = (q0, #, 6)
vielleicht etwas kürzer
(q0, #, q0, #, 6)
schreibt, gibt es auch wieder die Darstellung der Übergangsfunktion als Zustandübergangsdiagramm:
Ê
126
Anmerkungen:
>
Die Übergangsfunktion δ ist vorne der Einfachheit halber gleich deterministisch definiert.
Nichtdeterministische Turing-Maschinen, abgek.: NTM “können nicht mehr” als DTM,
d.h. DTM sind in der Lage, NTM zu simulieren. Wenn wir von TM sprechen, sind DTM
gemeint, wenn nichts anderes vermerkt ist.
Bei einer nichtdeterministischen Turing-Maschine NTM gilt
δ(q, a) f Q × Γ × {6, 7, 9}
Dann müsste man schreiben: δ(q0, #) = {(q0, #, 6), ...}
Es gibt eine Vielzahl von “leichteren Variationen” der TM, die sich nach kurzer Betrachtung
als äquivalent in dem Sinne erweisen, dass man stets zu einer TM des einen Typs eine äquivalente des anderen finden kann, wie z.B.:
>
Manchmal wird δ so definiert: δ : (Q \ F) × Γ 6 Q × (Γ c {6, 7}). Dann kann die TM also
nur als Aktion entweder Schreiben oder Sichbewegen ausführen. Dieser TM-Typ ist
äquivalent zum allgemeiner definierten.
>
Es genügt, einen einzigen Endzustand zu haben. Eine TM hält schon, wenn für einen
Zustand q in δ kein Nachfolgezustand definiert ist. Dies kann als gleichbedeutend mit
zusätzlichen Übergängen von den Zuständen ohne Nachfolgerzustand in den Endzustand
für jedes γ 0 Γ aufgefasst werden.
>
Der Bequemlichkeit halber gibt es in Γ \ G die Zeichen $ und #, nämlich Trennzeichen
und Bandbegrenzung. Die Bandbegrenzung muss man sich so vorstellen, dass sie bei
Bedarf nach rechts oder links verschoben werden kann.
>
Man kann TM “abmagern” bis auf zwei Symbole bzw. zwei Zustände. Man kann quasi
Zustände in Symbolen codieren und umgekehrt.
>
Ganz offensichtlich ist jeder Kellerautomat auch eine TM. Umgekehrtes gilt nicht!
>
Um Turing-Maschinen kombinieren zu können, sollte man sie so programmieren, dass sie
sich in einer eindeutig definierten Situation ablösen. Insbesondere sollte das Band nur
noch solche Zeichenketten enthalten, die für die weitere Rechnung wichtig sind. Hilfreich
hierfür ist die Technik des “Aufräumens des Bandes”, dass z.B. zu jeder Turing-Maschine
M es eine Turing-Maschine M' gibt, die dieselbe Funktion berechnet wie M, und die,
wenn sie hält, auf dem Band nur das Ergebnis stehen hat.
>
Die Verwendung solcher "ordentlichen" Turing-Maschinen macht ihre Kombination
einfach: Berechnet M1 eine Funktion f1 : (Σ*)i 6 (Σ*)k und M2 eine Funktion f2 : (Σ*)k 6
(Σ*)l, so lässt sich aus M1 und M2 eine Turing-Maschine zur Berechnung von f2 B f1 : (Σ*)i
6 (Σ*)l bauen: Benenne alle Zustände von M2 so um, dass sie in M1 nicht vorkommen,
ersetze jedes Vorkommen des Haltezustands h im Programm für M1 durch den Startzustand von M2 und füge die beiden Programme zusammen. Startzustand der neuen Maschine ist der Startzustand von M1.
Ê
127
Der wichtige Konfigurationsbegriff, wie wir ihn bei den endlichen und den Kellerautomaten
kennen gelernt haben und der sehr handlich für die Beschreibung der Arbeitsweise eines Automaten ist, lässt sich auch auf die TM übertragen:
Definitionen:
Es ist hilfreich für die Programmierung einer TM, sich den (relevanten) Arbeitsbereich mit
dem speziellen Symbol # 0 Γ begrenzt vorzustellen, das sonst auf dem Band nicht mehr vorkommt. Eine Konfiguration ist dann ein Tupel
(
q
#αx
0Z,
mit α 0 (Γ \ {#})*, x 0 Γ
y
zβ#
0Γ,
mit β 0 (Γ \ {#})*, z 0 Γ
der aktuelle Zustand
der links vom aktuellen Symbol
stehende Bandinhalt
das aktuell betrachtete Symbol
der rechts vom aktuellen Symbol
stehende Bandinhalt
)
Manchmal sieht man statt (q, #αx, y, zβ#) übersichtlicher auch #αxqyzβ# geschrieben. Der
Zustand q kennzeichnet so die Stelle, auf der der Lese/Schreibkopf steht.
Die Nachfolgekonfiguration zu (q, #αx, y, zβ#) ist (q', #αxw, z, β#), i.Z. (q, #αx, y, zβ#) | (q',
#αxw, z, β#), gdw. (q', w, 6) 0 δ(q, y) oder im deterministischen Fall δ(q, y) = (q', w, 6) ist, also
im Zustand q beim Sichten von y das Symbol w auf das Band geschrieben und dann nach rechts
gegangen wird. Analoges gilt für die beiden anderen Bandbewegungen.
Es ist eine Art Geschmacksfrage, wie man die Startkonfiguration definiert. Meist lässt man die
Maschine T auf oder direkt rechts von der linken Bandbegrenzung beginnen. Das impliziert bei
einer quasi "leeren Eingabe", dass T auf der rechten Bandbegrenzung steht. Im u.a. Beispiel
stünde demnach der Kopf über dem a.
...
#
a
b
c
$
0
1
0
$
e
#
...
Analog kann man die Endkonfiguration verschieden definieren. Man kann eine TM stets so
umformen, dass sie ihr Band am Ende der eigentlichen Arbeit “aufräumt”, also nur noch das
Ergebnis auf dem Band hat und “ordentlich” vor oder nach diesem steht (natürlich nur, wenn sie
überhaupt hält!).
Ê
128
Anmerkungen (Äquivalenz der Begriffe Akzeptieren/Erkennen, Berechnen, Entscheiden):
>
Beim einführenden Beispiel, Addition zweier durch Strichlisten dargestellter Zahlen,
um die Funktionsweise einer Turing-Maschine zu erläutern, sprachen wir salopp vom
“Berechnen des Ergebnisses”, also von der Erzeugung einer Zeichenkette, die wir intuitiv
als die Summe der beiden Zahlen interpretieren wollen. Dabei sind wir scheinbar weggegangen von der bislang gewohnten Sprechweise bzgl. der Endlichen Automaten und
den Kellerautomaten. Wir sagten, dass die letzteren “eine Sprache erkennen” können und
nannten sie auch “Akzeptoren”, die als Ausgabe nur “ja” oder “nein” sagen. Allerdings
überwanden die Mealy- und Moore-Automaten diese Wortkargheit. Sie können komplexere Ausgaben machen - sind aber, wie gezeigt, nicht mächtiger als die EA.
>
Auch eine TM T kann man zunächst nur als Akzeptor sehen, indem man eine zu
erkennende Zeichenkette z auf ihr Band schreibt. Gemäß des Programms von T, das die
zu entscheidende Eigenschaft von z (z.B.“ist Palindrom”) untersucht, wird als Ergebnis
“ja” oder “nein” auf das Band geschrieben, bevor T stoppt. Dabei ist es irrelevant, ob
gleichsam noch “Schmutz” auf dem Band steht.
>
Im obigen Absatz wurde bewusst schon mal die Sprechweise “zu entscheidende
Eigenschaft ... Palindrom” benutzt. Sie ist gleichwertig zur Sprechweise “akzeptieren /
erkennen einer Zeichenkette, die ein Palindrom ist”.
>
Durch die Möglichkeit, dass eine TM recht flexibel mit dem Bandinhalt umgehen kann,
tritt der Aspekt “Akzeptieren von Zeichenketten” in den Hintergrund und das “Berechnen” in den Vordergrund. Man sollte sich aber Folgendes bewusst machen: Eine TM TP,
die z.B. die Palindromeigenschaft einer Zeichenkette entscheiden / Palindrome akzeptieren soll, kann man als Funktion interpretieren, mit beispielsweise TP(abba) = 1 und
TP(abbaa) = 0. Man kann also allgemein sagen: Die “Erkennung”, das “Akzeptieren”, das
“Entscheiden” eines Wortes σ 0 V* über einem Alphabet V relativ zu einer Grammatik
G ist eine “Berechnung”, die z.B. den Wert 1 liefern soll, wenn σ 0 L(G) ist, und 0, wenn
dies nicht der Fall ist.14 Das Akzeptieren/Erkennen einer Sprache ist somit gleichwertig
zur Berechnung ihrer charakteristischen Funktion.
>
Mit dieser Einsicht kann man erahnen, dass “Akzeptieren / Erkennen”, “Berechnen”
und “Entscheiden” äquivalente Begriffe für letztendlich denselben Sachverhalt sind. Nur
je nach Kontext werden sie entsprechend verwendet. Im Folgenden soll das weiter
präzisiert werden. Insbesondere der Begriff “entscheidbar” wird noch eingehender
behandelt.
Ê
14
Es klingt unschön zu sagen, “eine Sprache wird berechnet”.
129
Der Vollständigkeit halber:
Definition:
Ein TM T = (G, Γ, Q, q0, F, δ) erkennt/akzeptiert eine Sprache L f G* gdw. gilt:
L = {w 0 G* | #q0w# |* #αhβ#, α,β 0 Γ*, h 0 F}
Ê
Zurück zur Beziehung zwischen TM und Typ0-Sprachen, die am Anfang des Kapitels erwähnt
wurde: Man beachte, dass man die o.a. Berechnung der Addition auch durch folgende Grammatik
simulieren kann. (Achtung, der Strich | ist nicht als Alternativsymbol zu interpretieren, sondern
steht für sich selbst!):
S
E
E
Z
Z
B|
B$
|B#
|C#
6
6
6
6
6
6
6
6
6
#B|E$|Z#
|E
g
|Z
g
|B
|B
C#
#
Erstellung der Startkonfiguration
Erstellung der Startkonfiguration
Erstellung der Startkonfiguration
Erstellung der Startkonfiguration
Erstellung der Startkonfiguration
Durchschieben
Umschreiben von $
Löschen von |
Löschen von | und Stopp
Die letzten 3 Produktionen könnte man sogar noch ersetzen durch
| B $ 6 g.
Das o.a. Beispiel lässt sich verallgemeinern. Es gibt hier also eine analoge Beziehungen wie
zwischen regulären/Typ3- bzw. kontextfreien/Typ2-Grammatiken und Endlichen Automaten
bzw. Keller-Automaten:
Satz:
Zu jeder Turing-Maschine T lässt sich eine Typ0-Grammatik G angeben, die ihr Verhalten
simuliert. Das Umgekehrte gilt ebenfalls. In diesem Zusammenhang spricht man auch von
Bisimulation von Typ0-Grammatiken (für allgemeine Regelsprachen) und Turing-Maschinen.
Weil der Satz so wichtig ist, noch eine andere, äquivalente Formulierung: Eine Sprache L f G*
kann genau dann von einer TM T erkannt werden, wenn es eine Grammatik G gibt, die L erzeugt.
Beweis(Idee):
Der formale Beweis ist etwas umständlich und beruht auf Konstruktionen, die, wie im Beispiel
oben angedeutet, eine Simulation des Verhaltens von T durch G zeigen und vice versa.
Ê
130
Nach diesem Ergebnis ist es fast klar, dass man eine Turing-Maschine T auch als einen
Generator für eine Sprache ansehen kann. T “zählt die Wörter der Sprache (rekursiv) auf” (nicht
mit “abzählbar” verwechseln!), wobei wir a priori nicht voraussetzen, dass die Wörter in irgendeiner speziellen Ordnung aufgezählt werden.
Die Herleitung von Wörtern durch eine Grammatik ist i.A. ein nichtdeterministischer Prozess.
Bei der Simulation von Grammatiken durch TM kommt man zunächst auf die nichtdeterministische Variante NTM. Deshalb ist es gut zu wissen, dass, wie schon vorne einmal erwähnt, gilt:
Satz:
Zu jeder Sprache L f G*, die durch eine NTM N erkannt wird, gibt es eine DTM D, die L
erkennt.
Beweis(Idee):
Die vollständige Version des Beweises ist wieder recht länglich. Die Grundidee ist folgende:
δN(q, a) von N hat i.A. mehr als ein Element, sagen wir, maximal k. Jede mögliche Folge von
Zahlen zwischen 1 und k wird zur Konstruktion von D, durch ein geeignetes Symbol von der
eigentlichen Bandeingabe B getrennt, auf das Band in einen Bereich F geschrieben. Dann wird
außerdem B noch einmal, wieder durch ein geeignetes Symbol getrennt, nach dieser Folge von
Zahlenfolgen F auf das Band in einen Bereich K kopiert. δN wird zu einem δD so erweitert, dass
D letztlich N systematisch auf dem Bereich K simuliert. Scheitert der Test für eine Folge fi ε F,
wird die nächste probiert. So kann man alle bereits getesteten Möglichkeiten abhaken und die
restlichen verfolgen. Weil B erhalten bleibt und immer nur auf K gearbeitet wird, kann stets
wieder die Grundsituation hergestellt und mit einem neuen f ein neuer Test gestartet werden.
Ê
131
Document
Kategorie
Seele and Geist
Seitenansichten
13
Dateigröße
230 KB
Tags
1/--Seiten
melden