Info08.de - Forum des Erstsemester Jahrgangs 2008

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.

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

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.

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

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

Edit: Denkfehler meinerseits:

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

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

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

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

Dann wäre jedoch etwas wie richtiger, denk ich.