Fachrat Informatik - Forum

Quoted

Original von NullAhnung
Die Typ 1 Grammatik hab ich jetzt. Darf ich bei Typ 3 das machen: S->aaA oder ist das auch wieder nix?

Auch wieder nix

Es sind nur Regeln der Form S->a und S->aA erlaubt.

ich hab mal ne kleine verständnisfrage:
man soll doch mit der in aufg. 2 a gegebenen sprache ne gramm. typ 3 erstellen wobei wörter gebildet werden müssen und die anzahl von as gerade sein soll, sollen die gebildeten wörter beliebig lang sein? wenn ja dann wie soll man da nach dem tip von vier vorgehen?
"Kleiner Tipp: wenn du über die Grammatik Wörter erstellst, achte nur darauf, dass die Anzahl der a's am Ende korrekt ist. Anschließen erstelle Regeln wo du Positionen verändern kannst, sodass alle a-b-Kombinationen erreichbar sind"

Da es offenbar einige Verwirrung darüber zu geben scheint, wie Grammatiken der verschiedenen Typen auszusehen haben, hier mal eine kurze Zusammenfassung:

Typ 0:
Linke Seite der Produktionen: beliebig, aber mindestens eine Variable

Rechte Seite der Produktionen: beliebig


Typ 1:
Linke Seite der Produktionen: beliebig, aber mindestens eine Variable

Rechte Seite der Produktionen: beliebig

Einschränkung: die rechte Seite muß bei jeder Produktion mindestens so lang sein wie die linke

Sonderregel: Die Produktion "Startvariable -> epsilon" ist erlaubt, wenn die Startvariable bei keiner Produktion auf der rechten Seite vorkommt.


Typ 2:
Linke Seite der Produktionen: genau eine Variable

Rechte Seite der Produktionen: beliebig

Einschränkung: die rechte Seite muß bei jeder Produktion mindestens die Länge 1 haben

Sonderregel: Die Produktion "Startvariable -> epsilon" ist erlaubt, wenn die Startvariable bei keiner Produktion auf der rechten Seite vorkommt.


Typ 3:
Linke Seite der Produktionen: genau eine Variable

Rechte Seite der Produktionen: entweder genau ein Terminalzeichen oder ein Terminalzeichen gefolgt von einer Variablen.

Einschränkung: die rechte Seite muß bei jeder Produktion mindestens die Länge 1 haben

Sonderregel: Die Produktion "Startvariable -> epsilon" ist erlaubt, wenn die Startvariable bei keiner Produktion auf der rechten Seite vorkommt.

das hab ich mir in der vorlesung auch aufgeschrieben und verstehs auch, nur beantwortet das meine frage nicht

Quoted

Original von Uprooter
man soll doch mit der in aufg. 2 a gegebenen sprache ne gramm. typ 3 erstellen wobei wörter gebildet werden müssen und die anzahl von as gerade sein soll, sollen die gebildeten wörter beliebig lang sein?

Ja, denn es soll ja jedes Wort dieser Sprache mit der Grammatik abgeleitet werden können.

Quoted

wenn ja dann wie soll man da nach dem tip von vier vorgehen?
"Kleiner Tipp: wenn du über die Grammatik Wörter erstellst, achte nur darauf, dass die Anzahl der a's am Ende korrekt ist. Anschließen erstelle Regeln wo du Positionen verändern kannst, sodass alle a-b-Kombinationen erreichbar sind"

Ein Beispiel, das dich vielleicht auf die richtige Idee bringt:

Folgende Grammatik erzeugt die Sprache {(ab)^k | k aus N_0}, also {epsilon, ab, abab, ababab, abababab, ...}:

S -> epsilon
S -> aY
Y -> bX
Y -> b
X -> aY


Zur Erklärung:

Steht bei einer Ableitung am Ende ein Y, so bedeutet das, daß noch mindestens ein "b" folgen muß, damit das Wort zur Sprache gehört.

Steht bei einer Ableitung am Ende ein X, so bedeutet das, daß noch ein "ab" folgen muß, damit das Wort zur Sprache gehört.

Mit den Variablen kann man aich also gewissermaßen die "Zustände" der Ableitung merken (also die Eigenschaften des bisher abgeleiteten Wortes). Bei der Übungsaufgabe 2a) könnten diese Zustände sein: "Anzahl a ungerade", "Anzahl a gerade".

Ich will an dieser Stelle aber auch nicht zuviel verraten. Am besten, Du kommst nächste Woche in die Übung, dort werden wir das ausführlich erklären.

dank dir vielmals mal sehen was ich damit auskochen kann

Quoted

Original von Joachim
Da es offenbar einige Verwirrung darüber zu geben scheint, wie Grammatiken der verschiedenen Typen auszusehen haben, hier mal eine kurze Zusammenfassung:

Typ 0:
Linke Seite der Produktionen: beliebig, aber mindestens eine Variable

Rechte Seite der Produktionen: beliebig


Typ 1:
Linke Seite der Produktionen: beliebig, aber mindestens eine Variable

Rechte Seite der Produktionen: beliebig

Einschränkung: die rechte Seite muß bei jeder Produktion mindestens so lang sein wie die linke

Sonderregel: Die Produktion "Startvariable -> epsilon" ist erlaubt, wenn die Startvariable bei keiner Produktion auf der rechten Seite vorkommt.

Dazu noch eine Anmerkung:

Streng genommen, sind bei Typ-0- und Typ-1-Grammatiken auch die linken Seiten der Produktionen beliebig, d. h. es können auch Terminalsymbole ersetzt werden. Da ich dies aber nicht für besonders sinnvoll halte, habe ich es anders aufgeschrieben.

Letztendlich ist es auch egal wie man es definiert. An den Eigenschaften dieser Grammatiken ändert sich dadurch nichts.