HSG |
|
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?
Die Sprache L = {anbn | 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.
Der Automat ist dabei nach folgendem Schema aufgebaut:
In der Abbildung ist der Trace zum Erkennen von aabb zu sehen.
Mit folgender Grammatik (Schöningh, Theoretische Informatik - kurzgefasst, S.14) lassen sich einfache arithmetische Ausdrücke darstellen:
Auch hier kann der Kellerautomat automatisch erzeugt werden:
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:
Fertige zu der Grammatik Syntax-Diagramme an.
Auf der kleinen Insel Noam sprechen die Eingeborenen eine ganz besondere Sprache. In langjähriger Arbeit konnte eine Sprachforscherin folgendes feststellen:
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?
Gib zu obiger Aufgabe Syntaxdiagramme an.
Gib zu obiger Aufgabe eine Grammatik an. noam.jff
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.