Hallo! Eine Frage:
{a,b}* - heißt das so wie "abab" oder "aaaaabbbbbb"?
ich glaub das heißt, dass in der menge a und b drin sind und man beliebig oft rausnehmen darf?
ababab.. wäre wohl (ab)* oder so - ähnlich geschrieben?
aaaaabbbbb mit beliebig vielen a's und b's wäre dann glaub ich a*b*
du glaubst nicht nur, du weisst, dennis!
Moinsen,
also muss die Maschiene Wörte wie z.B. aabbaaabbabb annehmen? Immer gleich viele a wie b müssen enthalten sein, die reihenfolge ist jedoch egal.
Hab ich das so richtig verstanden??
Gruß und danke!
joa so war mein erster satz gemeint.. beispiel vergessen^^
es sollte also auch "", "a" oder "b" akzeptiert werden. beliebig lange wörter mit beliebig vielen as und bs halt :)
edit:
Immer gleich viele a wie b müssen enthalten sein
ne - beides beliebig
"aa" geht, "aabaa" auch etc
Ups ich war schon in der Aufgabe 2 vom Aufgabenzettel:
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe07/aufg13.pdfDa müssen ja gleich viele a wie b sein damit die Sprach von dem Automaten akzeptiert wird.
Kann mir evtl. jmd n Tipp zu der Aufgabe geben?
also bevor keiner antwortet..
ich vermute mal, man kann sich überlegen, wie die wörter aussehen, die akzeptiert werden?
"ab" "aabb", aber auch "aababb", "bbaa" etc
jetzt würde ich versuchen alle "bausteine" dieser wörter einzeln zu "odern".
aber da auch "sehr viele" bs gefolgt von eben genau so vielen as erlaubt sind, würde man "sehr viele" bausteine brauchen? mhm ka
ne grammatik, die sowas erzeugt wäre doch
S -> C
C -> aB, Ba, bA, Ab, ""
A -> CaC
B -> CbC
oder nicht? seh gerad kein gegenbeispiel.. evtl sind die vielen Cs auch overkill ;)
btw "genauso viele a wie b" findet sogar google :>
Hm ja an sowas hatte ich auch gedacht.
Was ich aber leider überhaupt nicht weiß ist wo dieses Wort auftritt.
Soll das auf dem Turingband stehen?
Und dann wird das durchlaufen und nach as und bs gesucht bis alle sgefunden wurden und dann mit eccept beendet wird?
Naja danke nochmal ich werds ma weiter googlen und suchen.
Zu doof, dass ich in FGI noch die 3,5 Punkte brauche :(
Der Stern hat eine höhere Präzedenz als die Klammern. Also ersetzt Du {a, b}* zunächst einmal durch beliebig viele {a, b}s:
{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}{a, b}…
Und jetzt darfst Du Dich an jeder Stelle entscheiden, ob Du a oder b nehmen möchtest. Es wird also jedes Wort akzeptiert, das ausschliesslich aus den ersten beiden Buchstaben des Alphabets besteht (auch das leere Wort).
Wer seine Turingmaschine testen möchte, für den ist der Link ganz interessant:
http://wap03.informatik.fh-wiesbaden.de/weber1/turing/tm.html da kommt man aus dem Spielen gar nicht mehr raus ^^
ne grammatik, die sowas erzeugt wäre doch
S -> C
C -> aB, Ba, bA, Ab, ""
A -> CaC
B -> CbC
oder nicht? seh gerad kein gegenbeispiel..
Ja, die ist richtig.
evtl sind die vielen Cs auch overkill ;)
Ja, man kann das abkürzen zu S -> aSbS | bSaS | "".
