Aufgabe 10.2
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Aufgabe 10.2
Aus Ermangelung eines Unterforums schreibe ich das mal hier rein . Hat mir jemand einen Tipp zur b)? Ich habe mir einige Wörter aufgeschrieben, für die das gilt, erkenne aber kein System /keine Regel, was für diese Wörter gilt.
Re: Aufgabe 10.2
also ich hab mal bis |w| = 4 die wörter aufgeschrieben, die akzeptiert werden: e, abb, bab, bba, aaab, aaba, abaa, baaa
dazu halt noch (leicht ersichtlich): aaaaa, bbbbb
natürlich werden auch all diese wörter mit sich selbst oder mit anderen (ebenso akzeptierten wörtern) konkateniert akzeptiert. also z.b. abb*bab oder bba* aaaaa u.s.w
leider habe ich aber bisher auch kein system erkennen können =((
dazu halt noch (leicht ersichtlich): aaaaa, bbbbb
natürlich werden auch all diese wörter mit sich selbst oder mit anderen (ebenso akzeptierten wörtern) konkateniert akzeptiert. also z.b. abb*bab oder bba* aaaaa u.s.w
leider habe ich aber bisher auch kein system erkennen können =((
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Aufgabe 10.2
Ja, das Problem ist dabei halt auch, dass du immer "Blöcke" einschieben kannst, zum Beispiel bba oder abb usw., da die dich ja immer wieder an dieselbe Stelle führen. Das zu verallgemeinern ist irgendwie merkwürdig und mir nicht ganz schlüssig.
Re: Aufgabe 10.2
also, es ist denke ich so:
es gibt wohl 4 möglichkeiten, ein wort zu generieren: es geht entweder über a) oder b) aus z0 raus und kommt durch a) oder b) wieder rein
nun muss man für diese 4 möglichkeiten schauen, wie sich das verhalten kann. dazu muss man untersuchen, welche (teil)zweige auf jeden fall abgelaufen werden müssen (z.b. das es durch a raus muss und b rein muss), und welche optional sind (diese können dann meist beliebig oft wiederholt werden) äm, ich hoffe man versteht, was ich meine.
Hier mal meine Lösungen, soweit ich momentan bin. Vllt kann man die ja noch weiter zusammenfassen...
es gibt wohl 4 möglichkeiten, ein wort zu generieren: es geht entweder über a) oder b) aus z0 raus und kommt durch a) oder b) wieder rein
nun muss man für diese 4 möglichkeiten schauen, wie sich das verhalten kann. dazu muss man untersuchen, welche (teil)zweige auf jeden fall abgelaufen werden müssen (z.b. das es durch a raus muss und b rein muss), und welche optional sind (diese können dann meist beliebig oft wiederholt werden) äm, ich hoffe man versteht, was ich meine.
Hier mal meine Lösungen, soweit ich momentan bin. Vllt kann man die ja noch weiter zusammenfassen...
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
{ {a} {abb}* {bab}* {bb} }* { {b} {baa}* {bbb} {abb}* {b} }* { {b} {bba}* {b} {bba}* {a} }* { {aba} {b {abb}* ba}* a}*
Re: Aufgabe 10.2
Hallo, Leute! Erster Post Nun, zum Thema: Ich glaube, ich habe die Lösung.
Um nicht zu viel zu verraten, gebe ich euch nur einen kleinen Tipp:
Falls ihr noch mehr braucht, helfe ich gerne weiter
Um nicht zu viel zu verraten, gebe ich euch nur einen kleinen Tipp:
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
Irgendwie ist ein 'a' gleich 3 b's
When we say that two functions are almost always used together, we should remember that "almost" is a euphemism for "not."
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Aufgabe 10.2
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
Danke für deinen Hinweis, aber so ganz viel weiter bin ich damit noch nicht gekommen. Wenn ich diese Regel auf ein Wort aus "Platzhaltersymbolen" anwende, nennen wir sie mal c, dann habe ich ja ganzzahlig vielfache von (ccccc)^i, wobei ich ein c durch ein a oder 3c ersetzen kann. Wenn ich das aber mache, dann bekomme ich unter anderem bbaaaa, was ja offensichtlich nicht in der Sprache liegt.
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
a entspricht bbb, b entspricht aa -> ich nehme ein Wort aus natürlichen vielfachen von (ccccc)^i und c=a oder b. jetzt kann ich a oder b mithilfe der Regel durch bbb bzw. aa ersetzen. So korrekt ?
Re: Aufgabe 10.2
Ich glaube, du hast Recht, obwohl ich nicht genau verstehe was du meinst
Hier meine Denkweise (ohne Platzhalter und so):
Edit: Alternativ (auch formaler, aber ein Stück komplizierter zu verstehen), könnte man sich überlegen was eigentlich f und f* hier sind (ja, die 'Namen' der Zuständen haben eine Bedeutung)
Edit 2: Noch ein wichtiger Hinweis:
Ich habe meine Antwort nicht in der Form L = ...{...}*....
Ich bin auch nicht sicher, ob es überhaupt möglich ist. (oder eher - ob es sinnvoll ist, denn es ergibt sich was langes unde kompliziertes) (es ist durchaus möglich, dass ich mich irre)
Es steht ja in der Aufgabenstellung "Beschreiben Sie die Sprache...", also ich vermute man erwartet auch nicht so eine Darstellung, wie diese oben
Hier meine Denkweise (ohne Platzhalter und so):
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
1. Ein Wort, das nur aus b's besteht, muss 5 (oder 0, oder 10, oder 15, oder 20, also 5n für n - natürlich oder Null) b's enthalten, um akzeptiert zu werden.
2. (Informell!!!!) a = bbb
3. Damit: abb = bbbbb (hat 5 b's, wird also akzeptiert)
4. Längeres Beispiel:
a.a.a.b.a.b.a = bbb.bbb.bbb.b.bbb.b.bbb hat 17 b's - wird nicht akzeptiert
Jetzt mit einem 'a' mehr (egal wo! hier unten ist es am Ende):
a.a.a.b.a.b.a.a = bbb.bbb.bbb.b.bbb.b.bbb.bbb hat 20 b's - wird akzeptiert
(Überprufe selbst, dass es wirklich so ist für die obigen Beispiele, verschiebe bei dem zweiten das 'a' auf verschiedene Stellen im Wort)
5. Wenn man den Zusammenhang findet, so ergibt sich, dass ein Wort genau dann akzeptiert wird, wenn etwas bestimmtes für die Anzahlen von a's und b's gilt (und die Reihenfolge davon ist egal!).
6. Diesen Zusammenhang lasse ich dich alleine finden, sollte nun leicht sein.
(Natürlich kann man äquivalent mit b=aa arbeiten, wird aber eine andere (nicht gleiche, aber trotzdem äquivalente) Antwort bekommen)
2. (Informell!!!!) a = bbb
3. Damit: abb = bbbbb (hat 5 b's, wird also akzeptiert)
4. Längeres Beispiel:
a.a.a.b.a.b.a = bbb.bbb.bbb.b.bbb.b.bbb hat 17 b's - wird nicht akzeptiert
Jetzt mit einem 'a' mehr (egal wo! hier unten ist es am Ende):
a.a.a.b.a.b.a.a = bbb.bbb.bbb.b.bbb.b.bbb.bbb hat 20 b's - wird akzeptiert
(Überprufe selbst, dass es wirklich so ist für die obigen Beispiele, verschiebe bei dem zweiten das 'a' auf verschiedene Stellen im Wort)
5. Wenn man den Zusammenhang findet, so ergibt sich, dass ein Wort genau dann akzeptiert wird, wenn etwas bestimmtes für die Anzahlen von a's und b's gilt (und die Reihenfolge davon ist egal!).
6. Diesen Zusammenhang lasse ich dich alleine finden, sollte nun leicht sein.
(Natürlich kann man äquivalent mit b=aa arbeiten, wird aber eine andere (nicht gleiche, aber trotzdem äquivalente) Antwort bekommen)
Edit 2: Noch ein wichtiger Hinweis:
Ich habe meine Antwort nicht in der Form L = ...{...}*....
Ich bin auch nicht sicher, ob es überhaupt möglich ist. (oder eher - ob es sinnvoll ist, denn es ergibt sich was langes unde kompliziertes) (es ist durchaus möglich, dass ich mich irre)
Es steht ja in der Aufgabenstellung "Beschreiben Sie die Sprache...", also ich vermute man erwartet auch nicht so eine Darstellung, wie diese oben
When we say that two functions are almost always used together, we should remember that "almost" is a euphemism for "not."
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-- David L. Parnas, "Designing Software for Ease of Extension and Contraction"
-
- Beiträge: 34
- Registriert: Do 13. Nov 2008, 16:30
Re: Aufgabe 10.2
Hi,
also ich hab mal einen völlig anderen Ansatz verfolgt. Und zwar habe ich mir angesehen wie viel Zustände der Akzeptor bei a und wie viele er bei b springt. Also habe ich erstmal alle Zustände im Uhrzeigersinn durchnummeriert(geht auch anders herum) und herausgefunden dass a immer 2 weiter und b immer einen zurrück geht. Insgesamt müssen sie aber immer beim Zustand 0 bzw 5 herauskommen...
also war ein Ansatz von mir zb:
m := anzahl der a in dem wort
n := anzahl der b in dem wort
dann muss gelten: (2m-n) div 5 = 1
... aber das ist wohl nur der Algorithmus der sich hinter dem ganzen versteckt... ich denke zumindest mal das so was als Lösung nicht viel taugt.
D.h eine Möglichkeit um die Sprach zu definieren ist alle Möglichkeiten um auf 5 zu kommen aufzuzeigen und dann einen dicken fetten Stern herum.
Ich weiß nur nicht ob nicht eine kontextfreie rechtslineare Grammatik nicht doch um einiges cooler ist...
was mein ihr?
Edit:
Also hab jetzt mal das wohl komplizierteste Beispiel:
und jetzt kann man noch die Nichtterminanten zusammenfassen damit man nicht ganz so viele hat:
weiter gehts nicht, da T als Nichtterminante in T vorkommt und U in U...
also ich hab mal einen völlig anderen Ansatz verfolgt. Und zwar habe ich mir angesehen wie viel Zustände der Akzeptor bei a und wie viele er bei b springt. Also habe ich erstmal alle Zustände im Uhrzeigersinn durchnummeriert(geht auch anders herum) und herausgefunden dass a immer 2 weiter und b immer einen zurrück geht. Insgesamt müssen sie aber immer beim Zustand 0 bzw 5 herauskommen...
also war ein Ansatz von mir zb:
m := anzahl der a in dem wort
n := anzahl der b in dem wort
dann muss gelten: (2m-n) div 5 = 1
... aber das ist wohl nur der Algorithmus der sich hinter dem ganzen versteckt... ich denke zumindest mal das so was als Lösung nicht viel taugt.
D.h eine Möglichkeit um die Sprach zu definieren ist alle Möglichkeiten um auf 5 zu kommen aufzuzeigen und dann einen dicken fetten Stern herum.
Ich weiß nur nicht ob nicht eine kontextfreie rechtslineare Grammatik nicht doch um einiges cooler ist...
was mein ihr?
Edit:
Also hab jetzt mal das wohl komplizierteste Beispiel:
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
G = ({Q, R, S, T, U}, {a,b}, {Q}, P)
P={
Q -> , aS, bU
R -> aT, bQ
S -> aU, bR
T -> aQ, bS
U -> aR, bT
}
wobei halt in wirklichkeit Q für den Startzustand steht, R für 1, S für 2, T für 3, U für 4...
P={
Q -> , aS, bU
R -> aT, bQ
S -> aU, bR
T -> aQ, bS
U -> aR, bT
}
wobei halt in wirklichkeit Q für den Startzustand steht, R für 1, S für 2, T für 3, U für 4...
PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken
P={
Q->, abbQ, bbaQ, aaU, abaT
T-> aQ, baU, bbbQ, bbaT
U->aaT, abQ, bT
}
Q->, abbQ, bbaQ, aaU, abaT
T-> aQ, baU, bbbQ, bbaT
U->aaT, abQ, bT
}
Folge dem und du wirst den Weg der Permutation finden
Re: Aufgabe 10.2
Ihr macht das denke ich etwas zu kompliziert, die Lösung stand eigentlich schon da
eine formale sprache ist definiert durch zb L={a^n b^n | n € N+} (vergebt mir bitte das ich das nicht in latex einprügel ^^)
und wie schon erwähnt wurde müssen die a's und b's zusammen ein vielfaches von 5 ergeben (positiv oder negativ ist egal) wobei a = 2 und b = -1
und wir haben schließlich die Schöne Funktion Na(w) , wenn w = baaa dann Na(w) = 3
von hier ists nurnoch ein kleiner schritt zu der Bedingung für die anzahl der a's und b's in w wie beim obrigen beispiel das n :>
eine formale sprache ist definiert durch zb L={a^n b^n | n € N+} (vergebt mir bitte das ich das nicht in latex einprügel ^^)
und wie schon erwähnt wurde müssen die a's und b's zusammen ein vielfaches von 5 ergeben (positiv oder negativ ist egal) wobei a = 2 und b = -1
und wir haben schließlich die Schöne Funktion Na(w) , wenn w = baaa dann Na(w) = 3
von hier ists nurnoch ein kleiner schritt zu der Bedingung für die anzahl der a's und b's in w wie beim obrigen beispiel das n :>
Re: Aufgabe 10.2
Dann wäre jedoch etwas wieDaniel B. hat geschrieben:Ihr macht das denke ich etwas zu kompliziert, die Lösung stand eigentlich schon da
eine formale sprache ist definiert durch zb L={a^n b^n | n € N+} (vergebt mir bitte das ich das nicht in latex einprügel ^^)
und wie schon erwähnt wurde müssen die a's und b's zusammen ein vielfaches von 5 ergeben (positiv oder negativ ist egal) wobei a = 2 und b = -1
und wir haben schließlich die Schöne Funktion Na(w) , wenn w = baaa dann Na(w) = 3
von hier ists nurnoch ein kleiner schritt zu der Bedingung für die anzahl der a's und b's in w wie beim obrigen beispiel das n :>
Code: Alles auswählen
L={a^n b^m | n, m ∈ ℕ⁺}
¿ɯıɥ ssɐɹɹɐqɯǝ ʎɥʍ 'ʇou s,ʇı ɟı — noʎ llǝʇ ll,ǝɥ 'ɔɐɯ ɐ s,ʇı ɟı — sǝsn ǝɥ so ʇɐɥʍ uɐɯ ɐ ʞsɐ ɹǝʌǝu