Teilmengenkonstruktion < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe |
Es ist keine Aufgabestellung vorhanden, es handelt sich um ein Beispiel. Es geht um eine Teilmengenkonstruktion von NEA -> DEA
Ich habe den Artikel auf Wikipedia verstanden, kann aber nun mit dem Vorlesungsstoff nichts anfangen, weil er mir nach Wikipediaschema nicht das liefert was mir der Prof. liefert.
http://homepages.fh-giessen.de/~hg12496/afs/nea-dea-2.pdf
Ich verstehe nicht warum bei Teilmengen-Konstruktion 2. Abschnitt, 1. Tabelle letzte Zeile ; warum wird bei der 3 die 1 und die 3 als Menge eingetragen ? Über die Zustandsänderung a ist doch nur 1 zu erreichen und nicht 3 ! Und was bedeutet diese unerreichbarkeit ? Ich kann mir einfach nicht erklären wie ich das separiere. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
http://s10.directupload.net/file/d/2097/t9l776fq_jpg.htm
Frage ist oben schon erklärt.
Viel dank ! Ich bin schon seit 2 Stunden dran und mein Kopf ist kurz vor dem Explodieren :(
Im übrigen hier der Wikipedialink, http://de.wikipedia.org/wiki/Teilmengenkonstruktion , dort wird es irgendwie anders aufgezeigt.
Es scheint so als nehme mein Prof. jede der Möglichkeiten von {1} - {1,2,3} anstatt wie dort einfach vom Starpunkt ausgehend und dann die zu übernehmen die noch nicht vorhanden waren.
Lieben Gruß
Micha
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:49 Sa 13.03.2010 | | Autor: | felixf |
Moin Micha!
> Es ist keine Aufgabestellung vorhanden, es handelt sich um
> ein Beispiel. Es geht um eine Teilmengenkonstruktion von
> NEA -> DEA
>
> Ich habe den Artikel auf Wikipedia verstanden, kann aber
> nun mit dem Vorlesungsstoff nichts anfangen, weil er mir
> nach Wikipediaschema nicht das liefert was mir der Prof.
> liefert.
>
> http://homepages.fh-giessen.de/~hg12496/afs/nea-dea-2.pdf
>
> Ich verstehe nicht warum bei Teilmengen-Konstruktion 2.
> Abschnitt, 1. Tabelle letzte Zeile ; warum wird bei der 3
> die 1 und die 3 als Menge eingetragen ? Über die
> Zustandsänderung a ist doch nur 1 zu erreichen und nicht 3
> !
Du musst beachten, dass es von 1 eine [mm] $\varepsilon$-Zustandsaenderung [/mm] zu 3 gibt. Damit kannst du ueber die Eingabe $a = a [mm] \varepsilon$ [/mm] von 3 ueber 1 zurueck zu 3 kommen.
(Guck beim Wikipedia-Eintrag bei [mm] "$\varepsilon$-Abschluss [/mm] eines Zustandes" im Abschnitt "Formal".)
> Und was bedeutet diese unerreichbarkeit ? Ich kann mir
> einfach nicht erklären wie ich das separiere.
Du schaust halt, welche Zustaende du vom Startzustand ueberhaupt erreichen kannst. Hast du etwa einen Automat mit zwei Zustaenden $X$ und $Y$, und ist $X$ sowohl Start- wie auch Zielzustand und bei jeder Eingabe geht man von $X$ wieder nach $X$, so ist $Y$ einfach unerreichbar. Wenn du also $Y$ weglaesst, erhaelst du einen kleineren Automaten welcher genau die gleichen Eingaben akzeptiert.
Bei der Potenzmengenkonstruktion erhaelst du normalerweise einige Zustaende, die vom Startzustand nicht erreicht werden koennen. Diese kannst du genauso einfach weglassen, da sie auf die akzeptierte Sprache keinen Einfluss haben.
LG Felix
|
|
|
| |
|
Okay,
Teil 1 ist damit gelöst. Vielen Dank. Ich habe mir schon soetwas gedacht, nur konnte ich es mir nicht vorstellen da ich da ziemlich starr auf dem beharre was ich weiß. Sprich sobald das "Epsilon" vorhanden ist, ist das fast gleichzusetzen mit einer "Schleife" um den Zustand.
Ich frage mich , trotz deiner Erklärung die ich verstanden zu haben schien, dennoch warum diese beiden Teilmengen als unerreichbar gelten ( unten stehend )? Ich habe mir diese beide Teile mal unten in das Diagramm eingefügt und sehe das von den Zuständen nur Bedienungen in Richtung der anderen Zustände gehen, ist das der Punkt ? Wenn ja, wie finde ich das relativ schnell heraus, gibt es da eine Faustregel oder sehe ich das erst beim zeichnen ?
{1} 0 {2}
&
{1,2} {2,3} {2,3}
Lieben Gruß
Micha
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:38 Sa 13.03.2010 | | Autor: | felixf |
Hallo Micha,
> Ich frage mich , trotz deiner Erklärung die ich verstanden
> zu haben schien, dennoch warum diese beiden Teilmengen als
> unerreichbar gelten ( unten stehend )?
weil du von der Startmenge [mm] $\{ 1, 3 \}$ [/mm] nicht zu [mm] $\{ 1 \}$ [/mm] bzw. [mm] $\{ 1, 2 \}$ [/mm] kommen kannst.
> Ich habe mir diese
> beide Teile mal unten in das Diagramm eingefügt und sehe
> das von den Zuständen nur Bedienungen in Richtung der
> anderen Zustände gehen, ist das der Punkt ?
Ja.
> Wenn ja, wie
> finde ich das relativ schnell heraus, gibt es da eine
> Faustregel oder sehe ich das erst beim zeichnen ?
Durch's Zeichnen findest du es heraus, ansonsten kannst du wie folgt vorgehen: du gehst die Tabelle fuer [mm] $\delta'$ [/mm] durch und markierst wie folgt:
* vor den Startzustand schreibst du ein [mm] \
[/mm]
* du nimmst dir irgendeinen Zustand, vor dem ein \ steht, und markierst die Zustaende, die man von dort erreichen kann (also die in der Tabelle in den rechten beiden Spalten stehen) mit einem [mm] \.
[/mm]
* schliesslich markierst du den Zustand, den du gerade abgearbeitet hast, mit einem X (indem du zu dem \ ein / hinzufuegst)
Dann zeigt dir ein \ an, dass der Zustand erreichbar ist aber noch bearbeitet werden muss, und X sagt dass er erreichbar ist und schon bearbeitet wurde. Sobald vor jedem Zustand nur noch X oder gar nichts steht, bist du fertig, und alle mit X davor sind die erreichbaren.
(Das ist sozusagen eine ![[]](/images/popup.gif) Breitensuche, nur dass du nicht auf einem Baum arbeitest sondern auf einem beliebigen einfachen Graphen.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:28 Sa 13.03.2010 | | Autor: | Giesskanne |
Vielen Dank.
Ich habe eben erneut eine Teilmengenkonstruktion durchgeführt ( http://homepages.fh-giessen.de/~hg12496/afs/nea-dea-1.pdf ) und diese mit der Wikipediaversion erfolgreich hinbekommen. Ich denke es ist zu aufwendig mit der Abarbeitung von jedem möglichem Zustand, wobei man dann sowieso die hälfte davon wieder verwirft.
Hat mir echt weiter geholfen und ich bin wieder einen kleinen Schritt weiter!
Lob and Homepage und Hilfesteller :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:35 Do 25.03.2010 | | Autor: | felixf |
Hallo!
> Vielen Dank.
> Ich habe eben erneut eine Teilmengenkonstruktion
> durchgeführt (
> http://homepages.fh-giessen.de/~hg12496/afs/nea-dea-1.pdf )
> und diese mit der Wikipediaversion erfolgreich hinbekommen.
Super :)
> Ich denke es ist zu aufwendig mit der Abarbeitung von jedem
> möglichem Zustand, wobei man dann sowieso die hälfte
> davon wieder verwirft.
Das stimmt. Deswegen konstruiert man meist nur die, die man eh braucht 
In der Praxis, sprich wenn man einen nicht-deterministischen endlichen Automat am Computer simuliert, konstruiert man die deterministische Darstellung erst gar nicht, sondern arbeitet direkt mit Teilmengen als Zustaenden und erstellt die Uebergangsfunktion "on the fly" (man sollte jedoch vorher die [mm] $\varepsilon$-Uebergange [/mm] loswerden).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:04 So 09.05.2010 | | Autor: | Giesskanne |
Servus,
habe die Klausur im übrigen bestanden, vielen Dank für die Hilfe :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:43 So 09.05.2010 | | Autor: | felixf |
Moin,
> habe die Klausur im übrigen bestanden, vielen Dank für
> die Hilfe :)
das ist ne gute Neuigkeit! Glueckwunsch! Freut mich sehr das zu hoeren :)
LG felix
|
|
|
|
