Wieder eine Automate-Konstruktion

vip*r

Hey Leute!

Ich hab folgende Sprache L:

L = {w aus Σ^*_Bool | |w|₀ + |w|₁ = 2}

Hier mein Automat: http://imageshack.us/photo/my-images/6/82602351.jpg/

Ist das richtig?

Christoph

vip@r schrieb:

Ist das richtig?

Das kannst du doch in 3 Minuten selber herausfinden?

Führ den Automaten doch mal aus auf ein paar Wörtern der gegebenen Sprache und auf ein paar Wörtern außerhalb der gegebenen Sprache und schau was passiert.

vip*r

Ich verstehe die Bedingung schon richtig, oder?

Ich verstehe das so: Der Automat erkennt nur Wörter die die Form 01, 00, 10, 11 haben, oder? Alle anderen Wörter fliegen raus.

vip*r

Wenn ich jetzt z.B. in den obigen Automaten von mir das Wort 0100 reinstecke, dann akzeptiert er nach dem er die 1 gelesen hat. Es würde aber noch 00 folgen, was aber nicht mehr macht weil ja der Automat schon angehalten wurde, oder?

Christoph

vip@r schrieb:

Ich verstehe die Bedingung schon richtig, oder?

Ich verstehe das so: Der Automat erkennt nur Wörter die die Form 01, 00, 10, 11 haben, oder? Alle anderen Wörter fliegen raus.

Du schreibst:

vip@r schrieb:

|w|₀

Was "Betragsstriche mit kleiner Null unten" bedeutet, muss im Skript zur Vorlesung stehen oder in deinen Aufzeichnungen oder im Buch, je nachdem wo du diese Aufgabe her hast. Wenn es die 0en im Wort zählt, und wenn Sigma = {0,1} ist, dann wird die Sprache durch die Bedingung aus deinem ersten Posting endlich, ja.

vip@r schrieb:

Wenn ich jetzt z.B. in den obigen Automaten von mir das Wort 0100 reinstecke, dann akzeptiert er nach dem er die 1 gelesen hat. Es würde aber noch 00 folgen, was aber nicht mehr macht weil ja der Automat schon angehalten wurde, oder?

Ein endlicher Automat hält normalerweise nicht an sobald er in einen akzeptierenden Zustand kommt, sondern erst nachdem die gesamte Eingabe verarbeitet wurde. Aber auch das hängt von der genauen Definition ab, die du verwendest, deswegen würde ich auch hier im Skript oder Buch nachschauen, wie bei euch endlicher Automat genau definiert wurde.

volkard

vip@r schrieb:

Ich hab folgende Sprache L:
L = {w aus Σ^*_Bool | |w|₀ + |w|₁ = 2}

Der ist doch im anderen Thread längst gelöst.

vip*r

|w|₀ zählt die Anzahl der Nullen in einem Wort.

Der ist doch im anderen Thread längst gelöst.

Falls du den Modulo 2 Automat gemeint hast, dann verstehe ich aber nicht warum die beiden Automaten gleich sein sollen! Modulo 2 heißt ja, dass jede Wortlänge die durch 2 gerade teilbar ist erkannte werden sollen. Hier handelt es sich aber doch darum, dass nur Wörter mit der Länge 2 erkannt werden sollen. Hier also quasi wirlich nur 4 Wörter...

Bei meinem Automaten oben ist doch noch das Problem, dass z.B. 00 erkannt wird, evtl. nachfolgende Zeichen, dann aber noch erkannt werden was aber eben nicht sein soll. Mein Problem besteht jetzt darin, den Automaten soweit noch zu verbessern, dass wenn solche Zeichen noch kommen sollten diese auf einem nicht-akzept. Zustand gelenkt werden und dort mit einer 0,1-Eigenschleife "verbrannt" werden.

Kann mir da keiner Helfen?

volkard

vip@r schrieb:

Hier handelt es sich aber doch darum, dass nur Wörter mit der Länge 2 erkannt werden sollen. Hier also quasi wirlich nur 4 Wörter...

Upps. Hast recht.
Dann würde ich eine Kette machen, die bei jeder EIngabe eins nach rechts wandert. Der dritte Zustand akzeptiert. Und der vierte ist der Fehlerzustand.

vip*r

Also so: http://imageshack.us/photo/my-images/97/67131033.jpg/

volkard

vip@r schrieb:

Also so: http://imageshack.us/photo/my-images/97/67131033.jpg/

Richtig.

(Der läßt sich noch ein wenig optimieren, weil zufällig die Zustände 2 und 3 für beide Symbole jeweils den selben Nachfolgerzustand (den akzeptierenden) haben. Die beiden lassen sich zusammenfassen zu einem Zustand.)

vip*r

Ja genau. Das hab ich grad schon noch gemacht.ich hab jetzt 4 Zustände jeweils mit einer 0,1-Kante verbunden. Der dritte erkennt und der vierte ist der Fehlerzustand mit einer 0,1-Eigenschleife.

Ich hab jetzt hier gleich noch mal eine eine Sprache L von der ich zwar schon angefangen hab, aber jetzt nicht mehr weiter weiß:

L = {z aus Σ^*_Bool | z = u1110110v, mit u, v aus Σ^*_Bool}

u und v sind quasi beliebige Wörte aus Σ. Ich hab jetzt mal einen Automaten dastehen, der mir das mittlere Wort vollständig "herausschneidet" und an dessen letzten Zustand noch einen allerletzten akzept. Zustand welcher mir dann alles erkennt was noch kommt. Soweit sollte das schon richtig sein.

Mein Problem besteht nun darin, dass erste Wort u herauszufiltern und zu entscheiden wann des mittlere "definierte" Wort beginnt...

volkard

vip@r schrieb:

Ich hab jetzt hier gleich noch mal eine eine Sprache L von der ich zwar schon angefangen hab, aber jetzt nicht mehr weiter weiß:

L = {z aus Σ^*_Bool | z = u1110110v, mit u, v aus Σ^*_Bool}

q0: 0->q0  1->q1 //Bisher erkannt: u
q1: 0->q0  1->q2 //Bisher erkannt: u1
q2: 0->q1! 1->q3 //Bisher erkannt: u11
q3: 0->q4  1->   //Bisher erkannt: u111
q4: 0->    1->q5 //Bisher erkannt: u1110
q5: 0->    1->q6 //Bisher erkannt: u11101
q6: 0->    1->   //Bisher erkannt: u111011
q7: 0->q7  1->q7 //Bisher erkannt: u1110110v

Das Vorwärtsgehen ist ganz leicht.
Aber das Zurückfallen bei falschem Zeichen ist voll übel.
Zum Beispiel wird aus u111011 durch Anfügen einer 1 dann u111. Die drei letzen Zeichen waren ja 111, ich darf also bei Fehler nicht bis q0 zurückspringen, sondern muß immer überlegen, bis wohin genau.

vip*r

Also ich weiß ja nicht so genau, aber das ist wahrschenlich eh wieder falsch:

q0: 0->q0  1->q1 //Bisher erkannt: u
q1: 0->q0  1->q2 //Bisher erkannt: u1
q2: 0->q1! 1->q3 //Bisher erkannt: u11
q3: 0->q4  1->q3 //Bisher erkannt: u111
q4: 0->q4  1->q5 //Bisher erkannt: u1110
q5: 0->q4  1->q6 //Bisher erkannt: u11101
q6: 0->q5  1->q7 //Bisher erkannt: u111011
q7: 0->q7  1->q7 //Bisher erkannt: u1110110v

Jester

Das Problem ist, dass der Automat ja nicht gesagt kriegt "so, jetzt ist das u fertig, jetzt kommt der festgelegte text aus der mitte". er muß also selbst rausfinden, ob die bisherige Eingabe schonmal das feste Wort aus der Mitte enthalten hat.

Bau doch erstmal einen nicht-deterministischen Automaten (das ist nicht so schwer) und mach den dann deterministisch.

vip*r

Gut. Ein NEA sollte doch dann so aussehen:

q0: 0,1->q0 1->q1
q1: 1->q2
q2: 1->q3
q3: 0->q4
q4: 1->q5
q5: 1->q6
q6: 0->q7
q7: 0,1->q7

Stimmt das so?

vip*r

So, hier dann mal der DEA, der durch Umwandlung vom NEA entstanden ist. Ich hab jetzt einen Zustand mehr als vorher. Vielleicht kann das mal einer von euch überprüfen! Danke!

http://imageshack.us/photo/my-images/402/47590980.jpg/

Edit: Die nicht bezeichnete Kante ist eine 0-Kante...

Jester

Hallo,

Dein NEA sieht gut aus (mal geraten was anfangs- und endzustände sind). Mit der Umwandlung bin ich noch nicht ganz einverstanden:

- von q_4 muß es noch einen Pfeil zu q_0 geben, wenn man ne 0 eingibt
- der 1-Pfeil von q_6 muß imo zu q_2 gehen, an der stelle hat man ja schon zwei 1en hintereinander gesehen

- q_7 und q_8 sind quasi derselbe zustand

vip*r

Ich hab dann mal die Potenzmengenkonstruktion neu gemacht und bin dann auf folgenden DEA gekommen: http://imageshack.us/photo/my-images/6/32334606.jpg/

Warum aber nun die 1er-Kante von q6 aus nach q2 (und nicht nach q3 wie in meinem neuen DEA) gehen soll, verstehe ich nicht.

Woran du siehst, dass q7 und q8 eigenlich gleiche Zustände sind, würde mich auch sehr interessieren!

Edit: Ich zähl die Mengenzustände genauso durch wie die Zustände des NEAs. Verstehst du was ich meine?