3. Konstruktion eines Automaten

Konstruktion eines Automaten

  • V

    vip@r schrieb:

    Hey Leute!

    Hier hätt ich wieder eine Nuss für euch!

    L = {w in Σ*Bool | Zahlwert(wR) > 2}

    000  0
001  1
010  2
------
011  3
100  4
.
.
.

    …
    Wie würdet ihr da rangehen?

    Genau so, erstmal Daten sammeln und nach Erleuchtung streben.
    Ich habe ein wenig mehr gesammelt:

    0000 f
0001 w
0010 w
0011 w
0100 f
0101 w
0110 w
0111 w
1000 f
1001 w
1010 w
1011 w
1100 w
1101 w
1110 w
1111 w

    Wenn die Eingabe mit einer 1 anfängt, führt die nächste 1 zum Sieg.
    (Ab jetzt heißt *, daß das vorgehende Zeichen beliebig oft wiederholt wird, wie in regular expressions.)

    name bei0 bei1 akzeptiert kommentar
q0        q1   nein       Start-Zustand
q1   q1   q2   nein       1 0*
q2   q2   q2   ja

    Und wenn die erste Ziffer eine 0 war?
    Statt vorher zu überlegen, kann ichs auch gleich in den Automaten schreiben.

    name bei0 bei1 akzeptiert kommentar
q0   q3   q1   nein       Start-Zustand
q1   q1   q2   nein       1 0*
q2   q2   q2   ja         Zahl ist größer, weitere Ziffern vergrößern erst recht
q3   q4        nein       0
q4   q4   q2   nein       0 0 0*

    Und so weiter. Der Rest sollte ganz zwanglos gehen.

    name bei0 bei1 akzeptiert kommentar
q0   q3   q1   nein       Start-Zustand
q1   q1   q2   nein       1 0*
q2   q2   q2   ja         Zahl ist größer, weitere Ziffern vergrößern erst recht
q3   q4   q5   nein       0
q4   q4   q2   nein       0 0 0* Eine irgendwann folgende 1 würde gewinnen
q5   q5   q2   nein       0 1 0* Eine irgendwann folgende 1 würde gewinnen

    Wobei jetzt q4 und q5 "gleich" sind.

    name bei0 bei1 akzeptiert kommentar
q0   q3   q1   nein       Start-Zustand
q1   q1   q2   nein       1 0*
q2   q2   q2   ja         Zahl ist größer, weitere Ziffern vergrößern erst recht
q3   q4   q4   nein       0
q4   q4   q2   nein       0 0 0* oder 0 1 0* Eine irgendwann folgende 1 würde gewinnen

    Eigentlich war q1 auch "gleich" zu q4 und q5.

    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

    Das ist ja verrückt.
    An weniger als 4 Zustände mag ich eigentlich nicht glauben.

    0
  • V

    vip@r schrieb:

    und dann meine ich in der Vorlesung gehört zu haben, dass man für Reverse-Automaten einfach die Transitionspfeile umdrehen kann. Stimmt das?

    Davon habe ich noch nie gehört.
    Aber kurzes googlen bestätigt es.
    url=http%3A%2F%2Fpublic.tfh-berlin.de%2F~merceron%2Fpub%2FDP-DFA.pdf
    Leider zerhaut es dabei den DEA in einen NEA.

    Die Aufgabe ist so komisch, daß ich fast vermute, Ihr solltet genau das machen.

    0
  • V

    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?

    0
  • V

    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?

    10002 ist doch größer als 210.
    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.

    0
  • V

    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 -> wR = 0001 -> 0001 darf nicht akzeptiert werden. Der Automat tut dies aber...?

    0
  • V

    vip@r schrieb:

    w=1000 -> wR = 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:

    0
  • V

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

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

    0
  • V

    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(wR) > 2}

    und nicht über

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

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

    0
  • V

    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.

    0
  • V

    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?

    0
  • V

    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?

    0
  • G

    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?

    0
  • V

    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

    0
Anmelden zum Antworten