Grammatik Ableitungen

Neue Frage »

wurmi86 Auf diesen Beitrag antworten »
Grammatik Ableitungen
Gegeben sei die Grammatik G=({S,T},{a,b},R,S) mit der folgenden Regelmenge R:
S->ab
S->Tb
S->ab
S->e(epsilon)
T->b
T->Tb
T->ab
T->e

Hierin hat das Wort mehrere Ableitungen. Wieviele? Geben Sie alle an.

eigentlich kann ich das a und das b niemals auflösen oder?
kiste Auf diesen Beitrag antworten »

Deine Frage verstehe ich nicht, aber es gibt keine Rekursion die a's erzeugt. Also gibt es überhaupt keine Ableitung für a^4b^3
 
 
wurmi86 Auf diesen Beitrag antworten »

ja ungünstig gestellt die frage.

nagut dann anders. kann mir jemand eine Ableitung geben? den rest kann ich mir dann sicher zusammenschustern. aber irgendwie glaube ich es gibt wirklich keine Ableitung.
weil ich die Nichtterminalsymbole nicht auflösen kann. ich bin verwirrt, und stehe aufm Schlauch.

auf die aufgabe gibt es übrigens 4 punkte.
kiste Auf diesen Beitrag antworten »

Wenn ich 2 Sätze schreibe, dann erwarte ich auch dass beide gelesen werden.
wurmi86 Auf diesen Beitrag antworten »

Ja stimmt. Danke.

Mich hat nue ein bisschen irritiert, dass es 4 Punkte darauf gibt.
chrizke Auf diesen Beitrag antworten »

Da ist sehr wahrscheinlich ein Fehler in der Aufgabenstellung, da es zwei mal S->ab gibt. Das eine davon heißt garantiert S->aS.

Aber wenn es da nicht steht... Augenzwinkern
wurmi86 Auf diesen Beitrag antworten »

ach ja du hast recht. mein Fehler. es Gibt wirklich ein S->ab, und ein S->aS.geändert
kiste Auf diesen Beitrag antworten »

Der Trick ist es mit der Regel S->aS im einen Fall 3 a's und im anderen Fall 4 a's zu produzieren. Die restlichen Produktionen für die b's sind dann eindeutig
wurmi86 Auf diesen Beitrag antworten »

das ist mir gerade echt unangenehm. =).
aber ich blicke nicht durch. Schmunzeln erlaubt.

mein Wissensstand bis jetzt ist folgender:

ein komplett abgeleitetes Wort besteht am Ende nur aus Terminalsymbolen(also dem Alphabet(S und T))

Da diese aber in den Ableitungsregeln niemals alleine auftreten, kann ich demzufolge auch niemals ein Wort ableiten. Denke ich soweit richtig?


Irgendwie hänge ich auch noch daran, dass ich der Meinung bin, dass Nichtterminalsymbole NICHT aus Terminalsymbolen abgeleitet werden können.
Also dass z.B.: S->ab gar nciht geht.

ist es dann nun ein Tippfehler in der Aufgabenstellung? oder ein Tippfehler bei mir im Kopf?

MfG Wurmi
kiste Auf diesen Beitrag antworten »

Ja die Regel S->ab führt in diesem Fall tatsächlich nicht zum Ziel.

Aber sowas wie S -> aS -> aaS -> ... schon

Ah und die Terminalsymbole sind a,b nicht S,T Augenzwinkern
wurmi86 Auf diesen Beitrag antworten »

aber laut Definition ist die Grammatik gegeben durch G=(,N,S,R)
mit .. Menge der Terminalsymbole
N..Nichtterminale,
S Start und
R Regeln.

und in der Aufgabenstellung ist demanach {S,T} = ...weil es ja der erste Eintrag im 4-Tupel ist.
kiste Auf diesen Beitrag antworten »

Offensichtlich wurde bei deiner Aufgabe eine andere Reihenfolge benutzt, das siehst du ja auch daran dass Regelmenge und Startsymbol auch vertauscht wurden. Außerdem muss das Startsymbol immer ein Nichtterminal sein!

So eng darfst du das mit den Tupeln sowieso nicht sehen, das ist nur "formaler Quatsch"
wurmi86 Auf diesen Beitrag antworten »

sehr gut! jetzt entwirre ich die knoten im kopf. Danke.

nun kann ichs wenigstens schonmal angehen.

Wurmi
wurmi86 Auf diesen Beitrag antworten »

Danke kiste und chrizke

also gut

S->aS->aaS->aaaS->aaaaS->aaaaTb->aaaaTbb->aaaabbb


S->aS->aaS->aaaTb->aaaTbb->aaaabbb


gibt es mehr?

was ist z.B. mit irgend ein wort w*epsilon? epsilon ist das leere wort. aber ist w*epsilon=w?




Gruss Wurmi
kiste Auf diesen Beitrag antworten »

Zitat:
Original von kiste
Der Trick ist es mit der Regel S->aS im einen Fall 3 a's und im anderen Fall 4 a's zu produzieren. Die restlichen Produktionen für die b's sind dann eindeutig

Du hast die Regel mit 4 a's gefunden, fehlt also noch? Augenzwinkern

edit: Gut die andere hast du auch. Jetzt gibt es noch, wie du bereits erkannt hast die Möglichkeit mit epsilon. Versuche also statt T->b eine andere Regel
wurmi86 Auf diesen Beitrag antworten »

S->aS->aaS->aaaTb->aaaTbb->aaaabbb


sorry hatte es editiert oben. dachte bin schnell genug..

Danke! du bist wohl den ganzen Tag vorm Matheboard und hilfst solchen nullpeilern wie mir?

Alle Achtung, das sollte irgendwie honoriert werden. Weiter so =)

Gruss Wurmi
wurmi86 Auf diesen Beitrag antworten »

S->aS->aaS->aaaS->aaaaS->aaaaTb->aaaaTbbb->aaaabbb

grübel grübel. eine vierte seh ich nun wiederum nicht mehr.

demzufolge gibt es unendlich viele ableitungen. weil ich auch unendlich oft das epsilon verwenden kann...
kiste Auf diesen Beitrag antworten »

Ja, mehr sehe ich auch nicht.

Unendlich geht nicht, sonst bräuchtest du eine Regel wie T->eT oder T->TT oder sowas.
wurmi86 Auf diesen Beitrag antworten »

okay vielen dank. jetz sieht die mathewelt doch schon viel freundlicher aus.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »