3. Automaten Konstruktion

Automaten Konstruktion

  • V

    Hey Leute!

    Ich hab hier wieder eine Sprache aus der ich einen Automaten konstruieren will.

    L = {1n 0m | n, m aus N und (n+m) mod2 = 0}

    Die hintenstehenden "Eigenschaften" deute ich so:

    der erste Teil: Potenzen sind Element der natürlichen Zahlen
    der zweite Teil: Summe der Potenzen muss gerade durch 2 teilbar sein

    Wie ich hier aber nun einen Automaten zeichnen soll ist mir leider nach wie vor ein ziemliches Rätsel. Könnt ihr mir helfen?

    0
  • O

    probiers selbst aus. was sind deine Ansätze?

    Wir machen heir garantiert nicht alle deine Hausaufgaben.

    Ist übrigens sehr einfach. Kriegste sicherlich hin.

    0
  • V

    Wie ich hier schon ein paar Mal gesagt habe, WILL ich SICHERLICH NICHT, dass IHR meine Hausuafgaben macht. Dafür hab ich schon zu viele Threads erstellt, indem ich das Gegenteil bewiesen habe und mich sehr ausführlich und immer wieder mit der Thematik beschäftigt habe. Wollt ich nur mal klarstellen...

    Meiner Ansicht nach gibt es keinen Automaten der diese Sprache akzeptiert, da es immer wieder eine neue Potenz gibt die %2-teilbar ist. Aber irgendwas lässt mich daran dennoch zweifeln, denn die Aufgabenstellung gibt nicht darüber Auskunft, dass es keinen Automaten geben soll.

    Also wie gesagt über etwas (mehr) Hilfe würde ich mich sehr freuen!

    0
  • V

    Wenn ich nun z.B. für n=2 und für m=2 wähle, dann lässt sich die Summe, also n+m=4 -> 4%2=0, gerade durch 2 teilen. Da aber nun n, m aus N kommen und dieser Zahlenbereich ja nicht nach oben beschränkt ist, finde ich immer wieder Zahlen für n und m die %2=0 sind. Meiner Anstich nacht gibt's dann eine unendlich Zustandsanzahl des evlt. resultierenden Automaten; und genau das kann man mit keinem Automaten realisieren, was dazu führt, dass die obige Sprache L nicht regulär sein kann...

    0
  • V

    vip@r schrieb:

    Hey Leute!

    Ich hab hier wieder eine Sprache aus der ich einen Automaten konstruieren will.

    L = {1n 0m | n, m aus N und (n+m) mod2 = 0}

    Die hintenstehenden "Eigenschaften" deute ich so:

    der erste Teil: Potenzen sind Element der natürlichen Zahlen
    der zweite Teil: Summe der Potenzen muss gerade durch 2 teilbar sein

    Wie ich hier aber nun einen Automaten zeichnen soll ist mir leider nach wie vor ein ziemliches Rätsel. Könnt ihr mir helfen?

    Ich deute das als
    Entweder gerade Anzahl von 1 UND danach gerade Anzahl von 0.
    Oder ungerade Anzahl von 1 UND danach ungerade Anzahl von 0.

    Also erstmal einen Wackler an den Anfang.
    q0: 1->q1 //gerade 1-Anzahl
    q1: 1->q0 //ungerade 1-Anzahl

    Jo, wenn eine 0 kommt, gehts in die zweite Stufe
    q0: 0->q2 1->q1 //gerade 1-Anzahl
    q1: 0->?? 1->q0 //ungerade 1-Anzahl
    q2: 0->q3 1->qe //gerade 1-Anzahl und ungerade 0-Anzahl
    q3: //gerade 1-Anzahl und gerade 0-Anzahl
    q4: ...
    qe: 0->qe 1->qe //Fehler, Fehler, Fehler
    und ein wenig Tüfteln.
    Und dann nochmal nachdenken, ob man wirklich 7 Zustände braucht. *grübel* Keine Ahnung.

    Vielleicht ist es besser, es zu verstehen als
    Erst lauter Einsen, dann lauter Nullen
    UND
    die Gesamtzahl muß gerade sein.

    q0: 0->q2 1->q1 //Sind noch bei den Einsen und gerade Gesamtzahl
    q1: 0->?? 1->q0 //Sind noch bei den Einsen und ungerade Gesamtzahl
    q2: 0->q3 1->qe //Sind schon bei den Nullen und ungerade Gesamtzahl
    ...
    Ja, sieht besser aus. 5 Zustände?

    0
  • V

    Ich deute das als
    Entweder gerade Anzahl von 1 UND danach gerade Anzahl von 0.
    Oder ungerade Anzahl von 1 UND danach ungerade Anzahl von 0.

    Wenn du von entweder oder sprichst, sollte dann in den Eigenschaften nicht ein oder stehen? Bei mir in der Aufgabenstellung steht für das und übrigens das Zeichen für das "logische Und".

    0
  • O

    volkard hat in der Aussage den modulus zerlegt. ließ mal genauer.

    Ich habe nebenbei in deinen Threads nicht den Eindruck, dass du dir so viel Mühe gibst. Eher: ich sehe nicht sofort eine Lösung, also gehts nicht.

    Und dabei ists doch so einfach: du konstruierst einen Automaten der 0^n 1^m erkennt und einen Automaten der prüft, ob die Eingabelänge gerade ist. Und dann schneidest du die Automaten nach Vorlesungskonstruktion. That's all 🙄

    0
  • V

    Ich soll also einen Automaten erstellen, der 0^n 1^m erkennt. Aber genau das geht doch nicht weil unendlich große Zustandsanzahl, oder?

    0
  • O

    schleifen?

    0
  • V

    Mein Versuch für 0^n 1^n.

    http://imageshack.us/photo/my-images/806/29383151.jpg/

    0
  • V

    vip@r schrieb:

    Mein Versuch für 0^n 1^n.
    http://imageshack.us/photo/my-images/806/29383151.jpg/

    lol
    Dein Automat ist eine Münze.

    Außerdem war 0^n 1^m gemeint.

    Vielleicht so.
    q0: 0->q0 1:q1 //bisher nur nullen gelesen
    q1: 0->qe 1:q1 //auch einsen gelesen
    qe: 0->qe 1:qe //fehler
    q0 und q1 akzeptieren. Start bei q0.

    Bisher war bei Deinen Beispielen schön mlglich, den Zuständen einen Beschreibungstext zu geben, der klar macht, was der Zustand bedeutet. Vielleicht versuchst Du das auch mal.

    Und laß pro Pfeil nur ein Zeichen zu und pro Zustand nur zwei ausgehende Pfeile.
    Falls mal zufällig zwei Pfeile die selben Start- und Zielknoten haben, kannste immernoch prof-mäßig zusammenfassen. Oder es erstmal lassen.

    0
  • Z

    vip@r schrieb:

    Mein Versuch für 0^n 1^n.

    http://imageshack.us/photo/my-images/806/29383151.jpg/

    Nein. Ich habe mich jetzt zwar nicht komplett reingedacht. Aber auf den ersten Blick und keine weiteren -> Der Automat akzeptiert Wörter, die er nicht akzeptieren sollte.

    Du solltest dir beim Konstruieren von Automaten nicht nur darüber Gedanken machen, dass die richtigen Wörter akzeptiert werden, sondern auch darüber, dass die "falschen" Wörter nicht akzeptiert werden.

    Volkards Denkanstoß hat eigentlich schon ziemlich viel gesagt... Wenn er etwas mit 5 Zuständen meint, dann kann es gut sein, dass du es mit zweien nicht schaffst...

    0
  • V

    vip@r schrieb:

    Ich soll also einen Automaten erstellen, der 0^n 1^m erkennt. Aber genau das geht doch nicht weil unendlich große Zustandsanzahl, oder?

    Steht das so im Skript? Nee. Da steht mit dieser Argumentation, daß 0^n 1^n nicht geht.

    0
  • V

    0
  • V

    Nochmal ein Versuch: http://imageshack.us/photo/my-images/38/44887530.jpg/

    0
  • V

    vip@r schrieb:

    Nochmal ein Versuch: http://imageshack.us/photo/my-images/38/44887530.jpg/

    Der spring bei jedem beliebigen Zeichen und beim nächsten Zeichen wieder nach rechts und immer hin und her.
    Er landet bei einer geraden Anzahl von gelesenen Zeichen auf dem rechten Zustand.

    (rechts ist, wo der Daum,en links ist. Evtl steht das Bild auf dem Kopf)

    0
  • V

    ja eben und das soll er doch oder?

    0
  • V

    hm, irgendwie hab ich momentan überhaupt nicht das gefühl, das ich was verstehe. vielleicht hat jemand lust und vor allem auch zeit ein paar (einfache) sprachen zu posten zu denen ich dann den automat zeichen. sollte doch auch umgekehrt funktioniere, oder?

    0
  • V

    Ich glaub ich hab schon das Problem, dass ich gar nicht wirklich weiß wie ich bei einem gegebenen Automatengraphen weiß, wie man da ein gegebenes Wort wie z.B. 0011 durchgeht. Kann mir das jemand erklären?

    0
  • V

    Hey Leute!

    Ich hab mir nochmal Gedanken zu obiger Aufgabe gemacht.

    Das letzte Bild das ich gepostet habe war ja eigentlich ein Automat der die Sprache L = {w aus Σ*Bool | |w| mod 2 = 0} erkennt. Das heißt ich hätte ja jetzt quasi schon einen Automat der gerade Wortlänge erkennt.

    Und jetzt bräuchte ich eben noch einen Automaten der die Sprache L = {w aus Σ*Bool | 1* 0*} erkennt. Aber so einen gibt's wieder nicht, oder?

    Falls doch, könnte man ja jetzt einen Produktautomaten aus beiden Sprachen bauen und wäre fertig, oder?

    0
Anmelden zum Antworten