Konstruktion eines Automaten

volkard

vip@r schrieb:

volkard schrieb:
name bei0 bei1 akzeptiert kommentar
q0   q3   q1   nein       Start-Zustand
q1   q1   q2   nein       1 0* oder 0 ? 0*
q2   q2   q2   ja         Zahl ist größer, weitere Ziffern vergrößern erst recht
q3   q1   q1   nein       0
gewinnen
Wenn ich mir nun diesen Automaten hinmale, und das Wort 0001 reingebe (das Wort vor Reverse war 1000), dann akzeptiert der Automat aber! Das soll er doch eigentlich nicht, oder?

1000₂ ist doch größer als 2₁₀.
Oder habe ich schon wieder die Aufgabe falsch gelesen?
Ich wollte alle Zahlen akzeptieren, die wenn man sie umdreht und binär liest, größer als 2 sind.

vip*r

volkard schrieb:

Ich wollte alle Zahlen akzeptieren, die wenn man sie umdreht und binär liest, größer als 2 sind.

Ja, doch das stimmt schon. So hab ich das auch verstanden.

w=1000 -> w^R = 0001 -> 0001 darf nicht akzeptiert werden. Der Automat tut dies aber...?

volkard

vip@r schrieb:

w=1000 -> w^R = 0001 -> 0001 darf nicht akzeptiert werden. Der Automat tut dies aber...?

Die Eingabe 1000 akzeptiert er nicht. Zahlwert(0001)=1, ok.

Die Eingabe 0001 akzeptiert er. Zahlwert(1000)=168, ok.

:xmas2: :xmas2:

vip*r

Hm, was war dann mein Gedankenfehler? Der Automat bekommt nicht das umgedrehte Wort sondern soll es auch noch selbst umdrehen?

Aber: Zahlwert(1000)=8!!!!!!

volkard

vip@r schrieb:

Hm, was war dann mein Gedankenfehler? Der Automat bekommt nicht das umgedrehte Wort sondern soll es auch noch selbst umdrehen?

Klar. Wir reden ja über
L = {w in Σ^*_Bool | Zahlwert(w^R) > 2}

und nicht über

L = {w in Σ^*_Bool | Zahlwert(w) > 2}

(Ich nehme aus dem Kontext heraus an, daß w^R heißt, daß die Eingabe umgedreht werden soll.)

vip*r

Das hochgestellte R bedeutet natürlich, dass das Wort umgedreht, also Reverse, gesehen werden soll. Das hätt ich erwähnen sollen, Sorry, mein Fehler.

vip*r

Aber mir ist jetzt noch so vielen Aufgaben dennoch immer noch irgendwie schleierhaft wie man so schnell auf einen solch kleinen richtigen Automaten kommen soll

Du musst doch da irgendwie auch quasi immer die Definition im Hinterkopf haben, oder? Und du musst doch auch irgendwie wissen, welche Zahlenkonstellationen ab welchem Punkt immer akzeptiert werden da sie nicht mehr kleiner werden.

Reicht es dann nicht einen Automaten zu konstruieren, auf den man erst auf die Zustände eingeht, die nicht akzeptiert werden?

vip*r

Ich hab hier nochmal eine Sprache:

L = {z in Σ^*_Bool | z = 0v; v enthält nur gerade Anzahl Einsen}

Meine Vorschlag:

Name   bei 0   bei 1   akzeptierden
q0      q1
q1              q2          ja
q2      q2      q1

Kann das so stimmen?

Gregor

vip@r schrieb:

Ich hab hier nochmal eine Sprache:

L = {z in Σ^*_Bool | z = 0v; v enthält nur gerade Anzahl Einsen}

Meine Vorschlag:
Name   bei 0   bei 1   akzeptierden
q0      q1
q1              q2          ja
q2      q2      q1
Kann das so stimmen?

Was passiert, wenn man in Zustand q1 0 eingibt?

volkard

vip@r schrieb:

Aber mir ist jetzt noch so vielen Aufgaben dennoch immer noch irgendwie schleierhaft wie man so schnell auf einen solch kleinen richtigen Automaten kommen soll

Naja, gekommen bin ich auf einen Automaten mit 7 Zuständen. Den konnte ich dann optimieren und 3 Zustände wegwerfen.

vip@r schrieb:

Du musst doch da irgendwie auch quasi immer die Definition im Hinterkopf haben, oder? Und du musst doch auch irgendwie wissen, welche Zahlenkonstellationen ab welchem Punkt immer akzeptiert werden da sie nicht mehr kleiner werden.

Ja, wohl schon. Die Liste aller vierstelligen Eingaben hat mir enorm geholfen. Und dann beim Basteln, wo ich immer wieder binärzahlen rückwärts lesen mußte, bin ich zweimal fast vom Stuhl gefallen.

vip@r schrieb:

Reicht es dann nicht einen Automaten zu konstruieren, auf den man erst auf die Zustände eingeht, die nicht akzeptiert werden?

Wenn es Dir hilft, warum nicht?
Das wäre dann "Komplementbildung" aus
http://public.tfh-berlin.de/~merceron/pub/DP-DFA.pdf