Endlicher Automat ohne Ausgabe

Von: , Frage gestellt am Sa, 4. Jul 2009

Guten Tag,

ich muss einen endlichen Automaten ohne Ausgabe konstruieren der die Sprache L(alpha) = {w ; w enthält nach jeder 2 mindestens zweimal die 1 UND nach jeder 4 mindestens dreimal die 3} Eingabealphabet = {1,2,3,4}

Mit der Eingabe von 2,1,1,4,3,3,3 würde ich auf „kürzestem Wege“ den Endzustand erreichen, oder?
Ich bin total verunsichert ob nur diese Eingabekette akzeptiert wird, und alle anderen Eingaben in den Zustand „Fehler führen“!
Welcher Zustand wird erreicht wenn ich 2,1,1,3 eingebe?

Welcher Zustand tritt ein wenn vom Anfangszustand die Eingabe 1 mache?
Sehe ich es richtig, dass es insgesamt acht Zustände und einen „Fehlerzustand“ gibt?


Mit einer Zustandstafel wäre mir super geholfen. Dann könnte ich den Graphen daraus ableiten. Aber eine Antwort auf o.g. Fragen bringt mich sicher auch schon sehr viel weiter!

Vielen Dank im Voraus!

Michael

10 Antworten zu dieser Frage

1. Antwort von nach 7 Stunden 0 hilfreich

   Re: Endlicher Automat ohne Ausgabe

   Hallo Michael,
   
   endliche Automaten, wie schön. :-) L(alpha) = {w ; w enthält nach jeder 2 mindestens zweimal die 1 UND nach jeder 4 mindestens dreimal die 3}
   (Die Beschreibung ist schon mehrdeutig; ich nehme mal an, dass "nach" bedeuten soll, dass ein solcher Einer- bzw. Dreierblock direkt auf jede 2 oder 4 folgt.) Eingabealphabet = {1,2,3,4}
   Mit der Eingabe von 2,1,1,4,3,3,3 würde ich auf „kürzestem
   Wege“ den Endzustand erreichen, oder?
   Nein. Überleg mal, ob ein Wort auch dann noch zur Sprache gehört, wenn z.B. gar keine 2 auftaucht. (Und dann denk mal an das Leerwort.) Ich bin total verunsichert ob nur diese Eingabekette
   akzeptiert wird
   Nein, die Sprache L enthält unendlich viele Wörter. Zum Beispiel gehört "133111211311313134333333311111131211113111313143331" dazu und noch längere. Schreib dir mal ein paar Beispiele auf (und ein paar Gegenbeispiele, also Wörter, die nicht zu L gehören, z.B. "433"). Welcher Zustand wird erreicht wenn ich 2,1,1,3 eingebe?
   "2113" gehört zu L, muss also akzeptiert werden. Welcher Zustand tritt ein wenn vom Anfangszustand die Eingabe
   1 mache?
   Dann musst du in einem akzeptierenden Zustand landen; denn "1" ist Element von L.
   
   Viele Grüße
   
   Andreas
   

   • Antwort von nach 22 Stunden 0 hilfreich

     Re^2: Endlicher Automat ohne Ausgabe

     Hallo Andreas,
     
     danke schon mal für die ersten Anregungen! (Die Beschreibung ist schon mehrdeutig; ich nehme mal an, dass
     "nach" bedeuten soll, dass ein solcher Einer- bzw. Dreierblock
     direkt auf jede 2 oder 4 folgt.)
     Ja mehrdeutig, leider. Das mit den Blöcken ist korrekt. Das UND aus der Beschreibung ist somit kein logisches UND? Also es müssen nicht beide Bedingungen erfüllt sein? Das wäre eine wichtige Erkenntnis!
     
     
     Nein. Überleg mal, ob ein Wort auch dann noch zur Sprache
     gehört, wenn z.B. gar keine 2 auftaucht. (Und dann denk mal an
     das Leerwort.)
     Also wäre z.B. 4333 eine korrekte Eingabe die zur Sprache L gehört und in den Endzustand führt? Genau wie 211, was dann auch die kürzeste Eingabekette wäre um den Endzustand zu erreichen.
     
     
     Schreib dir mal ein paar Beispiele auf (und ein
     paar Gegenbeispiele, also Wörter, die nicht zu L gehören, z.B.
     "433").
     13211, 134333, 1331211 sind z.B ok.
     Wobei:
     1213, 3212, 4332 z.B. nicht ok sind.
     
     Wenn ich das dann so betrachte habe ich die Zustände S0 bis S7 sowie einen Fehlerzustand. Und die beiden kürzesten Möglichkeiten splitten sich vom Anfangszustand sozusagen auf. Einmal die Variante 4333 und 211. Meine Eingabe kann mit z.b 13 beginnen, dies wird auch akzeptiert, aber um den Endzustand zu erreichen muss eine Kette endweder mit 211 oder 4333 enden. Ich hoffe da liege ich richtig!?
     
     
     Viele Grüße
     
     Michael
     

     • Antwort von nach 23 Stunden 0 hilfreich

       Re^3: Endlicher Automat ohne Ausgabe

       Hallo Michael, Das UND aus der Beschreibung ist somit kein logisches UND? Also es
       müssen nicht beide Bedingungen erfüllt sein?
       doch, natürlich ist das ein logisches UND; so habe ich es auch interpretiert. Du musst nur beachten, dass die beiden durch UND verbundenen Aussagen allquantifiziert sind: Die Bedingung für die 2 ist also auch erfüllt, wenn gar keine 2 im Wort enthalten ist. Also wäre z.B. 4333 eine korrekte Eingabe die zur Sprache L
       gehört und in den Endzustand führt?
       Korrekt. Genau wie 211, was dann auch die kürzeste Eingabekette wäre um den Endzustand zu erreichen.
       Nein, kürzer und auch in L wären noch "11", "13", "31", "33", "1", "3" und "" (das Leerwort!). 13211, 134333, 1331211 sind z.B ok.
       Wobei: 1213, 3212, 4332 z.B. nicht ok sind.
       Ja. Meine Eingabe kann mit z.b
       13 beginnen, dies wird auch akzeptiert, aber um den Endzustand
       zu erreichen muss eine Kette endweder mit 211 oder 4333 enden.
       Ich hoffe da liege ich richtig!?
       Hmm; da stimmt entweder irgendetwas in deiner Vorstellung nicht, oder wir legen unterschiedliche Varianten von endlichen Automaten zugrunde: Dass ein Wort vom Automaten "akzeptiert" wird, heißt doch gerade, dass sich der Automat nach Eingabe des Wortes in einem Endzustand befindet, der als erfolgreich/akzeptierend gekennzeichnet ist.
       
       Andreas
       
       PS: Ich habe mir gerade mal einen passenden Automaten skizziert: Ich komme mit 6 Zuständen (+ einem Fehlerzustand) aus.
       

       • Antwort von nach einem Tag 0 hilfreich

         Re^4: Endlicher Automat ohne Ausgabe

         Hallo Andreas, doch, natürlich ist das ein logisches UND; so habe ich es auch
         interpretiert. Du musst nur beachten, dass die beiden durch
         UND verbundenen Aussagen allquantifiziert sind: Die Bedingung
         für die 2 ist also auch erfüllt, wenn gar keine 2 im
         Wort enthalten ist.
         Ahso, bis hierher war ich davon ausgegangen, dass auch tatsächlich die 2 (oder 4) im Wort enthalten sein muss. Nein, kürzer und auch in L wären noch "11", "13", "31", "33",
         "1", "3" und "" (das Leerwort!).
         Dann ist mir das auch klar! Hmm; da stimmt entweder irgendetwas in deiner Vorstellung
         nicht, oder wir legen unterschiedliche Varianten von endlichen
         Automaten zugrunde: Dass ein Wort vom Automaten "akzeptiert"
         wird, heißt doch gerade, dass sich der Automat nach Eingabe
         des Wortes in einem Endzustand befindet, der als
         erfolgreich/akzeptierend gekennzeichnet ist.
         Ich denke eher in meiner Vorstellung....aber langasam erschließt es sich. Ich gebe eine 1 ein, habe die Bedingungen erfüllt weil keine 2 oder 4 eingegeben wurde, und damit ist die Eingabe akzepiert = Endzustand. Soweit sehr gut!
         
         Aber: PS: Ich habe mir gerade mal einen passenden Automaten
         skizziert: Ich komme mit 6 Zuständen (+ einem Fehlerzustand)
         aus.
         Hmm, inklusive Anfangszustand? Da steh ich noch auf dem Schlauch!
         Wenn: L(alpha) = {w ; w enthält nach jeder 2 mindestens zweimal die 1 UND nach jeder 4 mindestens dreimal die 3} Eingabealphabet = {1,2,3,4}
         
         MIT Anfangszustand benötige ich dann 7 Zustande + 1 Fehlerzustand.
         
         Für ein kleineres Beispiel:
         L = {w; w= nach jeder 3 mindestens zwei mal die 2} E={1,2,3}
         Dann brauche ich inklusive Anfangszustand 4 Zustände + Fehlerzustand.
         
         
         Michael
         

         • Antwort von nach einem Tag 0 hilfreich

           Re^5: Endlicher Automat ohne Ausgabe

           Hallo, Für ein kleineres Beispiel:
           L = {w; w= nach jeder 3 mindestens zwei mal die 2} E={1,2,3}
           Dann brauche ich inklusive Anfangszustand 4 Zustände +
           Fehlerzustand.
           ich würde meinen Automaten mit 3 + 1 Zuständen so bauen:
           
           Zustände: S_0, S_1, S_2, S_F
           Startzustand: S_0
           akzeptierende Zustände: S_0
           Übergänge:
           

           S_0 --1,2--> S_0
           S_0 --3----> S_1
           S_1 --2----> S_2
           S_2 --2----> S_0
           + sonstige nach S_F
           

           
           Andreas
           

           • Antwort von nach einem Tag 0 hilfreich

             Re^6: Endlicher Automat ohne Ausgabe

             Hallo, ich würde meinen Automaten mit 3 + 1 Zuständen so bauen:
             
             Zustände: S_0, S_1, S_2, S_F
             Startzustand: S_0
             akzeptierende Zustände: S_0
             Übergänge:
             

             S_0 --1,2--> S_0
             S_0 --3----> S_1
             S_1 --2----> S_2
             S_2 --2----> S_0
             + sonstige nach S_F
             

             
             Andreas
             Verstehe, für mich war S_0 nicht Endzustand sondern nur Startzustand. Darum brauche ich immer einen Zustand mehr, eben S_3 als Endzustand. Aber deshalb wäre das doch sicher nicht falsch? Sinvoller ist bestimmt deine Variante, keine Frage.
             
             Wenn man es nach meiner "Strategie" auch machen kann, dann sage ich vielen vielen Dank für die Hilfe und Mühe!! Denn da hat sch heute echt was erschlossen!
             
             Michael
             

           • Antwort von nach einem Tag 0 hilfreich

             Re^7: Endlicher Automat ohne Ausgabe

             Verstehe, für mich war S_0 nicht Endzustand sondern nur
             Startzustand. Darum brauche ich immer einen Zustand mehr, eben
             S_3 als Endzustand. Aber deshalb wäre das doch sicher nicht
             falsch?
             Dann zeig doch mal deinen Automaten her; dann sage ich dir, ob er die gleiche Sprache akzeptiert wie meiner. :-)
             
             Andreas
             

           • Antwort von nach einem Tag 0 hilfreich

             Re^8: Endlicher Automat ohne Ausgabe

             Dann zeig doch mal deinen Automaten her; dann sage ich dir, ob
             er die gleiche Sprache akzeptiert wie meiner. :-)
             L = {w; w= nach jeder 3 mindestens zwei mal die 2} E={1,2,3}
             Anfangszustand= S_0
             Endzustand= S_3
             
             S_0--1,2-->S_3
             S_0--3---->S_1
             S_1--2---->S_2
             S_2--2---->S_3
             S_3--1,2-->S_3
             S_3--3---->S_1
             
             S_1--1,3-->S_F
             S_2--1,3-->S_F
             
             Für das "große" Beispiel:
             L(alpha) = {w ; w enthält nach jeder 2 mindestens zweimal die 1 UND nach jeder 4 mindestens dreimal die 3} Eingabealphabet = {1,2,3,4}
             Anfangszustand= S_0
             Endzustand= S_3
             
             S_0--1,3-->S_3
             S_0--3---->S_1
             S_1--2---->S_2
             S_2--2---->S_3
             S_0--4---->S_4
             S_4--1---->S_5
             S_5--1---->S_6
             S_6--1---->S_3
             S_3--1,3-->S_3
             S_3--4---->S_4
             S_3--3---->S_1
             und sonstige nach S_F
             
             Was meinst du?
             
             Michael
             

           • Antwort von nach einem Tag 0 hilfreich

             Re^9: Endlicher Automat ohne Ausgabe

             Für das "große" Beispiel:
             L(alpha) = {w ; w enthält nach jeder 2 mindestens zweimal die
             1 UND nach jeder 4 mindestens dreimal die 3} Eingabealphabet =
             {1,2,3,4}
             Hier ist mir ein Fehler unterlaufen!!!! SORRY!!!
             
             Es muss heißen: L(alpha) = {w ; w enthält nach jeder 3 mindestens zweimal die 2 UND nach jeder 4 mindestens dreimal die 1} Eingabealphabet = {1,2,3,4}
             Dann passt es auch mit den übergängen der Zustände. Anfangszustand= S_0
             Endzustand= S_3
             
             S_0--1,3-->S_3
             S_0--3---->S_1
             S_1--2---->S_2
             S_2--2---->S_3
             S_0--4---->S_4
             S_4--1---->S_5
             S_5--1---->S_6
             S_6--1---->S_3
             S_3--1,3-->S_3
             S_3--4---->S_4
             S_3--3---->S_1
             und sonstige nach S_F
             
             Was meinst du?
             
             Michael
             

• « Zurück
• 1
• 2
• Vorwärts »

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!