Konstruktion eines Automaten

[vip*r]

Gut, da hast du Recht.

Wenn ich nun bspw. Das Wort w=1111 durchlaufen lasse, dann enthält dieses Wort 11 genau zweimal. Aber genau dieses Wort wird vom Automat aber nicht erkannt...; weil die vierte 1 nämlich im DS landet...

Ich glaub aber, dass ein Fehler in meinem Graphen ist... Oder kann das jemand verifizieren?

Edit: 1111 enthält 11 dreimal. Shit.

[vip*r]

Ich hab jetzt mal nochmal versucht aus eigener Gedankenkraft einen Automaten für die Sprache zu erstellen. Tut's dann der einfache nicht auch?

Link: http://imageshack.us/photo/my-images/857/22923694.jpg/

Kann das mal jemand noch durchprobieren? Mir wäre kein Wort eingefallen das nicht geht!

[Gregor]

vip@r schrieb:

Ich hab jetzt mal nochmal versucht aus eigener Gedankenkraft einen Automaten für die Sprache zu erstellen. Tut's dann der einfache nicht auch?

Link: http://imageshack.us/photo/my-images/857/22923694.jpg/

Kann das mal jemand noch durchprobieren? Mir wäre kein Wort eingefallen das nicht geht!

Was ist mit "1110" und 110110?

[vip*r]

1110 ist doch an der Stelle bei der dritten 1 schon akzeptiert. Da interessiert doch dann nicht mehr was danach kommt, oder?

Bei 110110 ist es doch das gleich, oder? was nach der vierten 1 kommt ist doch egal, da der Automat schon akzeptiert hat, oder?

Ja, oder hab ich hier was grundsätzlich falsch verstanden?

[Gregor]

vip@r schrieb:

1110 ist doch an der Stelle bei der dritten 1 schon akzeptiert. Da interessiert doch dann nicht mehr was danach kommt, oder?

Bei 110110 ist es doch das gleich, oder? was nach der vierten 1 kommt ist doch egal, da der Automat schon akzeptiert hat, oder?

Ja, oder hab ich hier was grundsätzlich falsch verstanden?

Es könnten ja auch "1111" oder "110111" kommen. Die dürfen nicht akzeptiert werden. Die vorherigen aber schon.

[volkard]

Gregor schrieb:

EDIT2: Frage: Muss man bei einem Automaten eigentlich fuer alle Zustaende und alle moeglichen Eingaben Folgezustaende einbauen? Oder kann man einfach sagen, dass die Eingaben, die zu keinem Zustand fuehren, offensichtlich nicht akzeptiert werden?

Klar kann man das so handhaben. Man muß ja nur einen Zustand

name       bei0      bei1     akzeptiert
hoelle     hoelle    hoelle   nein

automatisch anlegen und jeden weggelassenen Pfeil per Konvention dahinzeigen lassen.

Und das macht man auch.

http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat sagt
"Alternativ kann man die Übergangsfunktion als partielle Funktion definieren, sodass nicht von jedem Zustand aus für jedes Eingabesymbol ein Nachfolgezustand existieren muss. Das Eingabewort gilt somit auch dann als verworfen, wenn beim Lesen der Eingabe ein Übergang nicht möglich ist."

[volkard]

Gregor schrieb:

Ich habe auch mal mein professionelles Automaten-Malprogramm angeworfen und aufgezeichnet, wie meiner so in etwa aussieht.

http://img838.imageshack.us/img838/382/automat.png

Uih, Du hast aber einen Kleinen!
7 Zustände, wenn ich "hölle" aka "DS" ("dead state") mitzähle, den Du ja durch Weglassen der 1 vom Zustand rechts unten benutzt hast.

Ich müßte zum selben Ergebnis kommen.
Zunächst mal entwickle ich nochmal von vorne mit "gut" und"gutm", wie angekündigt.

name       bei0      bei1      akzeptiert 
m          m         m1
m1         m         m11
m11        m11m      gut
m11m       m11m      m11m1
m11m1      m11m      gut
mgut       mgutm     hölle     ja
mgutm      mgutm     mgutm1    ja
mgutm1     mgutm     hölle     ja
hölle      hölle     hölle

9 Zustände. Da können also noch zwei weg.

Ah, die Zeilen mgut und mgutm1 sind identisch, weil sie außer dem Namen völlig gleiche Zabellenzeilen haben. Die kann ich zusammenfassen. Alle Sprünge nach mgutm1 ersetze ich durch mgut.

name       bei0      bei1      akzeptiert 
m          m         m1
m1         m         m11
m11        m11m      gut
m11m       m11m      m11m1
m11m1      m11m      gut
mgut       mgutm     hölle     ja
mgutm      mgutm     mgut      ja
hölle      hölle     hölle

So, 8 Zustände. Ob ich noch so eine Zeile finde?
Ja! m11 und m11m1 sind auch identtisch. Ich mache m11m1 weg.

name       bei0      bei1      akzeptiert 
m          m         m1
m1         m         m11
m11        m11m      gut
m11m       m11m      m11
mgut       mgutm     hölle     ja
mgutm      mgutm     mgut      ja
hölle      hölle     hölle

So, auch 7 Zustände.
(Dabei hat's mir aber die Bedeutung der Namen zerkloppt. )

Das male ich jetzt mal hin.
Oder es müßte reichen, Deinen Automaten mit meinen Zustandsnamen zu beschriften.

Der linke heißt m.
Der rechts von m heißt m1.
Der rechts von m1 heißt m11.
Der über m11 heißt m11m.
Der rechts von m11 heißt mgut.
Der über mgut heißt mgutm.
Und der weggelassene heißt hölle.

Und jetzt schaue ich im Bildchen alle Zustände nacheinander an und prüfe, ob diue Pfeilchen genau den Tabellenzeilen entsprechen.
Jup.

Wir kommen also zum selben Automaten. Bin aber ein wenig enttäuscht, wie umständlich mein Weg anscheinend war.

Da die Bedeutung der Namen zerkloppt ist, sollte ich sie noch umbenennen in q1 bis g6 und DS. Besser nichtssagende Namen haben, als zu lügen.

name       bei0      bei1      akzeptiert 
q1         q1        q2
q2         q1        q3
q3         q4        q5
q4         q4        q3
q5         q6        DS        ja
q6         q6        q5        ja
DS         DS        DS

[Gregor]

volkard schrieb:

Wir kommen also zum selben Automaten. Bin aber ein wenig enttäuscht, wie umständlich mein Weg anscheinend war.

Ich denke, Dein Weg ist sehr robust und auch bei komplexeren Automaten anwendbar. Ich habe hingegen einfach drauflosgezeichnet. Bei komplexeren Aufgaben geht das schnell schief.

[volkard]

Gregor schrieb:

Ich denke, Dein Weg ist sehr robust

Ja, stimmt. Das klappt sogar nach der Party noch.

[Gregor]

Ich denke eigentlich, dass man den Zuständen trotzdem sehr gute Bezeichner geben kann. Mir fällt zum Beispiel gerade auf, dass man den Automat völlig systematisch auf Sprachen mit 3"11", 4"11", 5"11" und so weiter erweitern kann.

Aber die Frage ist, ob es ein systematisches Konstruktionsprinzip gibt, mit dem man ohne Optimierung direkt auf so einen Automaten kommt.

[volkard]

Gregor schrieb:

Ich denke eigentlich, dass man den Zuständen trotzdem sehr gute Bezeichner geben kann.

Ja. Aber die werden zu lang. Dann lieber so machen

name bei0 bei1 kommentar
q1   q1   q2   Noch kein Paar gesehen und keine offene 1 am Ende
q2   q1   q3   Noch kein Paar gesehen und eine offene 1 am Ende
…

[vip*r]

Gregor schrieb:

Ich habe auch mal mein professionelles Automaten-Malprogramm angeworfen und aufgezeichnet, wie meiner so in etwa aussieht.

http://img838.imageshack.us/img838/382/automat.png

Hm, sorry wenn ich grad versuche deinen Automaten in Frage zu stellen, aber was passiert bei deinem Automaten wenn die Zahlenfolge 1111 kommt? Nach der dritten 1 kommt der Automat nicht mehr weiter...

Oder bin ich immer noch am falschen Weg?

[vip*r]

Hey Leute!

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

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

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

Also den Automaten jetzt einfach aus Gedankenkraft hinmalen is aber scho a bissl heavy, oder? Ich hab mir jetzt gedacht, dass es vielleicht gehen könnte erstmal einen Automaten zu bauen, der L = {w in Σ^*_Bool | Zahlwert(w) > 2} realisiert und dann meine ich in der Vorlesung gehört zu haben, dass man für Reverse-Automaten einfach die Transitionspfeile umdrehen kann. Stimmt das? Wie würdet ihr da rangehen?

[volkard]

vip@r schrieb:

Gregor schrieb:

Ich habe auch mal mein professionelles Automaten-Malprogramm angeworfen und aufgezeichnet, wie meiner so in etwa aussieht.

http://img838.imageshack.us/img838/382/automat.png

Hm, sorry wenn ich grad versuche deinen Automaten in Frage zu stellen, aber was passiert bei deinem Automaten wenn die Zahlenfolge 1111 kommt? Nach der dritten 1 kommt der Automat nicht mehr weiter...

Oder bin ich immer noch am falschen Weg?

Er hat den DS nicht eingezeichnet und auch Pfeile weggelassen, die auf den DS laufen. Nach der dritten 1 bei der vierten 1 mußt Du nur dem unsichtbaren 1-Pfeil auf den unsichtbaren DS folgen. Oder sieh es so, daß dann der Automat kaputtgeht, weil er bei der vierten 1 ratlos ist.

Siehe auch http://www.c-plusplus.net/forum/297741-20
Manchmal habe ich das Gefühl, Du liest nicht mit.

[volkard]

vip@r schrieb:

Hey Leute!

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

L = {w in Σ^*_Bool | Zahlwert(w^R) > 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.

[volkard]

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.

[vip*r]

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?

[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: