Formale Sprachen und Automaten - kontextfreie Sprachen

Sprachen

Pfad: Startseite / Fächer / Informatik / Theorie / Sprachen / kontextfreie Sprachen

Autor: mk
05.11.2008 18:59
695

kontextfreie Sprachen und Kellerautomaten

Aufgabe

Gib auf deinem Taschenrechner eine vielfach korrekt geklammerte Zahl ein, z.B (((...((42))...))). Bis wie viele Klammerpaare macht er das mit? Welche Fehlermeldung kommt, wenn du diese Grenze überschreitest?

Beispiel 1

Die Sprache L = {aⁿbⁿ | n ∈ IN} wird z.B. durch die Grammatik S → aSb, S → ε erzeugt. Gibt man diese Grammatik in JFLAP ein, so kann man sich automatisch ( Convert to PDA(LL) ) folgenden nichtdeterministischen Kellerautomaten erzeugen lassen.

Kellerautomat zu anbn

Der Automat ist dabei nach folgendem Schema aufgebaut:

Im Zustand q0 wird spontan das Startsymbol auf den Stack (in den Keller) gelegt und in den Zustand q1 übergegangen.
Der Zustand q1 erhält für jede Produktion A → α eine Schleife mit der Anweisung λ;A;α , dh. A wird vom Stack genommen und durch α ersetzt. Eine Produktion A → a wird durch die Anweisung a;a;λ ersetzt, dh. das gelesene Zeichen wird vom Stack entfernt. Durch eine geschickte Abfolge der beiden Anweisungsarten ist es möglich, mit einer Zeichenkette, die sich aus den Produktionen herleiten lässt, den Stack (Keller) zu leeren.
Bei leerem Keller (nur Kellerende-Zeichen Z auf dem Stack) erfolgt spontan ein Übergang in den akzeptierenden Zustand q2.

In der Abbildung ist der Trace zum Erkennen von aabb zu sehen.

Trace zu aabb

Beispiel 2

Mit folgender Grammatik (Schöningh, Theoretische Informatik - kurzgefasst, S.14) lassen sich einfache arithmetische Ausdrücke darstellen:

E → T
E → E+T
T → F
T → T*F
F → a
F → [E] Bemerkung: JFLAP verwendet die runden Klammern intern, sodass hier eckige benutzt werden.

Auch hier kann der Kellerautomat automatisch erzeugt werden:

Kellerautomat zu Schöningh, S.14

Zum Test kontrolliere man über 'Multiple Run', dass das Wort a*a*[a+a]+a akzeptiert wird. Hier hat wegen des Nicht-Determinismus der Computer schon ein wenig zu tun.

Ein Syntaxbaum zu obigem Wort sieht so aus:

Syntaxbaum zu Schöning, S.14

Aufgabe

Fertige zu der Grammatik Syntax-Diagramme an.

Beispiel 3

Noamesisch (Aufgabe des Informatik-Biber 2006)

Auf der kleinen Insel Noam sprechen die Eingeborenen eine ganz besondere Sprache. In langjähriger Arbeit konnte eine Sprachforscherin folgendes feststellen:

Es gibt die Wörter ba, di und du.
Durch Verdopplung eines Worts entsteht ein neues Wort; Beispiel: baba.
Ein neues Wort entsteht auch, indem ein Wort vorne und hinten an ein anderes Wort angefügt wird; Beispiel: baduba

Als sie versuchte, mit den Noamesen zu reden, funktionierte das ganz gut, doch bei einem der folgenden Worte zuckten die Noamesen nur verständnislos mit den Achseln.

Bei welchem?

A) dudubabadudubabadudu
B) didudubadududi
C) dudubadibadibadu
D) dididudidibadibadididudidi

Aufgabe

Gib zu obiger Aufgabe Syntaxdiagramme an.noam.gif

Aufgabe

Gib zu obiger Aufgabe eine Grammatik an. noam.jff

Aufgabe

Schreibe ein Delphi-Programm , das nach dem Syntax-Diagramm zufällig Wörter der Sprache erzeugt. Teste einige interessante Wörter mit der Grammatik in JFlap.

Arbeitsauftrag

Arbeite dich anhand folgender Links aus dem Kurs von Herrn Helmich in die Begriffe 'Stack', 'Stackmaschine' ein. Es soll am Ende ein funktionsfähiges Delphi-Programm stehen.

Stackmaschine

lokal