Hallo,

ich hab ein Problem mit D0L-Systemen, also Deterministischen Zero-Kontext Lindenmayer-Systemen. Und zwar: Ich hab die Sprache {a^4^n b^2010 a^4^n | n>=0} gegeben und soll daraus eine D0L-Grammatik erzeugen. Mein Ansatz wäre folgender: G=<{a,b}, a b^2010 a, {a -> aaaa}>

Nur hab ich jetzt auf einer Website gelesen das alle Symbole ableitbar sein müssen. (Das war so ein cooles Programm das mit den Ableitungsbaum aufgezeichnet hat, das mir das gesagt hat.) Muss ich jetzt meine Grammatik nun umformen und wenn ja, wie? Denn ich kenn keine Grammatik bei der man eine Obergrenze setzen kann.

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Mein Vorschlag dazu: Ein drittes Symbol plus die leere Menge für die "Obergrenze":

G=<{a,b,x,€}, x b^2010 x, {x -> aaaax | x -> € }> wobei € für leere Menge steht, a^0 eine leere Menge ist und a^1 <=> aaaa.

Bei a => aaaa sehe ich das Problem, dass so auch a^7 möglich ist, da ich von a auf aaaa schließe und dann eines der 4 a weiterableite : (aaaa)aaa [Klammerung zum Verständins].

Hoffe dass das so korrekt ist.
Der Informatik-Unterricht ist schon etwas her.

MFG
Tilo

Danke für deinen Beitrag. Das Problem ist nur wenn ich mit x b^2010 x anfange, das ich einerseits wieder das Problem hab das ich nicht weiß ob ich für b auch eine Produktion brauche damit es eine gültige D0L-Grammatik ist und zusätzlich kommt noch das Problem dass das wort {b^2010} auch in der Sprache liegt, was es nicht dürfte. Denn laut der Sprachendefinition (a^4^n b^2010 a^4^n für n >= 0) muss mindestens ein a auf jeder Seite stehen. Denn wenn wir in n 0 einsetzen bekommen wir für a = a^4^0 heraus. 4^0 = 1 (sowie jede Zahl Hoch 0) und das bedeutet ich hab a^1. Demnach ist das kleinste Wort in der Sprache a b^2010 a.

wie kommst du darauf das man plötzlich 7 a's Produzieren kann? Soweit ich weiß muss man doch einen Produktionsschritt fertig machen sobald man ihn angefangen hat. Also wenn ich zb aaaa hab muss ich im nächsten Produktionsschritt jedes a wieder mit 4 a ersetzen also hab ich dann aaaaaaaaaaaaaaaa, oder irre ich?

lg elundril

P.S.: lass dich nie von meinem Professor erwischen, der wird rasend wenn man die leere Menge mit dem Leerwort (dem Epsilon) verwechselt.

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

Okay Stimmt, dadurch dass für n 0 erlaubt ist wird die Sache komplizierter. Für n=0 und n=1 gibt es dann die zwei Worte ab^2010a und aaaab^2010aaaa.

Wie wäre es damit:

G=<{a,b,x,y,€}, y b^2010 y, {y -> a | y -> aaaax | x -> € | x -> aaaax }>

Durch das y wird sichergestellt dass es mindestens ein a gibt (Fall n=0) und durch x wiederum ist gesichert, dass es für n>0 immer nur Vielfache von a^4 gibt.
Statt x->€ kann man auch auch x->aaaa (ohne x am Ende) schreiben nur muss dann y->aaaax nach y->x geändert werden:

G=<{a,b,x,y}, y b^2010 y, {y -> a | y -> x | x -> aaaa | x -> aaaax }>

Vorteile hier: a) nur 4 statt 5 Symbole und b) keine Diskussion um Leerwort kontra leere Menge. (Das überlasse ich lieber den Philosophen).

Bin mal auf die Musterlösung des Professors gespannt.

ich versteh nicht ganz warum du das x und das y einführst, da es laut der Regeln für ein Lindenmayersystem eh zu keiner ungeraden Ableitung kommen kann? Das heißt wenn ich das Wort aaa b^2010 aaa hab, darf ich doch eh nicht mitten drunter aufhören. Also kommt dafür dann aaaaaaaaaaaa b^2010 aaaaaaaaaaaa raus, weil laut dem hier in jedem Ableitungsschrittes eines Wortes jedes Symbol einmal ersetzt werden muss (0L-Systeme auf wikipedia - 1. Absatz, 2. Satz).

Das was ich mich Frage ist ob ich auch für das b eine Ableitungsregel brauche, damit es ein korrektes Lindenmayersystem ist?

lg elundril

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.