FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI-1 Blatt 10

FGI-1 Blatt 10 2010-06-18 20:14
Anonymer User
Hi,

ist es erlaubt den Zustand q3 (zugleich auch Startzustand) wegzustreichen, da dieser nie erreicht wird?

RE: FGI-1 Blatt 10 2010-06-18 20:15
Anonymer User
War auf die Übungsaufgabe 10.2 bezogen…

RE: FGI-1 Blatt 10 2010-06-18 20:21
Wulf
Ein Startzustand der nicht erreicht wird? Wer baut denn sowas?!

Gib mal Link zum Blatt.

RE: FGI-1 Blatt 10 2010-06-18 20:26
Anonymer User
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe10/fgi1-a10.pdf

RE: FGI-1 Blatt 10 2010-06-18 20:29
Wulf
"Es ist hierbei das Ziel, das in der Vorlesung beschriebene Verfahren korrekt anzuwenden!"

Ich kenn das Verfahren nicht. Steht da was entsprechendes drin?
Ich würde spontan vermuten, dass man überhaupt keine Zustände entfernen darf.

RE: FGI-1 Blatt 10 2010-06-18 20:31
Anonymer User
Die Übergangstabelle habe ich erstellt. Nun muss ich den Automaten zeichnen, weiss aber nicht, ob ich den Startzustand q3 weglassen kann, weil dieser nicht erreicht wird und wir insgesamt ja sowieso 2 Startzustände hätten.

RE: FGI-1 Blatt 10 2010-06-18 21:32
UncleOwen
q3 wird doch erreicht. Beispielsweise mit dem leeren Eingabewort, oder mit bb. Ausserdem ist nicht Minimierung die Aufgabe, sondern Anwendung des Algorithmus - und der streicht keine Zustände.

RE: FGI-1 Blatt 10 2010-06-18 23:29
Anonymer User
Ich hab da ein Diagramm mit drei Endzuständen, elf Kanten und drei Schleifen raus bekommen.

RE: FGI-1 Blatt 10 2010-06-19 00:55
Wulf
Ich hab da ein Diagramm mit drei Endzuständen, elf Kanten und drei Schleifen raus bekommen.

Ich kenn ja den Algorithmus nicht.. aber ich krieg was anderes raus ;-)

RE: FGI-1 Blatt 10 2010-06-19 01:30
Anonymer User
Ich kenn ja den Algorithmus nicht..
http://www.informatik.uni-hamburg.de/WSV/teaching/vorlesungen/FGI1SoSe10/1_Endliche_Automaten.pdf
S. 47

RE: FGI-1 Blatt 10 2010-06-19 13:12
T4Y
q3 wird doch erreicht. Beispielsweise mit dem leeren Eingabewort, oder mit bb. Ausserdem ist nicht Minimierung die Aufgabe, sondern Anwendung des Algorithmus - und der streicht keine Zustände.

Richtig. Am besten du guckst dir nochmal das Verfahren auf Folie 7 genauer an. Mal dir am besten zu Satz 14.1 ein Beispiel auf und guck, wann genau was für eine Kante hinzugenommen wird, wenn man e-Kanten entfernt. (Die Seite davor ist ja auch ein Beispiel)

RE: FGI-1 Blatt 10 2010-06-19 14:08
Anonymer User
Ich hab da ein Diagramm mit drei Endzuständen, elf Kanten und drei Schleifen raus bekommen.

Hm.. bei mir sinds zwar auch drei Endzustände, aber nur sieben Kanten und eine Schleife.

RE: FGI-1 Blatt 10 2010-06-19 16:48
Anonymer User
Ich hab 3 Endzustände, 10 Kanten, 2 Schleifen und 2 Schlingen raus.

RE: FGI-1 Blatt 10 2010-06-19 17:29
T4Y
Ich hab 3 Endzustände, 10 Kanten, 2 Schleifen und 2 Schlingen raus.

Schleife = Schlinge (http://de.wikipedia.org/wiki/Glossar_Graphentheorie#Schleife)
Aber sonst hab ich das gleiche.

RE: FGI-1 Blatt 10 2010-06-20 15:06
Anonymer User
Hm.. bei mir sinds zwar auch drei Endzustände, aber nur sieben Kanten und eine Schleife.
Das hab ich auch :) Mal gucken was letzendlich richtig ist…

RE: FGI-1 Blatt 10 2010-06-20 15:27
T4Y
Komisch, dass die Ergebnisse so unterschiedlich sind. Vielleicht hilft dem einen oder anderen auch das folgende Beispiel zu der Aufgabe: http://eiche.theoinf.tu-ilmenau.de/lehre/afs_ss03/epsilon-kanten.pdf

Scheint ein sehr ähnliches Verfahren zu sein.

RE: FGI-1 Blatt 10 2010-06-20 15:28
Wulf
So, Algorithmus gelesen und angewandt (danke für den Link); nun komm ich auch auf 3+7+1.

RE: FGI-1 Blatt 10 2010-06-20 16:05
T4Y
Ich merke, dass ich den Satz falsch gelesen habe [25] Wenn ich die Epsilon-Pfade "rein" halte, komm ich jetzt auch auf 3,7,1

RE: FGI-1 Blatt 10 2010-06-21 15:54
theorinix
Komisch, dass die Ergebnisse so unterschiedlich sind. Vielleicht hilft dem einen oder anderen auch das folgende Beispiel zu der Aufgabe: http://eiche.theoinf.tu-ilmenau.de/lehre/afs_ss03/epsilon-kanten.pdf

Scheint ein sehr ähnliches Verfahren zu sein.

Mag wohl sein, aber das Verfahren aus dem Skript ist
1. anders als das in Vossen Witt
und
2. anders als das aus Ilmenau
und
3. sollte benutzt werden!
Hier geht es mehr um die in FGI-1 dargestellte und verwendete Methode und nicht um das Endergebnis!!

RE: FGI-1 Blatt 10 2010-06-22 18:29
Anonymer User
Mag wohl sein, aber das Verfahren aus dem Skript ist
1. anders als das in Vossen Witt
und
2. anders als das aus Ilmenau
und
3. sollte benutzt werden!
Hier geht es mehr um die in FGI-1 dargestellte und verwendete Methode und nicht um das Endergebnis!!

Dafür wäre ein realistischerer Beispiel-Automat im Skript super gewesen. Dem Thread nach zu urteilen ist es halt uneindeutig. Aber seis drum.

RE: FGI-1 Blatt 10 2010-06-22 18:56
Wulf
Dem Thread nach zu urteilen ist es halt uneindeutig.

Die formale Definition im Skript ist eindeutig.