close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

17 Wie kann man kontextsensitive Sprachen noch cha- rakterisieren ?

EinbettenHerunterladen
17 Wie kann man kontextsensitive Sprachen noch charakterisieren ?
Es fehlen noch einige Anmerkungen zum Pendant der Typ1-Grammatiken. Dies sind die Linear
beschränkten Automaten (LBA). Darunter versteht man nichtdeterministische Turing-Maschinen,
die mit einem Band fester Länge ausgestattet sind. Man kann auch sagen, dass ein LBA eine
NTM mit einseitig - z.B. links - begrenztem Band ist und am rechten “Bandende” steht ein
spezielles Symbol, das weder überschritten noch überschrieben werden darf.
Ein LBA mit Bandlänge n kann nur immer maximal n Symbole auf dem Band haben.
Man definiert die LBA meist so, dass das vorhandene Band vollständig mit der Eingabe ausgefüllt ist. Der LBA darf sich nur in diesem Bereich bewegen und dabei lesen oder schreiben.
Wenn eine TM sich so verhält, dass sie für jede Eingabe nicht den Bandbereich verlässt, auf
dem die Eingabe steht, ist sie demnach ein LBA.
Ohne Beweis, dem üblicherweise wieder eine Art der Bisimulation zwischen Grammatik und
Automat zu Grund liegt, wird behauptet:
Satz:
Zu jedem LBA B gibt es eine Typ1-Grammatik G mit L(B) = L(G) und umgekehrt.
Ê
Der deterministische LBA ist eine DTM. Die wichtige Frage, ob zu einem nichtdeterministischen LBA ein äquivalenter deterministischer existiert, ist offen!
Außerdem ohne Beweis der
Satz;
Die Klasse der Sprachen vom Typ1 ist unter Vereinigung, Konkatenation, Kleeneabschluss,
Komplementbildung und Durchschnitt abgeschlossen.
Ê
141
18 Zusammenfassung Sprachen und Grammatiken
Die Ergebnisse, die wir in den vergangenen Kapiteln erzielt haben, können wir in folgenden
Tabellen zusammentragen:
Beschreibungsmittel / Konzepte
Wie kann man die Sprachklasse beschreiben?
Sprachklasse
Beschreibungsmittel
Typ3
DEA, NEA, DEAg, reguläre Ausdrücke, rechts-/linkslineare Grammatiken
deterministische kontextfreie Sprachen
deterministische Kellerautomaten, LR(k)-Grammatiken
Typ2
(allgemeine) kontextfreie Grammatiken, (nichtdeterministische) Kellerautomaten
Typ1
linear beschränkter Automat
Typ0
Turing-/Register-/Post./...-Maschinen, WHILE, GOTO, λ-Kalkül
Determinismus vs. Nichtdeterminismus
Welche Äquivalenzbeziehungen gelten:
Sprachklasse
deterministisch
nichtdeterministisch
äquivalent ?
Typ3
DEA
NEA
ja
Typ2
DKA
(N)KA
nein
Typ1
DLBA
NLBA
unbekannt
Typ0
DTM
NTM
ja
142
Abschlusseigenschaften
Wie verhalten sich die Sprachklassen bzgl. der Abschlusseigenschaften bei den Mengenoperationen?
Sprachklasse
Durchschnitt
Vereinigung
Komplement
Produkt
Kleene-Abschluss / Stern
Typ3
ja
ja
ja
ja
ja
det. kfr
nein
nein
ja
nein
nein
Typ2
nein
ja
nein
ja
ja
Typ1
ja
ja
ja
ja
ja
Typ0
ja
ja
nein
ja
ja
Aufwand für das Lösen des Wortproblems
Die Frage, ob ein vorgelegtes Wort von einer vorgegebenen Grammatik generiert werden kann,
ist mit folgendem Aufwand entscheidbar:
Sprachklasse
Aufwand
Typ3
lineare Zeit, also O(n)
det. kfr
lineare Zeit, also O(n)
Anmerkung
bei gegebenem DEA !
Typ2
Aufwand O(n3)
Typ1
exponentielle Komplexität, “NP-hart”
Typ0
i.A. unlösbar
bei Grammatik in CNF !
143
Entscheidbarkeit
Hier einige wichtige Problem für die einzelnen Sprachklassen. Dabei geht es immer um die
Fragestellung: Gibt es einen Algorithmus, der das XYZ-Problem für jede Probleminstanz zu
lösen gestattet?
Zur Erinnerung:
Wortproblem:
Gegeben eine Grammatik G und eine Zeichenkette z. Frage: Wird z von
G produziert?
Leerheitsproblem:
Produziert eine gegebene Grammatik überhaupt ein Wort bzw. akzeptiert
ein gegebener Automat wenigstens ein Wort?
Endlichkeitsproblem: Ist die Sprache einer vorgelegten Grammatik bzw. eines Automaten
unendlich?
Schnittproblem:
Generieren zwei Grammatiken ein gleiches Wort bzw. gibt es ein Wort,
das zwei Automaten akzeptieren?
Äquivalenzproblem: Produzieren zwei Grammatiken dieselbe Sprache bzw. akzeptieren zwei
Automaten dieselbe Sprache?
Sprachklasse
Wortproblem
Leerheitsproblem
Endlichkeitsproblem
Schnittproblem
Äquivalenzproblem
Typ3
ja
ja
ja
ja
ja
det kfr
ja
ja
ja
nein
unbekannt
Typ2
ja
ja
ja
nein
nein
Typ1
ja
nein
nein
nein
nein
Typ0
nein
nein
nein
nein
nein
144
19 Wie kann man den Berechnungsbegriff noch charakterisieren ?
Ausgehend vom Begriff “(Formale) Sprache” sind wir zum “Grammatik”-Begriff gekommen,
mit dem wir die Möglichkeit geschaffen haben, die Wörter einer Sprache zu generieren. Als
Pendant zum Grammatik-Begriff führten wir die “Akzeptoren” ein, d.h. die Automaten-Typen,
die die jeweiligen Sprachklassen akzeptieren/erkennen können.
Im Rahmen der Behandlung von Turing-Maschinen sahen wir aber auch, dass das Akzeptieren
der Zeichenketten einer Sprache L f Σ* interpretiert werden kann als “Berechnung” der charakteristischen Funktion von L relativ zu Σ*.
Es wurde bereits erwähnt, dass man die Paare (Eingabe, Ausgabe/Ergebnis) als Sprache
auffassen und wieder die Frage des Akzeptierens dieser Sprache stellen kann. In diesem Zusammenhang spricht man eher von “Entscheiden”. Auf damit verbundene Probleme wird an
späterer Stelle noch genauer eingegangen.
Der Versuch, den intuitiven Berechnungsbegriff oder, gleichbedeutend, den “Algorithmus”Begriff zu präzisieren (und nicht das Akzeptieren von Sprachen), war der historische Ausgangspunkt der Überlegungen zu den TM. Weil sich in der Informatik alles um diese Begriffe dreht,
wollen wir sie im Folgenden durch weitere Konzepte beleuchten, die näher an der Erfahrung und
Sprechweise mit Programmiersprachen liegen, insbesondere durch die LOOP-, WHILE- und
GOTO-Berechenbarkeit. Auch hier wird gelten, dass - bis auf LOOP-Berechenbarkeit - die
Konzepte untereinander und zu den TM mit allen Varianten äquivalent sind.
Sei n, m 0 ù. Eine Turing-Maschine M berechnet eine partielle Funktion f : (G*)n 6 (G*)+ mit
f(α1, α2, ..., αn) = (γ1, γ2, ..., γm), gdw. M nach endlich vielen Schritten anhält, sich dabei in einem
Endzustand befindet und (γ1, γ2, ..., γm) auf dem Band steht. Hält M nicht an für die Eingabe (α1,
α2, ..., αn) oder hält M in einem Nichtendezustand, weil keine Folgekonfiguration mittels δ definiert ist, dann ist f für diese Eingabe undefiniert (deshalb “partiell”).
Sei f eine evtl. partielle Funktion f : (Σ*)n 6 (Σ*)+, also eine Funktion, die an manchen Stellen
nicht definiert sein muss. Genau dann ist f Turing-berechenbar, wenn es eine Turing-Maschine
gibt, die f berechnet.
Ist f total und Turing-berechenbar, dann nennt man f auch total rekursiv oder nur rekursiv. (Das
bedeutet, dass die zugehörige Turing-Maschine bei jeder Eingabe stoppt!)
Wegen der o.a. Äquivalenz können wir die folgenden These aufstellen:
Church/Turing-These:
Die von TM und ihren Varianten bzw. durch WHILE- sowie GOTO-Berechenbarkeit erfasste
Klasse von Funktionen stimmt genau mit der Klasse der Funktionen überein, die im intuitiven
Sinn berechenbar sind.
Ê
145
19.1
LOOP-Berechenbarkeit
Wir beginnen mit der einfachen Programmiersprache LOOP mit folgender Syntax. Zunächst
gibt es
Variablen:
Konstanten:
Trennsymbole:
Operationszeichen:
Schlüsselwörter:
x, y, z, ..., x0, x1, x2, x3, ...
0, 1, 2 , ...
Wertzuweisung := und Anweisungstrennsymbol ;
+, LOOP, DO, END
Wir verzichten auf “syntaktischen Zucker” wie READ und WRITE. Die weitere Syntax wird so
definiert, wobei c eine Konstante ist:
Jede Wertzuweisung
xi := xj + c
und
xi := xj - c
ist ein LOOP-Programm.
Sind P, P1 und P2 LOOP-Programme, dann auch
P1 ; P2
und
LOOP xi DO P END
Die Semantik soll nur informell erklärt werden und ist mit einem programmiersprachlichen
Vorverständnis unmittelbar einsichtig:
Soll ein LOOP-Programm eine k-stellige Funktion berechnen, stehen die k Eingabeparameter
in den Variablen x1, x2, ..., xk. Alle anderen haben den Wert 0. Die Variable x0 ist für das Resultat
reserviert. Die Wertzuweisungen werden wie üblich interpretiert. Die Subtraktion xj - c wird so
modifiziert, dass keine negativen Werte auftreten, also ist xj < c bekommt xi den Wert 0.
P1 ; P2 ist die übliche Hintereinanderausführung.
Die Laufschleife LOOP x DO P END ist so zu interpretieren, dass P genau x-mal ausgeführt
wird, auch wenn ggf. x innerhalb von P verändert wird.
146
Definition:
k 0 ù. Eine Funktion f : ùk 6ù heißt LOOP-berechenbar, wenn es ein LOOP-Programm P so
gibt, dass P, gestartet mit den Variablen x1, x2, ..., xk (und alle anderen gleich 0 gesetzt), stoppt
und f(x1, x2, ..., xk) = x0.
Beispiele:
Addition:
Multiplikation:
Ê
Anmerkungen:
>
Für xi := xj + 0 kann man auch xi := xj schreiben.
>
Für xi := xj + c mit xj = 0 kann man auch xi := c schreiben.
>
Man kann LOOP um den “Makro-Befehl”
IF x = 0 THEN P END
erweitern, denn dazu gleichwertig ist
y := 1;
LOOP x DO y:= 0 END;
LOOP y DO P END
Die Variable y darf sonst im Programm nicht benutzt werden.
>
LOOP-Programme haben keine Endlosschleifen. Sie terminieren immer, sind also total.
>
Die meisten arithmetischen Funktionen sind LOOP-berechenbar.
>
Zu jedem LOOP-Programm gibt es eine äquivalente TM, die dieselbe Funktion berechnet. Das Umgekehrte gilt nicht! Also, es gibt Funktionen, die nicht LOOP-berechenbar sind. Die LOOP-berechenbaren Funktionen sind eine echte Teilmenge der Turingberechenbaren Funktionen
147
Die Ackermann-Funktion (1928) als Beispiel für eine nicht LOOP-berechenbare Funktion:
ack(0, y) = y+1
ack(x, 0) = ack(x-1, 1)
ack(x, y) = ack(x-1, ack(x, y-1))
148
(Diese Seite ist absichtlich leer.)
149
19.2
WHILE-Berechenbarkeit
Die Programmiersprache LOOP wird durch ein Konstrukt WHILE erweitert, das syntaktisch
wie folgt definiert ist und die übliche Semantik besitzt:
WHILE x … 0 DO P END
P wird solange ausgeführt, bis x = 0 ist. Die Variable x darf in P benutzt und insbesondere
verändert werden.
So kommen wir zur Programmiersprache WHILE.
Definition:
Sei k 0 ù. Eine Funktion f : ùk 6ù heißt WHILE-berechenbar, wenn es ein WHILE-Programm
P so gibt, dass P, gestartet mit den Variablen x1, x2, ..., xk (und alle anderen gleich 0 gesetzt),
stoppt und f(x1, x2, ..., xk) = x0.
Ê
Anmerkungen:
>
Die Ackermannfunktion ist WHILE-berechenbar.
>
Weil
y := x;
WHILE y > 0 DO P; y := y - 1; END
äquivalent ist zu
LOOP x DO P END
kann man auf das LOOP-Konstrukt verzichten.
>
Zu jedem WHILE-Programm, das eine Funktion f berechnet, gibt es eine äquivalente TM,
die f berechnet. Das Umgekehrte gilt ebenfalls.
150
19.3
GOTO-Berechenbarkeit
Programme der GOTO-Programmiersprache15 bestehen aus einer Folge von “markierten
Anweisungen”
M1 : A1 ;
M2 : A2 ;
....... ;
Mk : Ak ;
wobei für Ai Folgendes zugelassen ist:
Wertzuweisungen
unbedingte Sprünge
bedingte Sprünge
Stopp-Anweisung
xi := xj + c und xi := xj - c
GOTO Mj mit 1#j#k
IF x = c GOTO Mj mit 1#j#k
HALT
Wenn Marken nie angesprungen werden, kann man sie auch weglassen. Es würde genügen, nur
den Test auf x = 0 zuzulassen.
Die Semantik von GOTO-Programmen ist wie gewohnt definiert.
Durch rückwärts gerichtete Sprünge kann man die WHILE-Anweisung simulieren, was zu tun
normalerweise verpönt ist:
M1 :
M2 :
IF x = 0 THEN GOTO M2 ;
P;
GOTO M1 ;
.....
So ist klar, dass man jedes WHILE-Programm in ein GOTO-Programm überführen kann.
Auch die Umkehrung gilt (wenn auch etwas umständlicher zu beweisen): Jedes GOTOProgramm kann man durch ein WHILE-Programm simulieren. Man kann beweisen (“Kleenesche
Normalform”), dass man jedes Programm so umformen kann, dass nur eine einzige WHILEAnweisung vonnöten ist.
Da die Äquivalenz zwischen Turing-Berechenbarkeit und WHILE-Berechenbarkeit schon
erwähnt wurde, gilt - wie zu erwarten - dass auch GOTO-Berechenbarkeit und Turing-Berechenbarkeit die gleiche Menge von Funktionen umfasst.
15
Zur Zeit der hitzigen Diskussionen in den 1970-ern über Strukturiertes Programmieren hätte man
sie wohl als PFUI-Programmiersprache bezeichnet.
151
(Die Seite ist absichtlich leer.)
152
19.4
Weitere Berechenbarkeit-Kalküle
Die Suche nach einer Formalisierung des Berechenbarkeit/Algorithmus-Begriffs hat noch
weitere Kalküle gebracht, so die
>
primitiv rekursiven Funktionen, die mit der Klasse der LOOP-berechenbaren Funktionen
übereinstimmen
>
µ-rekursiven Funktionen, eine Erweiterung der primitiv rekursiven Funktionen um den
µ-Operator, der ein Pendant zur WHILE-Anweisung ist
>
λ-Kalkül, die Basis der Programmiersprache Lisp
>
Markov-Algorithmen, eine Mischung aus Produktionensystem mit einer Kontrollstruktur,
die festlegt, welche Regel anzuwenden ist.
>
.......
Wieder gilt: Die Klasse der µ-rekursiven Funktionen, der durch den λ-Kalkül beschreibbaren
Funktionen, der WHILE-, GOTO- und Turing-berechenbaren Funktionen sind identisch. Oder
anders ausgedrückt: Eine Funktion ist genau dann µ-rekursiv, wenn sie WHILE-berechenbar oder
Turing-berechenbar oder λ-berechenbar oder GOTO-berechenbar oder Markov-berechenbar oder
... ist.
Wegen der Äquivalenz derartig unterschiedlicher Ansätze ist die Church/Turing-These
gerechtfertigt. Allerdings übertragen sich die “Entscheidbarkeitsprobleme” im einen Kalkül in
analoger Weise auf die anderen.
Es gibt dabei u.a. so hübsche Theoreme wie: Man kann entweder entscheiden (also man kann
ein automatisches Verfahren entwerfen), ob bei einer Programmiersprache P ein vorgegebenes
Programm eine Endlosschleife hat, oder man kann in P den Compiler für P schreiben. Beides
zusammen ist nicht möglich.
153
19.5
Universelle Turing-Maschinen
Bislang hatten wir nur ad-hoc-Turing-Maschinen behandelt, also TM, die genau eine Funktion
ausführen. Ein Computer scheint zunächst mehr zu können, weil er offensichtliche eine beliebige
Funktion f berechnen kann, die durch ein Programm Pf realisiert wird, wobei bei einer Eingabe
x gilt Pf(x) = f(x). Dass es eine TM gibt, die alle Berechnungen durchführen kann, indem sie jede
andere TM zu simulieren vermag, soll im Folgenden gezeigt werden.
Durch Gödelisierung ist es gelungen, die Selbstanwendung von (zahlentheoretischen) Funktionen zu formalisieren. Dies wird verallgemeinert: Eine Funktion U heißt universell für eine
Klasse K von Funktionen, wenn sie als Argumente die Beschreibung F einer Funktion f 0 K
sowie die Eingabewerte x für f nimmt und dann f(x) berechnet, also U(F, x) = f(x). U
interpretiert/simuliert also die Beschreibung F von f zusammen mit einem Argument x und
berechnet das Ergebnis.
Man beachte, dass ein Computer C genau das auch macht: Er nimmt als Eingabe den Programmtext Pf, der die Beschreibung einer zur Diskussion stehenden Funktion f ist, und liefert mit
einer (ebenfalls codierten) Eingabe x das Ergebnis Pf(x) als Ausgabe, also C(Pf, x) = Pf(x). Wenn
man sich überlegt, dass jede Turing-Maschine durch ein Pascal-Programm beschrieben werden
kann, wobei Pascal-Programme nur syntaktische Verbesserungen von WHILE- bzw. GOTOProgrammen sind, ist ein Computer also universell hinsichtlich der Klasse TM aller TuringMaschinen.
Die Überlegungen lassen sich auch auf Turing-Maschinen übertragen: Eine universelle TuringMaschine ist eine Turing-Maschine U, die eine Turing-Maschine T in dem Sinne simuliert, dass
U auf ihrem Eingabeband eine Beschreibung von T (zur Not die Gödelnummer G(T), vereinfacht
gesagt) und ein (für T gedachtes) Eingebewort σ (ggf. auch G(σ)) nimmt. Dabei wird σ so
verändert, wie es T tun würde, also
U(G(T), G(σ)) = T(σ)
Man muss nicht das bisherige Gödelisierungsverfahren G verwenden, um zu zeigen, dass U
existiert. Wie schon an anderer Stelle gesagt, kann man eine TM T “normieren”, z.B. hinsichtlich
der Zahl der Endzustände. So kann man T schließlich geeignet (über dem Binäralphabet)
codieren, wobei folgende Überlegungen hilfreich sind:
Zu T existiert eine TM mit nur einem Endzustand.
Die Zustände von T kann man durch (Binär-)Zahlen repräsentieren, wo z.B. immer der
Startzustand die erste Position und der Endzustand die zweite Position in einer Aufzählung hat. Ein Zustand zi lässt sich z.B. durch 0i repräsentieren, das Bandalphabet analog,
so dass die Anweisung δ(zi, xj) = (zk, xm, bn) des Programms von T etwa durch
0i10j10k10m10n1 dargestellt werden kann. Die 1 dient als Trenner.
Auf diese Weise ergibt sich eine Binärfolge c(T) als Codierung von T, wobei die Reihenfolge
für die Einzelbefehle keine Rolle spielt. Insofern gibt es mehr als eine Darstellung für T. Als
154
Binärzahl interpretiert, kann man immer die Codierung nehmen, die die kleinste Zahl darstellt.
Klar, zu jeder TM gibt es eine Binärdarstellung, aber nicht jede Binärfolge stellt eine TM dar.
Die Funktion δU von U muss jetzt “nur” so gewählt werden, dass sie jedes δ simuliert.
Der technisch verwickelte Beweis lässt sich etwas vereinfachen, wenn man U als 3-Band-TM
U konzipiert. Auf dem ersten Band steht die Codierung c(T) von T und zunächst auch das
Eingabewort w (auch codiert). Dann kopiert man w auf das zweite Band und löscht es auf dem
ersten. Also steht auf dem ersten Band immer das zu simulierende Programm c(δT) zur Interpretation zur Verfügung und das zweite ist das eigentliche Arbeitsband. Auf dem dritten Band
schreibt U den Zustand, in dem sich aktuell T während der Simulation durch U befinden würde.
Am Anfang der Simulation ist es z1 in Form von 0.
Die Ausführung eines Simulationsschritts funktioniert so: Angenommen, T hätte den Schritt
δ(zi, xj) = (zk, xm, bn) auszuführen und der Lese/Schreibkopf befände sich auf dem Zeichen xj. Auf
Band 3 von U steht bei der Simulation zi (in Form von 0i) und der Lese/Schreibkopf von U steht
auf Band 2 auf der ersten 0 der Codierung von xj. (Durch Investition von einigen weiteren
Zuständen kann U die Binärfolge als die Codierung von xj erkennen.) Dann sucht U auf dem
Band 1 den zugehörigen Binärblock c(δ(zi, xj)). Gibt es keinen, hält U an, allerdings ohne im
Endzustand zu sein. Wird c(δ(zi, xj)) = 0i10j1gefunden, wird das Analogon zu (zk, xm, bn) ausgeführt, also Band 2 verändert und der neue Zustand auf Band 3 geschrieben. U simuliert genau
das, was T gemacht hätte.
Bleibt noch eine Bemerkung zur “Übersetzung” Ü des Programms von T in eine Binärfolge.
Dass die Funktion Ü(T) = c(T) berechenbar ist und dazu unschwer eine TM TÜ angegeben
werden kann, ist klar. Die Funktion Ü ist somit ein Compiler für ein beliebiges TM-Programm
PT, damit es auf der universellen TM ausgeführt werden kann.
Mit der obigen Konstruktion wurde gezeigt, dass eine TM U existiert, so dass
U(G(T), G(σ)) = T(σ)
Diese Tatsache wird manchmal auch als utm-Theorem bezeichnet. Die Existenz von Ü nennt man
Übersetzungslemma. Das Übersetzungslemma garantiert u.a., dass man Programme einer (universellen) Programmiersprache P in äquivalente Programme einer Programmiersprache P’
übersetzen kann.
155
Document
Kategorie
Bildung
Seitenansichten
8
Dateigröße
188 KB
Tags
1/--Seiten
melden