Sprachproblem: Verständnis
-
Hey ho!
Hab hier diese Sprache gegeben:
L = {1n 0m | n,m in Σ*Bool Λ n+m%2=0}
Ich verstehe nun nicht ganz wie das n+m%2=0 gemeint ist. Meint der Ausdruck nun das hier: n+(m%2)=0, oder das hier: (n+m)%2=0. Ich gehe aber mal davon aus, dass die erste Variante gemeint ist, da der Modulo-Operator doch unter Programmiersprachen als auch in der Mathematik als Punkt-Rechnung behandelt wird.
Wie versteht ihr das?
Das würde ja dann bedeuten, dass der Ausdruck nur dann Null wird, wenn n=0 und m%2=0 was ja auch nur der Fall ist wenn m=0 ist. Nur dann würde der Automat akzept., oder?
-
-.-
-
Was bedeutet -.-?
-
Ich würde von (n+m)%2 ausgehen, wenn du nicht gerade nen Aufgabensteller hast, der sich besonders schlau vorkommen will. Denn ansonsten ist der Ausdruck unnötig kompliziert, wie du ja schon erkannt hast.
-
Für den Ausdruck (n+m)%2=0 hab ich hier schon mal einen Automat gebaut. Ist der so richtig http://imageshack.us/photo/my-images/198/30410220.jpg/?
-
Hm, shit. Ich hab leider bei der Sprache einen Fehler gemacht. So lautet sie richtigerweise:
L = {1n 0m | n,m in N Λ n+m%2=0}
Also kommen n und m aus den natürlichen Zahlen. Dann sollte doch der Automat für den Ausdruck n+(m%2)=0 gar nicht mehr so schwierig sein, oder? Der Automat erkennt doch dann eigentlich nur gerade Anzahl von Nullen. Der Ausdruck gleich Null wird ja nur Null wenn auf jeden Fall mal n=0 ist.
Stimmt doch so oder?
-
Nein, der akzeptiert 0011.
-
vip@r schrieb:
Also kommen n und m aus den natürlichen Zahlen.
Wenn das für dich nicht dasselbe ist, was meinst du dann, was 1^n mit n in Σ*Bool bedeutet?
Dann sollte doch der Automat für den Ausdruck n+(m%2)=0 gar nicht mehr so schwierig sein, oder? Der Automat erkennt doch dann eigentlich nur gerade Anzahl von Nullen. Der Ausdruck gleich Null wird ja nur Null wenn auf jeden Fall mal n=0 ist.
Stimmt doch so oder?
Weshalb ich gemeint habe, dass die Klammerung anders gemeint ist.
-
Weshalb ich gemeint habe, dass die Klammerung anders gemeint ist.
Du meinst also, dass die Klammerung so gemeint war: (n+m)%2=0.
Falls ja, dann haben wir aneinander vorbei geredet. Der Automat von mir für dies Klammerung ist aber anscheinend falsch, weil er auch 0011 erkennt.
-
vip@r schrieb:
Der Automat von mir für dies Klammerung ist aber anscheinend falsch, weil er auch 0011 erkennt.
Nicht nur das. Er akzeptiert z. B. auch 100110.
-
Hm, dann is der Automat wohl schon wieder mal völliger Unsinn... Wie soll ich da dann weiter rangehen? Ich muss halt irgendwie sicherstellen, dass der Automat am Anfang nur Einser liest und danach nur Nullen. Und dann muss ich eben noch reinbringen, dass der Automat entweder bei gleicher anzahl ungerader Nullen und Einsen sowei bei unterschiedlicher Anzahl an Einsen und Nullen aber gerader Summe und bei Einsen und Nullen gerade Anzahl akzept. Leichter gesagt als getan...
-
vip@r schrieb:
Und dann muss ich eben noch reinbringen, dass der Automat entweder bei gleicher anzahl ungerader Nullen und Einsen sowei bei unterschiedlicher Anzahl an Einsen und Nullen aber gerader Summe und bei Einsen und Nullen gerade Anzahl akzept. Leichter gesagt als getan...
Erstens: Nullen können nicht ungerade sein.
Zweitens: Warum drückst du dich so kompliziert aus? Die Gesamtwortlänge soll gerade sein.
-
Ja, wenn nur die Gesamtwortlänge gerade sein soll, dann ist das ja weniger Problem als ich hier vermutet habe. Dann sollte es ja ein Automat der nur gerade Wortlänge erkennt tun. Aber: So ein Automat erkennt ja dann auch 010010, was aber doch laut Sprache gar nicht existieren kann, oder?
-
Du hast einen Automaten, der gerade Wortlängen erkennt. Außerdem hast du afair noch einen Automaten für 1*0* rumliegen. Also brauchst du nur noch die Schnittmenge aus beidem zu bilden und hast einen neuen Automaten für diese Sprache.
-
Außerdem hast du afair noch einen Automaten für 1*0* rumliegen.
Hab ich das wirklich?
Aber danke für die Hilfe. Jetzt weiß ich ja wie man da drauf kommen könnte.
-
Hm, Sorry, aber wie sieht denn ein 1*0* Automat aus? Der müsste doch wieder eine unendliche Anzahl an 1 und eine unendliche Anzahl an 0 erkennen, oder?
-
Ich bin mir ziemlich sicher, daß wir den schonmal irgendwo hier hatten. Aber ich versuch's trotzdem nochmal:
-> [u]A[/u] -0-> [u]B[/u] -1-> C ( ) ( ) 1 0
-
vip@r schrieb:
Hm, Sorry, aber wie sieht denn ein 1*0* Automat aus? Der müsste doch wieder eine unendliche Anzahl an 1 und eine unendliche Anzahl an 0 erkennen, oder?
Was meinst du damit? Meinst du, dass Wörter beliebig viele (nicht unendlich viele) Nullen und Einsen beinhalten können? Wenn ja: Wo ist das Problem?
-
CStoll: Dein Automat verwirft 1^n, n in |N_0.
-
Meinst du, dass Wörter beliebig viele (nicht unendlich viele) Nullen und Einsen beinhalten können?
Genau das meinte ich; ich hab anscheinend bloß grad das Wort unendlich im falschen Kontext benutzt...
-> A -0-> [u]B[/u] ( ) ( ) 1 0Ich geh mal davon aus, dass das B akzept. sein soll, oder?
