Konstruktion eines Automaten

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