Konstruktion eines Automaten

volkard

vip@r schrieb:

Diese obige schrittweise Entwicklung hast du jetzt auf welches Beispiel angewendet?

Auf dieses Beispiel: l = {w in Σ^*_Bool | w enthält 11 genau 2 mal}

~~Ja.~~
edit: NEIN! Siehe edit oben. Ich hatte die Aufgabestellung falsch gelesen.

vip@r schrieb:

Zitat: "... kann ich es sogar als Tabelle entwickeln und muß kein Bildchen malen."

Hm, das bringt mir jetzt nicht so viel die Tabelle, da ich es in der Klausur als Graph malen muss. Aber vielleicht kann man ja die Tabelle in einen Graphen umsetzen? Geht das?

Ja, geht sogar ganz einfach. Jede Zeile ist ein Kreischen und Bei0 und Bei1 ergeben die Pfeilchen auf die anderen Kreischen.

vip@r schrieb:

Das würde dann bedeuten, ich müsste erst die Tabelle machen und dann aus der Tabelle den Graphen extrahieren.

Nein, nichtmal.
Tabelle war für mich nur einfacher zu posten als das äquivalente Bildchen. Und unfertige Tabelle entspricht genauso dem unfertigen Bildchen. Statt eine neue Zeile in die Tabelle einzufügen, kann man genauso einen neuen Kreis zeichnen und die beiden abgehenden Pfeile.

vip@r schrieb:

Aber wie oben schon geschrieben würde ich gern wissen auf welche Sprache du die ausführliche Entwicklung bezogen hast, damit ich das mal Schrittweise durchspielen kann. Am besten bei einem Beispiel bei dem ich die Lösung schon habe.

Was Du magst. Bestell bei mir eine Entwicklung und ich versuche es.

vip@r schrieb:

Danach wäre es sehr nett wenn du mir eine sehr einfache Sprache geben würdest bei der ich dann die Tabelle respektive Graph entwickle und dir dann meine entwickelte Tabelle kurz abtippe damit du sie überprüfen kannst.

Bist du damit einverstanden?

Klar. Aber Du hast doch mehr Übungsaufgaben vorrätig als ich, oder?

Würde mich freuen![/quote]

Gregor

Danke fuer diesen Thread.

Ich hatte lange keine Automaten mehr konstruiert, habe aber anhand der Aufgabenstellungen hier gesehen, dass ich es wohl noch so halbwegs hinkriege.

Ich habe mir dabei ueberlegt, was ich eigentlich bei der Konstruktion mache und habe festgestellt, dass ich eigentlich nicht sooo systematisch vorgehe. Aber es scheint aehnlich wie bei der Programmierung zu sein. Man man einen Algorithmus konstruieren will, bei dem man an gewissen Stellen unterschiedliche Faelle unterscheiden muss, dann hat man fast das gleiche Problem:

Man muss sich ueberlegen, welche Faelle (Zustaende) auftreten koennen und was man in so einem Fall jeweils macht. Wenn man intuitiv programmiert, dann geht man die Funktionsweise des Algorithmus praktisch in seinem Kopf durch. "Wie wuerde ich das mache?!" und schreibt es auch so ins Programm. Bei der Konstruktion von derartigen Automaten, die bestimmte Sprachen akzeptieren sollen, kann man es genauso machen. Man ueberlegt sich im Kopf wie ein gegebenes Wort anfangen kann und abhaengig vom ersten Zeichen geht es dann gleich in unterschiedliche Zustaende. Dann denkt man weiter, was beim naechsten Zeichen passiert. Kommt man mit einem bestimmten Zeichen in einen schon dagewesenen Zustand? Oder stellt ein neues Zeichen eine ganz andere Situation dar?

volkard

Nochmal ein Versuch mit

l = {w in Σ^*_Bool | w enthält 11 genau 2 mal}

und diesmal lese ich die Aufgabestellung richtig. "genau 2 mal".

"m" steht wieder für "Müll": Eine beliebig lange Zeichenfolge, die keine 11 drin hat und mit 0 endet, also die bloß Müll ist und keine 1 zum Anbauen liefert.

name       bei0      bei1     akzeptiert
m          m         m1

Also ein Kreis mit m drin beschriftet und ein 0-Pfeil auf m und ein 1-Pfeil auf einen neuen Kreis mit m1 beschriftet. Die nächste Aufgabe ist es, zu überlegen, wohin die beiden Pfeile von m1 hingehen werden.

name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11

Also von m1 gehts beim Lesen einer 0 nach m zurück. Beim Lesen einer weiteren 1 aber gehts in einen neuen Zustand namens m11.

Und dann habe ich mir Kreis für Kreis vorgenommen und immer überlegt, wie der Folgezustand bei 0 und bei 1 wohl heißen müßte.

Als nächstes den m11 begutachten:

name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11
m11        m11m      m111

Und so weiter. Zeile für Zeile ist jeweils genau die Überlegung, was bei 1 und was bei 0 für ein Zustand folgen müßte.

name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11
m11        m11m      m111
m111       m111m     zuviel
zuviel     zuviel    zuviel
m11m       m11m      m11m1
m11m1      m11m      m11m11
m11m11     m11m11m   zuviel
m11m11m    m11m11m   m11m11m1
m11m11m1   m11m11m   zuviel

Soweit, sogut. Alle Zustände haben zwei Ausgänge.
Außer m111m, den habe ich noch nicht fertig.
Hier fällt mir auf, daß "m111m" und "m11m11m" gleichwertig sind.
Sie möchten zusammenfallen. Ich sollte mir einen besseren Namen dafür einfallen lassen, sagen wir mal "gutm". Entsprechend wollen "m111" und "m11m11" zusammenfallen und "gut" heißen. Das spart bestimmt viele Zustaände/Zeilen/Kreise.
Eigentlich bin ich ja faul und würde sie gerne jetzt schon zusammenfallenlassen.
Aber nö, ich mach mal brutal weiter.

name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11
m11        m11m      m111
m111       m111m     zuviel
zuviel     zuviel    zuviel
m11m       m11m      m11m1
m11m1      m11m      m11m11
m11m11     m11m11m   zuviel
m11m11m    m11m11m   m11m11m1
m11m11m1   m11m11m   zuviel
m111m      m111m     m111m1
m111m1     m111m     zuviel

Ihgitt, ist der riesig geworden. Hoffentlich ist er korrekt. Da steigt ja kein Schwein mehr durch. Und der Prof bekommt Augenkrebs, wenn er schauen will, ob der stimmt. Nach meinem Mittagsschläfchen muß ich das nochmal probieren mit "gut" und "gutm".

Wobei man das Bildchen ja auch (mit genau gleichem Ergebnis) formal optimieren könnte, wenn man mit Bleistift gemalt hätte. Ach, so viel spart die Optimierung wohl doch nicht ein.

Gregor

volkard schrieb:

Nochmal ein Versuch mit

l = {w in Σ^*_Bool | w enthält 11 genau 2 mal}

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

Vielleicht ist in dem allerdings auch ein Fehler. Wer weiss. Der Startzustand hat links einen Balken, die akzeptierenden Zustaende rechts.

EDIT:

@volkard: Mir erscheint Dein Automat korrekt zu funktionieren. ...zumindest wenn die Zustaende akzeptieren, von denen ich ausgehe, dass sie akzeptieren.

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?

vip*r

Gut, dann werde ich mal versuchen diese Aufgabe nachzuvollziehen.

Einige Fragen hab ich aber schon noch:

-> Was ist "bei0" und "bei1" und was soll dabei das "bei" bedeuten? Edit: Damit ist wahrscheinlich gemeint mit welchem Zeichen (1 oder 0) in welchen neuen Zustand gewechselt wird, oder?
-> m steht für Müll. Ok. Das m ist aber doch auch der jeweilige Zustand. Ich bin es bis jetzt gewohnt, dass man die Zustände durchnummeriert. Bspw.: q0, q1, q2, ..., qn-1, qn. Was soll hier nun m, m1, m11 und dann so komische aneinanderkettungen m11m11 bedeuten? Edit: Kann es sein, dass hiermit gemeint ist welche Zustand der Zeichenkette in dem jeweiligen Zustand gerade vorzufinden ist?

-> Was soll zuviel heißen? Geht bspw. vom Zustand m111 mit einer 1 die Transition dann in einen Deadstate?

-> Wie setze ich nun konkret die Liste in einen Graphen um? Edit: Link von meinem Graphen den ich aus der Liste extrahiert hab: http://imageshack.us/photo/my-images/441/43941107.jpg/ (Startzustand ist mit Pfeil gekennzeichnet)

Großes Edit: Wie erkenne ich denn nun aus der Liste welche Zustände akzeptierend sind?

Gregor

vip@r schrieb:

Großes Edit: Wie erkenne ich denn nun aus der Liste welche Zustände akzeptierend sind?

Naja, volkard hat seine Zustaende praktisch nach den Zeichen benannt, die bisher aufgetaucht sind. Entsprechend sind m111m, m111m1, m11m11, m11m11m und m11m11m1 akzeptierend. Die erfuellen ja die Bedingung, die an die zu akzeptierende Sprache gesetzt sind.

...Der von Dir gezeichnete Automat scheint uebrigens ein paar Kanten zu haben, die in volkards Liste nicht auftauchen und die falsch sind. Vor allem die Verbindungen zwischen m11m1 und m111m fallen mir gerade auf.

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}

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.