Kellerautomaten und Turingmaschinen

Klaus Becker

2010

2 Kellerautomat und Turingmaschine

3 Teil 1

Erkennen von Klammersprachen

4 Klammersprachen

12+5

23*(57+18)

3+5*(7+4)

((2+6)+5)*(7+4)

...

MarkeSetzenSchrittSOLANGE NichtIstMarke TUE SOLANGE NichtIstWand TUE Schritt *SOLANGE LinksDrehen*SOLANGE

<?xml version="1.0" encoding="iso-8859-1"?><Buch><Autor><Name>Borik</Name> <Vorname>Otto</Vorname><Hrsg/></Autor><Titel>Meyers Schachlexikon</Titel><Verlag>Meyers Lexikonverlag</Verlag> <Erscheinungsort>Mannheim</Erscheinungsort> <Erscheinungsjahr>1993</Erscheinungsjahr> <ISBN>3-411-08811-7</ISBN></Buch>

Der Hund, der die Katze, die eine Maus, die gerade ein Stück Käse, das gestern, als das Fußballspiel, das im Fernsehen gezeigt wurde, gerade zu Ende war, weggeworfen wurde, anbeißt, jagt, anbellt, heißt Bello.

5 Beispiel: Rechenausdrücke

Rechenausdrücke sind Ausdrücke, in denen Zahlen, Rechenzeichen und Klammern vokommen können. Sie begegnen uns überall, wo kompliziertere Rechnungen dargestellt werden müssen.

12+5

23*(57+18)

3+5*(7+4)

((2+6)+5)*(7+4)

...

z+z

z*(z+z)

z+z*(z+z)

((z+z)+z)*(z+z)

...

Im folgenden wollen wir uns auf die Klammer- und Rechenstruktur solcher Rechenausdrücke konzentrieren. Die Zahlen soll nur eine untergeordnete Rolle spielen. Wir ersetzen daher jede Zahl durch das Symbol "z". Zusätzlich betrachten wir der Einfachheit halber nur Rechenausdrücke mit den Rechenzeichen + und *. Entscheidend für die so vereinfachten Rechenausdrücke ist die korrekte Klammerung: Zu jeder öffnenden Klammer muss es - an passender Stelle - eine schließende Klammer geben.

6 Beispiel: Rechenausdrücke

Die Sprache LRA der vereinfachten Rechenausdrücke soll genau solche Klammer- und Rechenstrukturen beschreiben. Sie basiert auf dem Alphabet Σ = {z, +, *, (, )}. Präzise beschreiben kann man sie mit der folgenden Grammatik:

A -> A + S

A -> S

S -> S * F

S -> F

F -> ( A )

F -> z

Aufgabe:

Zeige mit Hilfe einer Ableitung, dass das Wort z*(z+z) (einfach) bzw. das Wort z+z*(z+z) (schwieriger) mit Hilfe der Grammatik erzeugt werden kann.

7 Beispiel: Programmiersprachen

Als Beispiel für eine sehr einfache Programmiersprache betrachten wir die Sprache, mit der man den Roboter Karol steuern kann.

Auch hier kommen Klammerstrukturen vor. Bei einer Solange-Anweisung werden Beginn und Ende mit den Schlüsselwörtern SOLANGE und *SOLANGE gekennzeichnet.

8 Beispiel: Programmiersprachen

Wir wollen Karol-Programme vereinfacht darstellen. Mit dem Symbol e soll eine elementare Anweisung beschrieben werden, mit dem Symbol b eine Bedingung. Mit den Symbolen s und * sollen Beginn und Ende einer SOLANGE-Anweisung gekennzeichnet werden.

MarkeSetzenSchrittSOLANGE NichtIstMarke TUE SOLANGE NichtIstWand TUE Schritt *SOLANGE LinksDrehen*SOLANGE

Aufgabe:

Entwickle eine Grammatik für die Sprache LRP der vereinfachten Roboterprogramme. Du kannst sie auch selbstständig um Symbole zur Kennzeichnung von Fallunterscheidungen erweitern.

ees b s b e * e*

eesbsbe*e*

9 Beispiel: XML

XML benutzt sogenannte Tags zur Informationsbeschreibung. Anfangs- und Endtags bilden dabei jeweils Klammerpaare.

XML erlaubt es dem Benutzer, solche Klammerpaare selbst festzulegen und somit flexibel komplexe Klammerstrukturen zu entwickeln.

<?xml version="1.0" encoding="iso-8859-1"?><Buch><Autor><Name>Borik</Name> <Vorname>Otto</Vorname><Hrsg/></Autor><Titel>Meyers Schachlexikon</Titel><Verlag>Meyers Lexikonverlag</Verlag> <Erscheinungsort>Mannheim</Erscheinungsort> <Erscheinungsjahr>1993</Erscheinungsjahr> <ISBN>3-411-08811-7</ISBN></Buch>

10 Beispiel: XML

Die Sprache LMyXML soll vereinfachte XML-artige Ausdrücke beschreiben. Jedes zu dieser Sprache gehörende Wort soll aus einem Anfangstag, einem Text und einem Endtag bestehen. Anfangs- und Endtag sollen im Wesentlichen identisch sein. Die Tag-Bezeichner sind beliebige nicht-leere Zeichenketten, die nur aus den Buchstaben a und b bestehen. Der Text zwischen den Anfangs- und End-Tag soll nur aus den Buchstaben a, b und c bestehen. Zur Sprache LMyXML gehört beispielsweise das Wort <ab>acaa</ab>.

Aufgabe:

Die Sprache LMyXML kann mit der gezeigten Grammatik beschrieben werden. Erstelle eine Ableitung des Worts <ab>acaa</ab>.

S -> <aAT>S -> <bBT>T -> aATT -> bBTT -> MAa -> aAAb -> bAAM -> MaBa -> aBBb -> bBBM -> MbM -> >NN -> aNN -> bNN -> cNN -> </

11 Grenzen von endlichen Automaten

Problem: Kann man Klammersprachen mit endlichen Automaten erkennen?

A

ok(((())))

Fehler((())

Wir betrachten hier korrekte Klammerausdrücke der Gestalt (((...))), die nach einer Anzahl öffnender Klammern genauso viele schließende Klammern haben. So ist (()) ein korrekter Klammerausdruck, während die Ausdrücke (() und (()))) keine korrekten Klammerausdrücke in unserem Sinne sind.

Versuche, einen endlichen Automaten A zur Erkennung solcher Klammerausdrücke zu konstruieren, scheitern an der Schwierigkeit, die Anzahl der öffnenden Klammern im Automaten mitzuzählen. Es scheint, dass diese Schwierigkeit bei endlichen Automaten - die ja eine feste Anzahl von Zuständen haben - unüberwindbar ist. Die folgenden Argumentationen zeigen, dass das tatsächlich der Fall ist.

aaaabbbb

aaabb

12 Grenzen von endlichen Automaten

Gibt es einen endlichen Automaten, der L = {anbn | n = 1, 2, 3, ...} erkennt?

DFA

ok(((())))

Fehler((())

Angenommen, es gibt einen endlichen Automaten A mit L(A) = L. Dieser Automat A hat eine feste Anzahl Zustände, etwa m = 15 (die Zahl 15 ist hier willkürlich gewählt, sie spielt für die Argumentation keine Rolle).

Wie wählen nun ein Wort w = akbk aus L = {anbn | n = 1, 2, 3, ...} aus mit k > m, etwa k = 16. Bei der Abarbeitung des Wortes w = akbk muss bereits bei der Verarbeitung der 16 a's mindestens ein Zustand z mindestens zweimal durchlaufen werden, denn es gibt mehr a's als Zustände.

Wir nehmen einmal an, dass der Zustand z mit dem dritten a und mit dem siebten a erreicht wird. Für die folgende Argumentation ist nicht entscheidend, mit welchen a's man z erreicht, sondern nur, dass z zweimal durchlaufen wird.

Es entsteht eine Schleife, die erst mit dem ersten b wieder verlassen wird. Wie die 16 b's den Automaten in einen Endzustand bringen, ist für die Argumentation ohne Belang.

aaaabbbb

aaabb

13 Grenzen von endlichen Automaten

Die folgende Grafik soll die Situation verdeutlichen:- A hat m Zustände (hier m = 15).- A akzeptiert w = akbk mit k > m (hier w = a16b16).- Bei der Verarbeitung des a-Anfangsteils von w wird ein Zustand mindestens zweimal durchlaufen werden (hier wird q3 insgesamt 4 mal durchlaufen).

Weitere spezielle Eigenschaften von A, die in der Grafik zu erkennen sind, sind für den Beweisgang nicht von Bedeutung.

Grafik entnommen aus: http://hsg.region-kaiserslautern.de/faecher/inf/material/automaten/anbn/index.php

14 Grenzen von endlichen Automaten

Dem Bild kann man direkt entnehmen, dass neben w = a16b16 auch andere Wörter wie a4b16 (Schleife wurde nicht durchlaufen) oder auch a8b16 (Schleife wurde einmal durchlaufen) akzeptiert werden.

Der Automat akzeptiert folglich auch Wörter, die nicht zu L = {anbn | n = 1, 2, 3, ...} gehören. Das steht aber im Widerspruch zur Annahme, dass der Automat A die Sprache L = {anbn | n = 1, 2, 3, ...} erkennt.

Da die Annahme, dass es einen endlichen Automaten gibt, der die Sprache L = {anbn | n = 1, 2, 3, ...} erkennt, zu einem Widerspruch führt, muss die Annahme falsch sein. Satz (über die Grenzen von endlichen Automaten):

Die Sprache L = {anbn | n = 1, 2, 3, ...} kann nicht von einem endlichen Automaten erkannt werden. Sie ist also nicht regulär.

15 Erweitertes Automatenmodell

Wir betrachten hier korrekte Klammerausdrücke der Gestalt (((...))), die nach einer Anzahl öffnender Klammern genauso viele schließende Klammern haben. So ist (()) ein korrekter Klammerausdruck, während die Ausdrücke (() und (()))) keine korrekten Klammerausdrücke in unserem Sinne sind.

Kellerautomat / Stapelautomat

16 Erweitertes Automatenmodell

Aufgabe

Erstelle mit JFlap den abgebildeten erweiterten Automaten (mit [File][New][Pushdown Automaton]). Teste mit [Input][Step by State] die Arbeitsweise des erweiterten Automaten.

17 Kellerautomat

Der Kellerautomat hat eine nichtleere endliche Menge Z von Zuständen. Im vorliegenden Fall ist das die Menge Z = {q0, q1, q2}. Der Zustand q0 ist hier als Anfangszustand ausgezeichnet, der Zustand q2 als ein Endzustand.

Eingabe

zu entfernende

oberste Kellersymbole

hinzuzufügende oberste

Kellersymbole

Eine Verarbeitung wird durch einen Zustandsübergang (von einem Zustand in einen anderen, gegebenenfalls denselben Zustand) beschrieben. Ein Zustandsübergang erfolgt nur in Abhängigkeit von einem Eingabesymbol und den obersten Kellersymbolen. Ein Zustandsübergang aktualisiert zudem den Keller, indem Symbole vom Keller entfernt und neue Symbole im Keller abgelegt werden.

18 Fachkonzept - Kellerautomat

Ein (deterministischer) Kellerautomat ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:

e. nichtleere, endl. Menge von Zuständen

eine nichtleere, endliche Menge von Eingabesymbolen

eine nichtleere, endliche Menge von Kellersymbolen,

eine Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit von einer vorgegebener Eingabe und einer Folge von Kellersymbolen die Folgezustände zuordnet und zudem die jeweils neu im Keller aufzunehmenden Symbole festlegt,

ein ausgezeichneter Zustand - dem Anfangszustand -,

eine Menge von Endzuständen

ein ausgezeichnetes Kellersymbol, das die untere Kellerbegrenzung beschreibt.

Bei einem nichtdeterministischen Kellerautomaten müssen die Zustandsübergänge nicht eindeutig sein. Zudem sind λ-Übergänge möglich.

19 Fachkonzept - Kellerautomat

Die Menge der Eingabesymbole eines Kellerautomaten kann als Alphabet einer Sprache aufgefasst werden.

Unter der Sprache eines Kellerautomaten versteht man die Menge aller Wörter aus Eingabesymbolen, die den Kellerautomaten vom Anfangszustand in einen Endzustand überführen.

Wenn K ein gegebener Kellerautomat ist, dann schreiben wir L(K) für die Sprache des Kellerautomaten K.

= {(, )}

L(A) = {(), (()), ((())), ...}

20 Fachkonzept - Kellerautomat

Ein Kellerautomat ist also eine Verarbeitungseinheit, die Symbole eines Eingabeworts verarbeitet, sich dabei stets in einem bestimmten Zustand befindet und die zum Zwischenspeichern von Symbolen einen Stapel / Keller benutzt.

21 Übungen

Im Folgenden sollen etwas verallgemeinerte Klammerausdrücke betrachtet werden:

()(), (()(())), ()(())(()()), ...

bzw. in abstrahierter Form:

abab, aabaabbb, abaabbaababb, ...

(a) Beschreibe diese verallgemeinerten Klammerausdrücke mit einer Grammatik.

(b) Entwickle einen Kellerautomaten, der die Sprache der verallgemeinerten Klammerausdrücke erkennt.

22 Übungen

Entwickle einen Kellerautomaten, der die Sprache der vereinfachten Rechenausdrücke / vereinfachten Karol-Programme erkennt.

z+z

z*(z+z)

z+z*(z+z)

((z+z)+z)*(z+z)

...

eesbsbe*e*

23 Teil 2

Kellerautomaten und kontextfreie Sprachen

24 JFlap: Grammatik -> Kellerautomat

Wir betrachten eine Grammatik für die Sprache Lab = {anbn | n = 1, 2, 3, ...} der Klammerausdrücke.

Aufgabe: Analysiere den Zusammenhang zwischen der vorgegebenen Grammatik und dem erzeugten Kellerautomaten. Analysiere auch, was sich im Keller des Kellerautomaten abspielt, wenn ein Eingabewort verarbeitet wird. Der aus der Grammatik erzeugte Kellerautomat ist nichtdeterministisch. Woran erkennt man das?

25 JFlap: Kellerautomat -> Grammatik

Wir betrachten einen Kellerautomaten zur Erkennung der Sprache Lab = {anbn | n = 1, 2, 3, ...} der Klammerausdrücke.

26 JFlap: Kellerautomat -> Grammatik

Wir ändern den Kellerautomaten geringfügig ab, so dass die Fehlermeldung "Transitions must pop 1 and push 0 or 2" nicht mehr auftritt.

27 JFlap: Kellerautomat -> Grammatik

JFlap erzeugt aus dem Kellerautomaten eine komplizierte Grammatik.

28 JFlap: Kellerautomat -> Grammatik

JFlap vereinfacht die erzeugte Grammatik.

29 Kontextfreie Grammatiken

S -> LDA -> aB -> bL -> FBD -> λF -> ALF -> λ

Zum Kellerautomaten K lässt sich die Grammatik GK erzeugen. Es fällt auf, dass alle Produktionen dieser Grammatik GK eine bestimmte Struktur haben.

Nichtterminalsymbol

Wort bestehend aus Terminal- und

Nichtterminalsymbolen

30 Fachkonzept - kontextfreie Sprache

Eine Produktion u -> v heißt kontextfrei genau dann, wenn gilt: Die linke Seite u der Produktion ist ein Nichtterminalsymbol. Die rechte Seite v der Produktion ist ein beliebiges Wort (also auch das leere Wort) bestehend aus Terminal- und Nichtterminalsymbolen.Eine Grammatik heißt kontextfrei genau dann, wenn alle Produktionen der Grammatik regulär sind.

Eine Sprache heißt kontextfrei genau dann, wenn es eine reguläre Grammatik gibt, die diese Sprache erzeugt.

A -> A+SA -> SS -> S*FS -> FF -> (A)F -> z

S -> <aAT>S -> <bBT>T -> aATT -> bBTT -> MAa -> aAAb -> bAAM -> MaBa -> aBBb -> bBBM -> MbM -> >NN -> aNN -> bNN -> cNN -> </

kontextfreie Grammatik für LRA

nicht-kontextfreie Grammatik für LMyXML

Um nachzuweisen, dass eine Sprache kontextfrei ist, reicht es aus, eine reguläre Grammatik zur Sprache zu konstruieren. Auch wenn man noch keine kontextfreie Grammatik zu einer Sprache gefunden hat, so heißt das noch nicht, dass die Sprache nicht-kontextfrei ist.

31 Theorie - kontextfreie Sprachen

Satz (Zusammenhang zwischen kontextfreien Sprachen und Kellerautomaten):

Zu jeder kontextfreien Sprache gibt es einen nichtdeterministischen Kellerautomaten, der diese Sprache erkennt. Der Kellerautomat kann automatisiert aus einer kontextfreien Grammatik zur kontextfreien Sprache erzeugt werden.

S -> aSbS -> λ

32 Theorie - kontextfreie Sprachen

S -> aSbS -> λ

S -> aSb-> aaSbb-> aabb

Zustand; Kellerinhalt Eingabewort------------------------------------------------q0; Z aabb| λ,Z;SZq1; SZ aabb| λ,S;aSbq1; aSbZ aabb| a,λ;aq1; SbZ abb| λ,S;aSbq1; aSbbZ abb| a,λ;aq1; SbbZ bb| λ,S;λq1; bbZ bb| b,λ;bq1; bZ b| b,λ;bq1; Z| λ,Z;λq2

Beachte, dass alle Produktionen der Grammatik in den Zustandsübergängen des Kellerautomaten kodiert sind. Der Kellerauromat ist so konstruiert, dass jede Ableitung mit Produktionen der Grammatik G mit Hilfe von Zustansübergängen des Kellerautomaten simuliert werden kann.

Ableitung mit der Grammatik

Zustandsübergänge beim Kellerautomaten

33 Theorie: kontextfreie Sprachen

Satz (Zusammenhang zwischen Kellerautomaten und kontextfreien Sprachen):

Die Sprache eines nichtdeterministischen Kellerautomaten ist kontextfrei: Zum nichtdeterministischen Kellerautomaten gibt es eine kontextfreie Grammatik, die dieselbe Sprache erzeugt, die vom Kellerautomaten erkannt wird. Man kann diese kontextfreie Grammatik automatisiert erzeugen.

S -> LDA -> aB -> bL -> FBD -> λF -> ALL -> λ

34

nicht-/deterministische Kellerautomaten

Nichtdeterministische Kellerautomaten sind mächtiger als deterministische Kellerautomaten. Es gibt kontextfreie Sprachen, die zwar von nichtdeterministischen, nicht jedoch von deterministischen Kellerautomaten erkannt werden.

S -> 0S0S -> 1S1S -> λ

35 Teil 3

Exkurs: Shift-Reduce-Parser

36

Kellerautomat für eine Rechtsableitung

Wir betrachten die Sprache LRA der vereinfachten Rechenausdrücke mit der Grammatik G .

37 Rechtsableitung eines Wortes

A reduce by A -> A+S

-> A+S reduce by S -> S*F

-> A+S*F reduce by F -> (A)

-> A+S*(A) reduce by A -> A+S

-> A+S*(A+S) reduce by S -> F

-> A+S*(A+F) reduce by F -> z

-> A+S*(A+z) reduce by A -> S

-> A+S*(S+z) reduce by S -> F

-> A+S*(F+z) reduce by F -> z

-> A+S*(z+z) reduce by S -> F

-> A+F*(z+z) reduce by F -> z

-> A+z*(z+z) reduce by A -> S

-> S+z*(z+z) reduce by S -> F

-> F+z*(z+z) reduce by F -> z

-> z+z*(z+z)

Die gezeigte Ableitung ist eine sogenannte Rechtsableitung. In jedem Ableitungsschritt wird das am weitesten rechts stehende Nichtterminalsymbol mit einer Regel aus G ersetzt.

A -> A+SA -> SS -> S*FS -> FF -> (A)F -> z

38

Simulation mit einem Kellerautomaten

Kellerinhalt Eingabewort Aktion---------------------------------------------------------------------------Z z+z*(z+z)$ shift zzZ +z*(z+z)$ reduce by F -> zFZ +z*(z+z)$ reduce by S -> FSZ +z*(z+z)$ reduce by A -> SAZ +z*(z+z)$ shift ++AZ z*(z+z)$ shift zz+AZ *(z+z)$ reduce by F -> zF+AZ *(z+z)$ reduce by S -> FS+AZ *(z+z)$ shift * *S+AZ (z+z)$ shift ((*S+AZ z+z)$ shift zz(*S+AZ +z)$ reduce by F -> zF(*S+AZ +z)$ reduce by S -> FS(*S+AZ +z)$ reduce by A -> SA(*S+AZ +z)$ shift ++A(*S+AZ z)$ shift zz+A(*S+AZ )$ reduce by F -> zF+A(*S+AZ )$ reduce by S -> FS+A(*S+AZ )$ reduce by A -> A+SA(*S+AZ )$ shift ))A(*S+AZ $ reduce by F -> (A)F*S+AZ $ reduce by S -> S*FS+AZ $ reduce by A -> A+SAZ $

A reduce by A -> A+S

-> A+S reduce by S -> S*F

-> A+S*F reduce by F -> (A)

-> A+S*(A) reduce by A -> A+S

-> A+S*(A+S) reduce by S -> F

-> A+S*(A+F) reduce by F -> z

-> A+S*(A+z) reduce by A -> S

-> A+S*(S+z) reduce by S -> F

-> A+S*(F+z) reduce by F -> z

-> A+S*(z+z) reduce by S -> F

-> A+F*(z+z) reduce by F -> z

-> A+z*(z+z) reduce by A -> S

-> S+z*(z+z) reduce by S -> F

-> F+z*(z+z) reduce by F -> z

-> z+z*(z+z)

39

Simulation mit einem Kellerautomaten

Kellerinhalt Eingabewort Aktion---------------------------------------------------------------------------Z z+z*(z+z)$ shift zzZ +z*(z+z)$ reduce by F -> zFZ +z*(z+z)$ reduce by S -> FSZ +z*(z+z)$ reduce by A -> SAZ +z*(z+z)$ shift ++AZ z*(z+z)$ shift zz+AZ *(z+z)$ reduce by F -> zF+AZ *(z+z)$ reduce by S -> FS+AZ *(z+z)$ shift * *S+AZ (z+z)$ shift ((*S+AZ z+z)$ shift zz(*S+AZ +z)$ reduce by F -> zF(*S+AZ +z)$ reduce by S -> FS(*S+AZ +z)$ reduce by A -> SA(*S+AZ +z)$ shift ++A(*S+AZ z)$ shift zz+A(*S+AZ )$ reduce by F -> zF+A(*S+AZ )$ reduce by S -> FS+A(*S+AZ )$ reduce by A -> A+SA(*S+AZ )$ shift ))A(*S+AZ $ reduce by F -> (A)F*S+AZ $ reduce by S -> S*FS+AZ $ reduce by A -> A+SAZ $

A -> A+SA -> SS -> S*FS -> FF -> (A)F -> z

reduce-Aktionen

shift-Aktionen

Der Keller ist zu Beginn leer. Nach und nach werden mit sogenannten shift-Aktionen Symbole des Eingabeworts im Keller abgelegt. Wenn möglich, wird dann mit einer sogenannten reduce-Aktion eine Produktion rückwärts angewandt.

40

Praxistauglichkeit des Kellerautomaten

Als nachteilig erweisen sich beim gezeigten Kellerautomaten die vielen nichtdeterministischen Zustandsübergänge. Wenn man mit [Input][Step by State] ein Eingabewort wie z.B. z+z*(z+z) schrittweise analysiert, dann ergibt sich schnell eine Vielzahl von möglichen Ableitungen.

41 Steuerung mit einer ParsingtabelleKellerinhalt Eingabewort Aktion---------------------------------------------------------------------------Z z+z*(z+z)$ shift zzZ +z*(z+z)$ reduce by F -> zFZ +z*(z+z)$ reduce by S -> FSZ +z*(z+z)$ reduce by A -> SAZ +z*(z+z)$ shift ++AZ z*(z+z)$ shift zz+AZ *(z+z)$ reduce by F -> zF+AZ *(z+z)$ reduce by S -> FS+AZ *(z+z)$ shift * *S+AZ (z+z)$ shift ((*S+AZ z+z)$ shift zz(*S+AZ +z)$ reduce by F -> zF(*S+AZ +z)$ reduce by S -> FS(*S+AZ +z)$ reduce by A -> SA(*S+AZ +z)$ shift ++A(*S+AZ z)$ shift zz+A(*S+AZ )$ reduce by F -> zF+A(*S+AZ )$ reduce by S -> FS+A(*S+AZ )$ reduce by A -> A+SA(*S+AZ )$ shift ))A(*S+AZ $ reduce by F -> (A)F*S+AZ $ reduce by S -> S*FS+AZ $ reduce by A -> A+SAZ $

Kellerinhalt; Eingabewort Aktion-----------------------------------------------------------------------0; z+z*(z+z)$| s5 shift z5z0; +z*(z+z)$| r6 reduce by F->z3F0; +z*(z+z)$| r4 reduce by S->F4S0; +z*(z+z)$| r2 reduce by A->S2A0; +z*(z+z)$| s7 shift +7+2A0 z*(z+z)$| s5 shift z5z7+2A0 *(z+z)$| r6 reduce by F->z3F7+2A0 *(z+z)$| r4 reduce by S->F10S7+2A0 *(z+z)$| s8 shift *8*10S7+2A0 (z+z)$| s1 shift (1(8*10S7+2A0 z+z)$...8*10S7+2A0 $| r3 reduce by S->S*F10S7+2A0 $| r1 reduce by A->A+S2A0 $| acc acceptA0 $

Die Aktionen des Kellerautomaten werden mit einer sog. Parsingtabelle gesteuert.

42 Steuerung mit einer ParsingtabelleKellerinhalt; Eingabewort Aktion-----------------------------------------------------------------------0; z+z*(z+z)$| s5 shift z5z0; +z*(z+z)$| r6 reduce by F->z3F0; +z*(z+z)$| r4 reduce by S->F4S0; +z*(z+z)$| r2 reduce by A->S2A0; +z*(z+z)$| s7 shift +7+2A0 z*(z+z)$| s5 shift z5z7+2A0 *(z+z)$| r6 reduce by F->z3F7+2A0 *(z+z)$| r4 reduce by S->F10S7+2A0 *(z+z)$| s8 shift *8*10S7+2A0 (z+z)$| s1 shift (1(8*10S7+2A0 z+z)$...8*10S7+2A0 $| r3 reduce by S->S*F10S7+2A0 $| r1 reduce by A->A+S2A0 $| acc acceptA0 $

ALGORITHMUS shift-reduce-Analyse:lege 0 im Stapel abWIEDERHOLE zustand = oberstes Symbol im Stapel lookahead = erstes Zeichen im aktuellen Eingabewort aktion = Eintrag in der Parsingtabelle zum Paar (zustand, lookahead) FALLS aktion == shift i (kurz: si): entferne das erste Zeichen des Eingabeworts und ... ... lege es im Stapel ab lege i im Stapel ab FALLS aktion == reduce i (kurz: ri): entferne doppelt so viele Symbole vom Stapel, ... ... wie Symbole auf der rechten Seite von Produktion i stehen zustand = oberstes Symbol vom Stapel symbol = linke Seite von Produktion i zustand = Eintrag i. d. Parsingtabelle zum Paar (zustand, symbol) lege symbol im Stapel ab lege zustand im Stapel abBIS aktion == acc oder aktion == rej (bzw. leerer Eintrag)

43 Erzeugung einer Parsingtabelle

JFlap erzeugt zu (geeigneten) kontextfreien Grammatiken eine passende Parsingtabelle.

44 Erkennung kontextfreier Sprachen

Viele Sprachen, die in der Praxis genutzt werden, können durch kontextfreie Grammatiken beschrieben werden. Automatisiert erzeugte Kellerautomaten zur Erkennung solcher Sprachen sind meist nichtdeterministisch und daher zum praktischen Einsatz wenig geeignet.

Zum Erkennen kontextfreier Sprachen nutzt man in der Praxis Shift-Reduce-Parser mit geeigneten Parsingtabellen. Solche Shift-Reduce-Parser benutzen - genau wie Kellerautomaten - einen Keller / Stapel zum Zwischenspeichern von Symbolen. Anders als Kellerautomaten nutzen sie aber eine Art Vorschau auf das nächste zu verarbeitende Eingabesymbol.

Shift-Reduce-Parser arbeiten deterministisch, d.h. sie können Wortprobleme direkt - ohne Ausprobieren mehrerer Möglichkeiten - lösen. Man kann jedoch nicht zu jeder kontextfreien Grammatik einen passenden Shift-Reduce-Parser automatisiert erzeugen. Nur wenn die Grammatik eine bestimmte Gestalt hat, ist eine automatisierte Erzeugung möglich.

Verfahren zur Erzeugung von Shift-Reduce-Parsern sind komplex und werden daher hier nicht behandelt.

45 Teil 4

Turingmaschinen

46 Vereinfachte XML-Ausdrücke

Die Sprache LMyXML soll vereinfachte XML-artige Ausdrücke beschreiben. Jedes zu dieser Sprache gehörende Wort soll aus einem Anfangstag, einem Text und einem Endtag bestehen. Anfangs- und Endtag sollen im Wesentlichen identisch sein. Die Tag-Bezeichner sind beliebige nicht-leere Zeichenketten, die nur aus den Buchstaben a und b bestehen. Der Text zwischen den Anfangs- und End-Tag soll nur aus den Buchstaben a, b und c bestehen. Zur Sprache LMyXML gehört beispielsweise das Wort <ab>acaa</ab>. S -> <aAT>S -> <bBT>T -> aATT -> bBTT -> MAa -> aAAb -> bAAM -> MaBa -> aBBb -> bBBM -> MbM -> >NM -> aMM -> bMM -> cMM -> </

47 Grenzen von Kellerautomaten

Problem: Kann man die Sprache LMyXML mit Kellerautomaten erkennen?

K

ok<ab>acaa</ab>

Fehler<ab>acaa</ba>

Man kann zeigen, dass die Sprache LMyXML nicht von einem (noch so komplizierten) Kellerautomaten erkannt werden kann.

48

Ein mächtigere Verarbeitungsmodell

49

Ein mächtigere Verarbeitungsmodell

Aufgabe:Teste das Verhalten des gezeigten verallgemeinerten Automaten. Mit [Input][Step...] kannst du Eingabewörter wie z.B. <ab>acaa</ab> eingeben, mit [Step] den Automaten dann schrittweise das Eingabewort verarbeiten lassen. Vergleiche das neue Verarbeitungsmodell - man nennt es Turingmaschine - mit einem endlichen Automaten. Was ist bei einer Turingmaschine anders als bei einem endlichen Automaten?Versuche auch, die Idee der gezeigten Turingmaschine zur Erkennung von Wörtern der Sprache LMyXML herauszufinden. Teste hierzu verschiedene, zur Sprache gehörende und auch nicht gehörende Wörter über dem Alphabet {a, b, c, <, >}. Beschreibe die Verarbeitung in eigenen Worten.

50 Turingmaschine

Die gezeigte Verarbeitungseinheit befindet sich stets in einem bestimmten Zustand. Sie verfügt über ein nach rechts und links unbegrenztes Band, auf dem sich zu Beginn das Eingabewort befindet. Die einzelnen Zellen des Bandes können mit einem Lese-/Schreibkopf angesteuert werden. Der Lese-Schreibkopf kann sich jeweils einen Schritt nach rechts und nach links bewegen (oder auch stehen bleiben). Er kann den Inhalt einer Zelle lesen und auch Symbole in Zellen schreiben.

geschriebene Bandsymbol

Bewegung des Lese-/Schreib-

Kopfes

gelesene Bandsymbol

51 Fachkonzept - Turingmaschine

Eine (deterministische) Turingmaschineist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:

eine nichtleere, endliche Menge von Zuständen

eine nichtleere, endliche Menge von Eingabesymbolen, die das Symbol ∅ nicht enthält

eine nichtleere, endliche Menge von Bandsymbolen, die alle Eingabesymbole und auch das Symbol ∅ für eine leere Zelle enthält

eine Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit von einem gelesenen Symbol den Folgezustand zuordnet, zudem das zu schreibende Symbol und die Bewegung des Lese-Schreibkopfes

einen ausgezeichneten Zustand - den Anfangszustand -

eine Menge von Endzuständen

Bei einer nichtdeterministischen Turingmaschine müssen die Zustandsübergänge nicht eindeutig sein.

52 Fachkonzept - Turingmaschine

Die Menge der Eingabesymbole einer Turingmaschine kann als Alphabet einer Sprache aufgefasst werden.

Unter der Sprache einer Turingmaschine versteht man die Menge aller Wörter aus Eingabesymbolen, die die Turingmaschine vom Anfangszustand in einen Endzustand überführen.

Wenn T eine gegebene Turingmaschine ist, dann schreiben wir L(T) für die Sprache der Turingmaschine T.

= {(, )}

L(T) = {(), (()), ((())), ...}

53 Fachkonzept - Turingmaschine

Eine Turingmaschine ist also eine Verarbeitungseinheit, die Symbole verarbeitet, sich dabei stets in einem bestimmten Zustand befindet und die zum Zwischenspeichern von Symbolen ein unbegrenztes, beschreibbares und nach rechts und links begehbares Band benutzt.

54 Bedeutung der Turingmaschine

Trotz dieser Mächtigkeit wird das Verarbeitungsmodell Turingmaschine in der Praxis nicht genutzt. Wegen der doch sehr eingeschränkten Verarbeitungsmöglichkeiten einer Turingmaschine werden die Verfahren zur Erkennung von Sprachen schnell kompliziert und aufwendig.

Satz (Zusammenhang zwischen Turingmaschinen und formalen Sprachen):

Zu jeder formalen Sprache, die mit einer Grammatik beschreibbar ist, gibt es eine (nicht-) deterministische Turingmaschine, der diese Sprache erkennt. Umgekehrt gibt es auch zu jeder (nicht-) deterministischen Turingmaschine eine Grammatik, die dieselbe Sprache erzeugt, die von der Turingmaschine erkannt wird.

Das Verarbeitungsmodell Turingmaschine hat eine zentrale Bedeutung im Rahmen der Theoriebildung. Die Verwendung beschränkt sich dabei nicht auf den Kontext Spracherkennung, das Verarbeitungsmodell wird auch bei Fragen der Berechenbarkeit benutzt.

55 Übungen

Man kann zeigen, dass die Sprache L = {anbncn | n = 1, 2, 3, ...} nicht mit einem Kellerautomaten erkannt werden kann. Diese Sprache besteht aus Wörtern, die wie folgt aufgebaut sind:

abc, aabbcc, aaabbbccc, aaaabbbbcccc, ...

Zeige, dass diese Sprache mit einer Turingmaschine erkannt werden kann. Erweitere hierzu die Turingmaschine zur Erkennung von L = {anbn | n = 1, 2, 3, ...}.

56 Teil 5

Sprachklassen und Automatenklassen

57 Chomsky-Hierarchie

Typ Grammatik äquivalenter Automat

0 allgemein (nicht)deterministische Turingmaschine

1 kontextsensitiv nichtdet. linear beschr. Turingmaschine

2 kontextfrei nichtdeterministischer Kellerautomat

3 regulär (nicht)deterministischer endl. Automat

58 Literaturhinweise

F. Gasper, I. Leiß, M. Spengler, H. Stimm: Technische und theoretische Informatik. Bsv 1992.

E. Modrow: Automaten, Schaltwerke, Sprachen. Dümmlers Verlag 1988.

R. Baumann: Informatik für die Sekundarstufe II, Band 2. Klett-Verlag 1993.

Informatik heute, Band 2. Schroedel-Verlag 1988.

U. Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag 2001.

J. E. Hopcroft / J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley 1988.

S. H. Rodger, T. W. Finley: JFLAP. Jones and Bartlett Publishers 2006.

...

Die Darstellung hier orientiert sich an den Materialien auf den Webseiten:

http://www.inf-schule.de