Darstellung einer Zahl als Dreierpotenz zur Basis 3 bei determistischen endlichen Automaten

Question

Aufgabe:

Entwerfen Sie zu jeder der folgenden Sprachen einen DEA, der diese Sprache akzeptiert. Begründen Sie kurz dessen Korrektheit:

(a) \( L_{1}=\{w \in\{0,1,2\}^{*} | w \text { ist die Darstellung zur Basis 3 einer Dreierpotenz} \} \)

(b) \( L_{2}=\left\{w \in\{ ◊, ♥, ♠ \}^{*} | \text { nach jedem } ◊\text { kommt mindestens ein } ♥ \text { oder ein } ♠ \right\} \)

Meine Frage bezieht sich zu Aufgabe a) Welche Zustände müsste der Automat abdecken? Kann mir jemand einen Hinweis auf die Dreierpotenz Basis 3 geben? Was eine Dreierpotenz ist, weiss ich. Nur kann ich nichts mit der Basis anfangen.

Answer 1

der Automat, der die Sprache \( L_1 \) akzeptiert, besteht aus drei Zuständen. Ich glaub', ich mal's doch mal hin, dann brauch' ich's nicht zu beschreiben:

Er basiert auf dem Prinzip, dass in einem b-adischen Zahlensystem, eine Potenz von b die Darstellung "1000...0" hat.

Der zweite Automat, der ja die \( L_2 \) repräsentieren soll, ist ähnlich einfach zu zeichnen (als Graph zu repräsentieren):

Das Zeichen A ist hier das Zeichen, das nicht sein eigener Nachbar sein darf ("◊"), B und C sind die beiden anderen Zeichen (♥ und ♠).

MfG

Mister

Comments

Hallo Mister und danke für die Antwort.

Deine Zeichnungen bestätigen schon mal meine Überlegungen.

Die Antwort von Lu hatte mich auch eher verwirrt.

Aber müsste bei b) der Knoten wo reject ist , nicht eigentlich zurück zum Startknoten führen, da ja nach jedem Karo eine Regel folgt?! Also doch auch, wenn es zum 2. mal auftaucht?!

MfG

---

nein, der Automat muss ein Wort ja ablehnen, das wenigstens ein Karopaar enthält. Wenn also ein solches Karopaar auftritt, darf das Wort nicht mehr akzeptiert werden.

Würden wir vom "Reject"-Knoten wieder zum Startknoten führen, so würden wir auch Wörter akzeptieren, obwohl sie die Regel nicht erfüllen, dass nach einem Karo wenigstens ein anderes Zeichen kommt.

Zum Beispiel: AAB wäre ein Wort, das akzeptiert würde, wenn ein "B"-Pfeil vom "Reject"-Knoten zum Startknoten zeigt.

MfG

Mister

---

also darf ich das aussagenlogisch verstehen das:

- nach einem Karo ein Herz >= 1 kommen muss oder

- nach einem Karo ein Pik >= 1 kommen muss

Ich hatte das nämlich so verstanden:

- nach einem Karo kommt >= 1 Herz oder

- nach Karo kommt genau 1 Pik.

So ist alles klar

vielen Dank =)

---

Aussagenlogisch würde ich sagen:

Nach jedem Karo kommt wenigstens ein Symbol, das kein Karo ist.

⇔

Es gibt keine zwei genau aufeinanderfolgenden Karos.

Bitte. Schönen Tag noch,

Mister

Answer 2

Kann mir jemand einen Hinweis auf die Dreierpotenz Basis 3 geben?

Was eine Dreierpotenz ist, weiss ich. Nur kann ich nichts mit der Basis anfangen.

Die Basis ist die Zahl 'unten'. Die Zahl 'oben' nennt man Exponent.

 Dreierpotenz mit Basis 3  ist 3^3

Deine Zahl dort ist 0*3^2 + 1*3^1 + 2*3^0.

Üblich zum Rechnen ist das Zehnersystem. https://de.wikipedia.org/wiki/Dezimalsystem

Die Basis ist hier 10.

Comments

Hallo lu. OK also jetzt ist das Problem mit der Potenz gelöst. Aber das würde doch heißen das mein Automat aus 3³ langen Wörtern bestehen könnte. Die Potenz bezieht sich ja nicht auf die Zeichen in w, oder versteh ich das falsch?

---

Deine Zahl dort ist 0*3² + 1*3¹ + 2*3⁰ gibt im Zehnersystem 5. ist also keine Dreierpotenz. Dein Automat arbeitet daher falsch.

---

Der zweite Automat würde mE richtig arbeiten.

---

@Lu: Wie erkennst du anhand der Sprache, dass ein Automat falsch arbeitet? Der User hat doch noch gar keinen Automaten angegeben?

---

@Mister: Ich habe verstanden, dass ich anhand der Angabe vor |
feststellen muss, ob der Automat richtig arbeitet.

und (0,1,2) soll ja nicht akzeptiert werden.

Die Angabe beim Zweiten erfüllt die Bedingung daneben.

Sollten das dort geschweifte Klammern sein, muss man wohl erst noch den Automaten erfinden.

---

@Lu: "Ich habe verstanden, ..." ← Über diesen Punkt würde ich nochmal nachdenken.

Ein Automat gibt nicht aus, ein Automat impliziert eine Sprache auf einem gegebenen Alphabet.

---

War mir eh etwas suspekt, wenn ein einziges akzeptiertes Wort schon genügen soll, um einen Automaten zu beurteilen.
Aber das wollte ich auch dem Fragesteller überlassen, der ja nur wissen wollte, was eine Basis ist.

---

Der Fragesteller wollte auch wissen, welche Zustände der Automat abdecken müsste.

---

Dazu sollte man selbstverstädnlich wissen, was ein Automat ist.

Es gibt natürlich Automaten, die nur ein einziges Wort akzeptieren.