Endlicher Automat ohne Ausgabe

Wissenschaft Informatik
#1

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

#2

Hallo Michael,

endliche Automaten, wie schön. :smile:

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

#3

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

#4

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.

#5

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

#6

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

#7

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

#8

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

Andreas

#9

Dann zeig doch mal deinen Automaten her; dann sage ich dir, ob
er die gleiche Sprache akzeptiert wie meiner. :smile:

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

#10

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

#11

Hi,

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}

ok, also mit vertauschten Rollen. Dann müsste hier aber statt bei „1,3“ der Übergang bei „1,2“ stattfinden.

S_0–1,3–>S_3
S_3–1,3–>S_3

Ansonsten sehen deine Automaten gut aus, bis auf eine Kleinigkeit: Sie akzeptieren das Leerwort nicht. Das kannst du beheben, indem du S_0 auch zum Endzustand machst. Dann sind S_0 und S_3 aber äquivalent und du kannst sie zu einem Zustand vereinigen; dann kommt genau mein Automat heraus.

Viele Grüße

Andreas