Beispiel 5.5

[schrankk]

Wenn ich die L-Systeme richtig verstanden habe :eek2:, sollte dann die Lösung etwa so aussehen:

a) G = ({a, c}, {a->a^5}, accccca)

b) G = ({a, b, c, d}, {a->a^2, b->b^3, c->c^5, d->d^8}, abcd)

c) G = ({a}, {a->a, a->Eps}, aa)

vlg

[KatzeImSack]

naja, bei den 0L-Systeme gibt es ja nur eine Produktion, oder?

also 1. hab ich genauso wie du...

bei 3. könnt ich höchstens auf Folie 174 verweisen.
({a,a²} von 0L-System nicht erzeugbar)

und bei 2. würd ich dann anstehen....

oder hast du da auch andere systeme hergenommen?

[jperl]

naja, bei den 0L-Systeme gibt es ja nur eine Produktion, oder?

also 1. hab ich genauso wie du...

bei 3. könnt ich höchstens auf Folie 174 verweisen.
({a,a²} von 0L-System nicht erzeugbar)

und bei 2. würd ich dann anstehen....

oder hast du da auch andere systeme hergenommen?

nein es gibt nur ein startwort. aber produktionen darf es mehrere geben.
siehe beispiele im skriptum.

zu 3.
{eps, a, aa} != {a, aa}

jperl

[Gerros]

G1 = <{a,c}, {a->a^5, c->c}, accccca}>
G2 = <{a,b,c,d}, {a->a^2, b->b^3, c->c^5, d->d^8}, abcd}>
G3 = <{a}, {a->eps, a->a}, aa>
es steht nirgends, dass das 0L-System deterministisch sein muss, also sollte glaub ich G3 so funktionieren...man kann nur die drei gegebenen Wörter von L3 konstruieren (inkl. eps).

kleiner Hinweis: ich persönlich hab mir lange den Kopf zerbrochen, bis ich dann draufgekommen bin, dass das in der Angabe immer heißt a^2^n und nicht a^2*n....

[Markus1201]

G = ({a}, {a->Eps, Eps->a}, aa)

Laut Skript wird doch bei Lindenmayer-Systemen immer alles parallel abgeleitet. aa\rightarrow\epsilon\epsilon\rightarrow aa und so weiter. Das würde fürs erste heißen dass du kein a erzeugen kannst. Falls du annimmst, dass du, wenn da zwei \epsilon stehen, eins wegnehmen darfst weil es das Wort nicht ändert, müsstest du auch eins dazugeben dürfen und würdest somit {a}* erzeugen.

Bei Fehlinterpretationen meinerseits bitte ich um Korektur.

[Bianconeri]

Habe ich das richtig verstanden, dass in einem 0L-System immer alle vorhandenen Ableitungen gleichzeitig durchgeführt werden? Wenn ja habe ich zumindest mal a) und b) gleich wie schrankk. c) muss ich mir noch anschauen.

[bsoykal]

wie laut zuletzt die richtige Lösung für 3?
:)

[schrankk]

wie laut zuletzt die richtige Lösung für 3?
:)
ich werde mich damit erst morgen richtig beschäftigen, aber ich kann dir noch ne Auskunf aus Wikipedia geben, und meine alte Lösung darauf aufbauend doch bissle verteidugen:
Um ein L-System zu realisieren, wird eine Tiefe n festgelegt und ein Ersetzungsschritt endlich oft wiederholt. Im Ersetzungsschritt wird das aktuelle Wort ω Zeichen für Zeichen abgearbeitet und jedes Zeichen durch das neue, in den Ersetzungsregeln festgelegte Wort ersetzt.
Kontext-freie L-Systeme (auch 0L-Systeme genannt) enthalten Produktionen p, die auf ein Anfangswort ω (auch Axiom genannt) n-mal angewandt werden. Die Produktionen ordnen dabei maximal einem Zeichen ohne Beachtung des Kontextes ein Wort zu. Wird für ein Zeichen keine Regel angegeben, wird im Allgemeinen die Identität als triviale Ersetzung des Zeichens durch sich selbst angenommen.Also in erstem Schritt (n=1, erste Widerholung) wird das Anfangswort aa Symbol für Symbol durch EpsEps ersetzt, was das Leerwort Eps ergibt. In zweitem Schritt (n=1) werden die Regeln auf vorher erhaltende Wörter angewendet (oder nur auf letzte Wort, bin leider noch nicht sicher). Eps -> a. Damit erhalten wir noch zu unserer Sprache das Wort a, der gemeinsam mit Anfangswort und Leerwort unseres Beispiel löst! Ja, und falls auf alle bisher erzeugte Wörter werden die Regeln angewendet, dann werden einfach immer a und Eps produziert... sehr-sehr viel, aber immer das gleiche, und kein {a}* o.Ä.

[bsoykal]

Ein Blödsinn aber können wir nicht so machen;

eps->a
a-> aa

w=eps ??

[schrankk]

Ein Blödsinn aber können wir nicht so machen;

eps->a
a-> aa

w=eps ??
somit wird bereits in drittem Schritt aus aa ein Wort aaaa erzeugt, was uns nicht erlaubt ist!

[bsoykal]

ahso :) danke

[bsoykal]

noch eine Frage kann ein V zu einer anderen V gehen ?
zB
b->a
c->a
a->eps
w=bc

[schrankk]

noch eine Frage kann ein V zu einer anderen V gehen ?
zB
b->a
c->a
a->eps
w=bc
ich denke schon, wieso nicht?! nur somit erzeugst du ein Terminalwort bc, das nicht erzeugen werden darf! ;)

[blackandcold]

Laut Skript wird doch bei Lindenmayer-Systemen immer alles parallel abgeleitet. http://mitaub.sourceforge.net/cgi-bin/mimetex.cgi?aa%5Crightarrow%5Cepsilon%5Cepsilon%5C rightarrow%20aa und so weiter. Das würde fürs erste heißen dass du kein a erzeugen kannst. Falls du annimmst, dass du, wenn da zwei http://mitaub.sourceforge.net/cgi-bin/mimetex.cgi?%5Cepsilon stehen, eins wegnehmen darfst weil es das Wort nicht ändert, müsstest du auch eins dazugeben dürfen und würdest somit {a}* erzeugen.

ad. c) G = ({a}, {a->Eps|a}, aa)

heißt so viel wie, dass entweder aa->aa oder aa->Epsa oder aa->EpsEps->Eps
geschieht parallel und da wir kein EpsEps->aa ham, können nur die (a, aa oder Eps) drei sachen entstehn. ;)

[Markus1201]

ad. c) G = ({a}, {a->Eps|a}, aa)

heißt so viel wie, dass entweder aa->aa oder aa->Epsa oder aa->EpsEps->Eps
geschieht parallel und da wir kein EpsEps->aa ham, können nur die (a, aa oder Eps) drei sachen entstehn. ;)

Das ist mir an sich klar, das ist meiner Meinung nach auch die richtige Lösung. Ich bin mir aber ganz sicher das man \epsilon nicht Ableiten darf, wie schrankk das vorgeschlagen hat.

[blackandcold]

da hast du recht, bei Eps is ende gelände ;)

[Lumpaci]

also zuerst hätte ich ja c ebenso gelöst, also
G = ({a}, {a->Eps|a}, aa)

Laut Skriptum (S.76 oben) ist aber ein 0L System (das ja n=1 hat und damit nur genau eine Produktion a->w zugelassen ist) deterministisch. Diese Produktionen sind aber nicht deterministisch. Daraus schließe ich, dass das nicht gehen kann.

[jperl]

also zuerst hätte ich ja c ebenso gelöst, also
G = ({a}, {a->Eps|a}, aa)

Laut Skriptum (S.76 oben) ist aber ein 0L System (das ja n=1 hat und damit nur genau eine Produktion a->w zugelassen ist) deterministisch. Diese Produktionen sind aber nicht deterministisch. Daraus schließe ich, dass das nicht gehen kann.

das n=1 steht imho dafür, dass es nur einen produktionenmenge P gibt, die aber durchaus mehrere produktionen enthalten darf.

jperl

[crashOverride]

das n=1 steht imho dafür, dass es nur einen produktionenmenge P gibt, die aber durchaus mehrere produktionen enthalten darf.

jperl

Hallo jperl,

das stimmt schon, jedoch darf in diesem einem Produktionstable jedes Zeichen nur einmal vorkommen als Produktion!!!!!

mfg

[jperl]

Hallo jperl,

das stimmt schon, jedoch darf in diesem einem Produktionstable jedes Zeichen nur einmal vorkommen als Produktion!!!!!

mfg

das gilt aber nur für systeme die ein D enthalten. müsste also D0L sein. d steht in diesem fall für deterministisch.
siehe skriptum (version oktober 2008) seite 76.

jperl

[jperl]

http://www.google.at/url?sa=t&source=web&ct=res&cd=9&url=http%3A%2F%2Fwww-fs.informatik.uni-tuebingen.de%2Flehre%2Fss04%2Ffs%2FUebungsblaetter %2FLoesungen%2FLoesungen_10.pdf&ei=-bwaSemKFZKg0gWGjaGdDw&usg=AFQjCNE05Z6qaBKPQs4c9QeSZ2c2Y0mIcw&sig2=VmP7y6AIJuP5KBPvcM_nPw

Seite 2

jperl

[schrankk]

http://www.google.at/url?sa=t&source=web&ct=res&cd=9&url=http%3A%2F%2Fwww-fs.informatik.uni-tuebingen.de%2Flehre%2Fss04%2Ffs%2FUebungsblaetter %2FLoesungen%2FLoesungen_10.pdf&ei=-bwaSemKFZKg0gWGjaGdDw&usg=AFQjCNE05Z6qaBKPQs4c9QeSZ2c2Y0mIcw&sig2=VmP7y6AIJuP5KBPvcM_nPw

Seite 2

jperl
also dann ist wohl die richtige Lösung für c) {a->a, a->Eps} mit dem Wort aa als Axiom!

Danke jperl!! :thumb:

[crashOverride]

Ok,

dann stimmt das ja eh von Lumpaci eh mit:

G = ({a}, {a --> Eps|a}, aa) jedoch würde ich

es anders hinschreiben:

und zwar so:

G = ({a}, {a --> {Eps, a}}, aa) dadurch wird gewährt, dass bei der
parallelen Ableitung, nicht gleich vorgegeben ist, dass zweimal a --> Eps,
oder a --> a hergenommen wird!

mfg


Siehe:

http://klimek.box4.net/files/lindenmayer.pdf
http://kolho3.tiera.ru/_Papers/TU%20Wien%20Scripta/Informatik/Formale_Sprachen_und_Automaten/Formale_Sprachen_und_Automatentheorie_001(de)(76s) .pdf

[Clyde]

Ist schon spät und mein Kopf dreht Kreise, aber beim Bsp a): a->a^5 mit Axiom accccca ist meiner Meinung nach falsch, da

1) mit 0-maligem Ableiten das Wort accccca herauskommt, was nicht in der Sprache {a^5n c^5 a^5n} ist,
2) Das Wort ccccc, was sehr wohl in der Sprache ist, nicht abgeleitet wird und
3) bei 1-maligem ableiten korrekt a^5 c^5 a^5 herauskommt, aber bei 2-maligem Ableiten dann schon a^25 c^5 a^25 abgeleitet wird und somit n={10,15,20} komplett ausgelassen werden.

Dieses 0L-System bildet also die Sprache {a^(5^n) c^5 a^(5^n)}, und nicht die geforderte.

Da man in L-Systemen ja auf der linken Seite der Produktion durchaus auch mehrere Variablen stehen haben kann, wäre meiner Meinung nach das richtige 0L-System:

{c^5 -> a^5 c^5 a^5} mit Axiom ccccc.

Hört sich das logisch an oder hab ich Mist gebaut? :)

[jperl]

1. die lösung stimmt.
2. dann wäre laut deiner meinung wohl auch das 2. beispiel falsch was ebenfalls stimmt.
3. schau dir mal den angabenzettel genau an. da steht 5^n und nicht 5n.
4. 0 mal ableiten gibts nicht. das ist das startwort.

jperl

[majinquinkx]

bilde mal die ersten wörter... es schaut wie eine Endlosschleife
nur c^5 können ersetzt werden und nur a^5c^5a^5 kommt dabei heraus. watt nun?

ich vermute es ist ein Beispiel, wofür es keine Lösung gibt.

korrektur

analyse:

wie wir sehen zeigt a^(5^n), dass die Anzahl der a eine Folge mit n = {5^0=1, 5^1=5, 5^2=25, ...} sein muss
der erste Ansatz mit accccca und a --> a^5 "ist richtiger"

[jperl]

bilde mal die ersten wörter... es schaut wie eine Endlosschleife
nur c^5 können ersetzt werden und nur a^5c^5a^5 kommt dabei heraus. watt nun?

ich vermute es ist ein Beispiel, wofür es keine Lösung gibt.

du solltest dich noch ein wenig eingehender mit L-Systemen beschäftigen.


schau dir den satz 1.138 (skriptum version oktober 2008) s. 75 an.
kurz gesagt:
die sprache bildet sich aus allen wörtern die in beliebig vielen schritten aus dem startwort gebildet werden können und nur aus terminalsymbolen bestehen.

jperl

[Clyde]

1. die lösung stimmt.
2. dann wäre laut deiner meinung wohl auch das 2. beispiel falsch was ebenfalls stimmt.
3. schau dir mal den angabenzettel genau an. da steht 5^n und nicht 5n.
4. 0 mal ableiten gibts nicht. das ist das startwort.

jperl

Gut, ich brauche hiermit offiziell eine Brille - ich hab a^5n gelesen, nicht a^5^n, damit erübrigt sich mein Post natürlich. Danke für den Hinweis, da hätte ich morgen wohl sehr blöd dreingeschaut :)

0 mal ableiten gibt es aber sehr wohl, vgl. z.B. http://en.wikipedia.org/wiki/L-system

der erste Ansatz mit accccca und a --> a^5 "ist richtiger"

Nicht "richtiger", ganz richtig ;)

[majinquinkx]

[ ...]
jo, danke... werd ich mir zu herzen nehmen...

[SBLU]

---del

[jperl]

doch die sprache {eps, a, aa} kann von oben angegebenen 0L-System gebildet werden.

jperl