| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
 Verfasst am: 24. Aug 2005 16:28 Titel: Spiegelsprache erkennen |
 |
|
Hi,
habe hier ein Problem.
Allgemein vertauscht man ja die Start- und Endzustände und dreht sämtliche Richtungen der Kanten um, um einen Automaten zu bekommen, der die Spiegelsprache eines gegebenen Automaten erkennt, richtig? 
Nun funktioniert das in diesem Beispiel hier auch, allerdings muß man dort anscheinend q0 als Startzustand belassen (q0 und q3 sind dann auch weiterhin Endzustände).
Das ist doch richtig so, oder? Die Frage ist halt vor allem: WARUM ist das so bzw. warum ist q3 dann nicht der Startzustand??
 http://img319.imageshack.us/img319/8583/spiegelsprache5sd.jpg
(das ganz links ist eine 0) |
|
| Nach oben |
|
 |
|
|
ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
| Verfasst am: 24. Aug 2005 19:29 Titel: Re: Spiegelsprache erkennen |
|
|
| Remington Steele hat Folgendes geschrieben: |
Allgemein vertauscht man ja die Start- und Endzustände und dreht sämtliche Richtungen der Kanten um, um einen Automaten zu bekommen, der die Spiegelsprache eines gegebenen Automaten erkennt, richtig? :)
|
Die NEA die ich kenne haben nur einen Startzustand, aber eventuell mehrere Endzustaende, da kann diese Regel nicht ganz hinkommen.
Gruss,
ED209
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 24. Aug 2005 21:56 Titel: |
|
|
Sorry ok, etwas unglücklich ausgedruckt: Startzustände werden zu Endzuständen und Endzuständen zu Startzuständen.
Kann jemand helfen?  |
|
| Nach oben |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 24. Aug 2005 22:53 Titel: |
|
|
Is lange her, aber das reine Umdrehen der Kanten erzeugt keinen Automaten her, der den gleichen Anforderungen genügt, schließlich entstehen Zustände, für die betimmte Übergänge nicht definiert sind
zB: q1 und dann eine 0...
oder q0 der dann plötzlich zwei Möglichkeiten für 0 und 1 hat 
_________________
 |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 25. Aug 2005 16:03 Titel: |
|
|
Sicher?
Wenn man in obigem Beispiel q0 als Startzustand läßt, scheint es aber zu funktionieren .
Kann mir vielleicht jemand helfen deswegen?  |
|
| Nach oben |
|
|
ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
| Verfasst am: 25. Aug 2005 20:00 Titel: |
|
|
| kurellajunior hat Folgendes geschrieben: | , schließlich entstehen Zustände, für die betimmte Übergänge nicht definiert sind
|
Es muessen ja nicht alle Uebergaenge existieren. Die Uebergaenge die fehlen sind halt nicht erlaubt.
| Zitat: |
oder q0 der dann plötzlich zwei Möglichkeiten für 0 und 1 hat ?( |
Das Ergebnis ist dann wohl nichtdeterministisch.
@Remington:
Ich hab mir noch nicht genau angeguckt welche Sprache der Automat akzeptiert, aber vemutlich ist das was du beobachtest Zufall und nicht allgemein uebertragbar.
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 25. Aug 2005 23:06 Titel: |
|
|
hm, könnte sein - allerdings glaube ich schon, daß das "so einfach" gehen müßte oder auf jeden Fall mit einem sonstigen Verfahren, da die Aufgabe in der Klausur 4 Punkte brachte und eigentlich nicht sehr veil Zeit darauf angesetzt ist...
... kennt sich jemand damit genau aus? |
|
| Nach oben |
|
|
ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
| Verfasst am: 26. Aug 2005 02:23 Titel: |
|
|
btw:
Wenn du die Pfeile umdrehst und die Start und Endzustaende belaesst wie sie sind erhaeltst du keinen Automat der die Spiegelsprache aktzeptiert.
Der Urspuengliche Automat akzeptiert das Wort 0. Wenn q0 startzustand ist, und die Pfeile umgedreht werden endet der Automat bei der Eingabe 0 bei {q4,q1}.
Deine Theorie stimmt nicht ganz, oder ich hab sie falsch verstanden.
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
| Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005
Beiträge: 31
|
| Verfasst am: 26. Aug 2005 08:26 Titel: |
|
|
Hm, das stimmt  .
Andererseits, wenn ich q0 und q3 zum Start- und Endzustand mache, müßte es wieder funktionieren oder? (ein NFA kann doch 2 Startzustande haben, richtig?) |
|
| Nach oben |
|
|
ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
| Verfasst am: 26. Aug 2005 16:13 Titel: |
|
|
Laut Wikipedia, und nach der Definition die ich kenne nicht. (http://de.wikipedia.org/wiki/NFA).
Dennoch koennte jemand wohl kommen und es anders definieren, da ein NFA mit beliebig vielen Zustaenden eigentlich gleichmaechtig sein muesste.
Angenommen du hast die Pfeile alle umgedreht und Start und Endzustand schon vertauscht, jetzt kannst du aus dem NFA mit mehren Startzustaenden einen mit einem Startzustand machen.
Du kannst einen neuen Zustanden machen, nennen wir ihn qs, die wie bei der Potenzmengenbildung die Menge alle ehemaligen Startzustaende erhaelt, neuer Startzustand ist und nur Pfeile von sich wegfuehren hat.
qs ist der Startzustand und ein Endzustand (weil q0 Endzustand war).
Bei 0 fuehrt der Zustand zu q0, q2 und q4, bei 1 fuehrt er zu q1 und q4.
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
