Aufgabe 10.2

[Christian S.]

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.

[Chrisor]

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 =((

[Christian S.]

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.

[ryo]

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...

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}*

[SLS]

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:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Irgendwie ist ein 'a' gleich 3 b's

Falls ihr noch mehr braucht, helfe ich gerne weiter

[Christian S.]

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.

Edit: Denkfehler meinerseits:

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 ?

[SLS]

Ich glaube, du hast Recht, obwohl ich nicht genau verstehe was du meinst

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)

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

[CansaSCity]

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:

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...

und jetzt kann man noch die Nichtterminanten zusammenfassen damit man nicht ganz so viele hat:

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
}

weiter gehts nicht, da T als Nichtterminante in T vorkommt und U in U...

[Daniel B.]

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 :>

[DaVinci]

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 :>

Dann wäre jedoch etwas wie

Code: Alles auswählen

L={a^n b^m | n, m ∈ ℕ⁺}

richtiger, denk ich.