fb18.de
/ Diplom Informatik
/ Unterbereich Grundstudium
/ Formale Informatik
F2 - Aufgabenzettel 2
kann mir ma jemand sagen was inner aufgabe 2.2. mit "kantenbeschrifteten Graphen" gemeint ist, und davon abgesehn versteh ich die anleitung dazu auch gaaaanich.
thx
Ein "kantenbeschrifteter Graph" ist einfach ein Graph, wo was an den Kanten dransteht *g*. Und wie der Graph nun aussehen soll… hmm… vielleicht mal ein Beispiel:
Sei R = {(1, 1, 2), (1, 2, 2), (2, 1, 3), (2, 3, 3)}
Dann sieht der Graph in etwa so aus:
1, 2 1, 3
1 -------> 2 -------> 3
Jetzt klar?
<edit>Mengenklammern…</edit>
nee doch noch ne frage…
was meinstu in was A definiert ist?
iss A={0,1,2,3} oda iss iss A in R?
dann gäbs ja unendlich viele möglichkeiten
naja is dann ja wahrscheinlich N, aba dann hätte mann auch gleich A={0,1,2,3} schreiben könn…
mmh, ich zweifel noch…
Also ich interpretier das mal als A := {0, 1, 2, 3}, ansonsten wird das mit dem Zeichnen ETWAS schwer…
Entschuldigung !
Der erste Aufgabenzettel wurde noch nich mal in den Gruppen besprochen und schon eine Frage zum neustem Blatt.
Bist du krank oder n workaholic ? :)
Ich hab Privat auch noch n ziemlich vollen stunden plan, so das es mir nur möglich ist alles zu erledigen, wenn ich unter der woche so weit zulege wie es mir möglich ist. Ausserdem iss ja kein verbrechen ;)
Sei R = {(1, 1, 2), (1, 2, 2), (2, 1, 3), (2, 3, 3)}
Dann sieht der Graph in etwa so aus:
1, 2 1, 3
1 -------> 2 -------> 3
Da stellt sich noch ne frage, iss das zufällig hier so, oda iss so ein graph immer kantengerichtet:
wenn nun jetz noch (2,2,3) dabei wär in R, würde der graph da so aussehen?
1, 2 1, 3
1 -------> 2 -------> 3
^ |
|_____2____|
oda so:
1, 2 1,2,3
1 -------> 2 -------> 3
(2,2,3) heißt doch, dass man mit dem Wort "2" (mitte) von Zustand 2 (links) nach Zustand 3 (rechts) kommt, also müsste dein unterer Graf richtig sein.
ach, ja mein fehler, ich meinte ja auch (3,2,2)!
Dann ist es natürlich der erste Graf. [img]
http://www.fb18.de/gfx/23.gif[/img]
ok…ich bin jetzt bei der letzten frage mit dem DFA…
ich versteh leider überhaupt nich was diese erweiterte überführungsfunktion darstellen soll, kann mir ma jemand das prinzip etwas näher erklären.
Davon ma abgesehn, der graph iss doch n DFA graph oda?? Denk ich zumindest…
Jo, isses. Von jedem Zustand aus gibt es pro Wort nur einen Weg, also ist es ein DFA. ALlerdings musst du darauf achten, wie das mit Start und Endzuständen ist. Wenn ich mich richtig erinnere, dann muss ein DFA auch immer genau einen Startzustand haben. Die Menge der Endzustände kann beliebig groß oder auch leer sein.
Die erweiterte Übergangsdingens hab ich nicht mehr genau im Kopf, kannst du das kurz umreißen, was damit gemeint ist? Oder du musst halt auf Slater warten, der weiß das alles noch [img]
http://www.fb18.de/gfx/22.gif[/img]
Hab das in meiner Grenzenlosen Güte nochmal nachgeschlagen [img]
http://www.fb18.de/gfx/25.gif[/img]
Der Unterchied liegt darin, dass du bei der erweiterten ÜF ganze Wörter eintragen kannst, bei der normalen aber nur einzelne Symbole d.h. wenn du da sowas wie d(Z1, abcd) stehen hättest dann wäre das das selbe, als wenn du da
d(d(d(d(Z1,a),b, c, d) stehen hättest. Und bedeuten tut das alles: von Zustand 1 liest du das Zeichen a und gehst in den Folgezustand. Dort liest dud as Zeichen b und gehst in den entsprechenden Folgezustand, usw.
mmmmh…joa…ich sag ma theoretisch verstanden, aba was heisst das für einen gegebenen graphen, nun die EÜF zu finden?
Wozu soll diese funktion nützen, muss der übergang vom start zum endzustand ermittellt werden? Ausserdem steht da mann soll das inner tabelle darstellen, was nun heisst das es mehr zu schreiben geht als eine formel, und wenn das zutrifft glaub ich das ichs dann doch net gerallt hab. Oder geht es darum diese funktion für jede kante anzugeben? Naja ihr merkt schon, ICH HAB KEIN PLAN! ;)
Ich habs in skript nachgeschlagen, hat mir aba leider nix gebracht…nada comprende
zB in diesem fall, wie würde den hier diese EÜF aussehen ungefähr??
Sei R = {(1, 1, 2), (1, 2, 2), (2, 1, 3), (2, 3, 3)}
1, 2 1, 3
1 -------> 2 -------> 3
wenn man lust hat, die einzelnen funktionswerte
aufzuschreiben, könnte man hier das tun:
sei f die überführungsfunktion und ff die erweiterte
überführungsfunktion,
dann folgt aus f(1,1)=2, f(1,2)=2, f(2,1)=3, f(2,3)=3
->
ff(1,1)=2, ff(1,2)=2, ff(2,1)=3, ff(2,3)=3
ff(lambda,1)=1,ff(lamba,2)=2
ff(1,11)=3, ff(1,21)=3, ff(1,13)=3, ff(1,23)=3
äusserst spannend,
in der aufgabe ist das allerdings nirgendwo gefragt oder?,
die frage lautet ob der graph mit den erweiterungen, die da
angegeben sind, ein DFA ist,
die überführungsfunktion als tabelle könnte ich mir so vorstellen:
x\z| 0 | 1 | 2 | 3
--------------------
0 | 0 usw
--------------------
1 |
--------------------
2 |
--------------------
3 |
Morgen.
Ich habe mal eine Frage zu der zweiten Aufgabe.
Ich muß doch x und y in die Formel einsetzen um z zu erhalten?
Beispiel x=1 und y=2.
((1+2)/2)= 3/2 also auf das nächste ganze abgerundet 1.
Sprich ich komme mit (1,2,1) wieder zurück zu 1, also eine Schleife?
Noch ein Beispiel:
x=2 und y=1
((2+1)/2)= 3/2 also wieder 1.
Vom Zustand 2 mit 1 komme ich auf Zustand 1.
Habe ich das so richtig verstanden.
Vielen Dank
Jens
gut, dass ist schön, dass ich das schonmal verstanden habe. Es gibt dann durch das abrunden zum Teil auch mehrere Möglichkeiten von einem Zustand in den nächsten zu kommen.
Beispiel
(0,1,0) hat das gleiche Resultat wie (0,0,0).
Danke
Jens
Hä???
Ich habs so verstanden, dass x,y,z jeweils ganze Zahlen sind und nicht durch abrunden oder so dazu gemacht werden???
"Help, I need somebody…"
x,y sind natürliche zahlen,
und irgendwo wird (x+y)/2 benötigt (=z),
das muss nicht immer natürlich sein ((1+2)/2 = 1.5),
deswegen wird dort abgerundet
thx für dein post mit dem graph slater.
ich hab allerdings noch 2 fragen:
1. was is der unterschied zwischen der ÜF und der EÜF?
2. Ich dachte lambda iss was mit scheme, was hat das hier zu suchen?
Eine Überführungsfunktion beschreibt, wie sich der Zustand des Automaten verändert, wenn EIN Symbol gelesen wird. Die erweiterte ÜF dagegen betrachtet ganze Wörter, also kein, ein oder mehrere Symbole gleichzeitig. Lambda bezeichnet dabei einfach das leere Wort, also das Wort, das aus keinem Symbol besteht.
Nee, dat mit (x+y)/2=z is mir klar. aber wenn(x,y,z)€ R Und R sich aus A x A x A ergibt, A :={0,…,3} dann denk ich, dass auch z ne natürlich Zahl sein muss. Schließlich krieg muss ich doch auch z in A finden. Ist A:={0,1,2,3} oder gehört da noch mehr rein?
Komm mir langsam echt voll blöd vor! Ick werd noch meschugge!
Also: A = {0,1,2,3}, und z \in A
Aber da auf der linken Seite der Gleichung floor(…) steht, ist das alles kein Problem.
Also die drei Punkte in der Definition von A bedeuten, dass z auch abgerundet werden kann? Wusst ich nich. Wurd das in F1 schon mal besprochen? Son Mist. Da sitzt man an ner Aufgabe, freut sich, dass man da irgendwie was rausgekriegt hat und das alles irgendwie logisch klingt und dann machen einem 3 Punkte nen Strich durch die Rechnung! Hätte das nich irgendwo mal erwähnt werden können? KOTZ, na dann fang ich noch mal von vorn an. Vielen Dank. Gibt es sonst noch irgendwelche Sachen, die nich ausdrücklich dastehen, sondern interpretiert werden müssen?
Also die drei Punkte in der Definition von A bedeuten, dass z auch abgerundet werden kann?
Nein, die 3 Punkte bedeuten genau das, was man erwartet: dass 1 und 2 auch zu A gehören. z an sich wird auch nie gerundet, nur die linke Seite der Gleichung.
Nöö, schnall ich nich. WO steht das? Denkst du dir das aus (is um Gottes Willen nich bös gemeint)? Warum soll ich das runden. Wenn du mir das begreiflich machst, dann hast dir das Bundesverdienstkreuz verdient! Und überhaupt: Bei mir ist der Graph auchnich das ZÜD für (ii). Da bei mir Endzustand 3 von Startzustand 0 gar nicht erreicht wird!
Warum soll ich das runden.
Also bei mir stehen um (x+y)/2 diese komischen senkrechten Striche mit Haken unten dran (auch bekannt als floor). Und das ist nunmal gleichbedeutend mit abrunden.
Da bei mir Endzustand 3 von Startzustand 0 gar nicht erreicht wird!
Das ist auch nirgendwo gefordert!
Also die drei Punkte in der Definition von A bedeuten, dass z auch abgerundet werden kann? Wusst ich nich. Wurd das in F1 schon mal besprochen? Son Mist. Da sitzt man an ner Aufgabe, freut sich, dass man da irgendwie was rausgekriegt hat und das alles irgendwie logisch klingt und dann machen einem 3 Punkte nen Strich durch die Rechnung! Hätte das nich irgendwo mal erwähnt werden können? KOTZ, na dann fang ich noch mal von vorn an. Vielen Dank. Gibt es sonst noch irgendwelche Sachen, die nich ausdrücklich dastehen, sondern interpretiert werden müssen?
;)))))),
genial, das ist ja wohl absicht oder?
sonst:
x ist 0 oder 1 oder 2 oder 3
y ist 0 oder 1 oder 2 oder 3
keine diskussion? gut
(x+y)/2 ist nicht unbedingt eine natürliche zahl,
also rundet man da
z = floor((x+y)/2) ist dann eine natürliche zahl,
damit ist z auch eine natürliche zahl (0 oder 1 oder 2 oder 3)
A = {0..3} <=> A = {0,1,2,3} und das hat keine weitere mysteriöse bedeutung,
noch mal anders:
z ist eine natürliche zahl nach definiton (z e A),
aber um z in der überführungsfunktion zu BERECHNEN (AUS x und y) muss halt eine ANDERE zahl, die nicht natürlich ist ((x+y)/2) erst ABGERUNDET werden, um damit eine zahl zu erhalten, die die anforderung, natürlich zu sein, erfüllt, und damit als z geeignet ist,
x ist 1 oder 2 oder 3
y ist 1 oder 2 oder 3
keine diskussion? gut
*diskutier*
0 ist auch erlaubt!
Wat? Da ist ein floor? Bei mir nich! Hört sich jetzt vielleich wirklich blöd an, aber auf meinem Ausdruck ist um x+y nur Betragszeichen…
Also falls da wirklich floor um den gesamten Audruck (x+y)/2 ist, dann 100 mal sorry. Ich schau mal noch mal das AB auf der m-site an.
Ich glaub mein schwein pfeift…
ach slater du weisst doch was ich mein…hab mich halt verschrieben, das L(M) such ich natürlich :) und was das L(M) iss weiss ich auch nich, deswegen ja die frage [img]
http://www.fb18.de/gfx/24.gif[/img]
L(M) ist die akzeptierte sprache, das steht doch sicher ganz säuberlich im skript definiert,
und ist in diesem fall nicht allzu wortreich..
Wat? Da ist ein floor? Bei mir nich! Hört sich jetzt vielleich wirklich blöd an, aber auf meinem Ausdruck ist um x+y nur Betragszeichen…
Dann solltest Du mal Deinen Drucker untersuchen lassen, bei mir war das immer das erste Zeichen eines total verdreckten Druckkopfs [img]
http://www.fb18.de/gfx/24.gif[/img]
Also in meiner Version (und auch in der online Version auf
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS03/F2/F2aufg02.pdf.gz ) ist da ein floor - Betragsstriche wuerden da auch wenig Sinn machen, die Summe zweier positiven Zahlen ist ja schon positiv.
JO, habs jetzt auch gesehen, zum Glück noch rechtzeitig.
Ich denk mal, ich muss die Patrone wieder nachfüllen
Hab noch mal ne Frage zu 2.2 (ii):
Wenn z= 0; heißt das, dass der Startzustand auf jeden Fall {0} sein muss oder gilt dann jeder Zustand als möglicher Startzstand?
Ich hab jetzt die Aufgabe nicht vorliegen, aber wenn es sich um einen DFA handelt, dann gibt es immer genau einen Startzustand.
Mmmh, na dann is bei mir der Graph aus (i) nicht das Zustandübergangsdiagramm für den benannten DFA aus (ii), da dort der Endzustand {3} nicht von 0 aus erreicht werden kann, das is nur von 3 aus selbst über 3 möglich.
Denn es gilt ja: floor((3+3)/2) = 3. Für y=4 ginge es auch noch, aber das is ja dann nich mehr in A!
Oder lieg ich da wieder mal falsch?
Mmmh, na dann is bei mir der Graph aus (i) nicht das Zustandübergangsdiagramm für den benannten DFA aus (ii), da dort der Endzustand {3} nicht von 0 aus erreicht werden kann, das is nur von 3 aus selbst über 3 möglich.
Oder lieg ich da wieder mal falsch?
Ja. Nirgendwo ist gefordert, dass ein Endzustand erreichbar sein muss.
Ich dachte schon, da ja unter (ii) steht: Zend ={3}
Wird damit nicht explizit ausgedrückt, dass der Endzustand unbedingt die 3 sein muss?
Wenn nicht, wozu dient dann überhaupt diese Angabe?
Der einzige Endzustand ist die 3, und dieser ist nicht erreichbar. Soweit richtig. Jetzt folgerst Du, dass dieses Ding deshalb kein DFA ist. Und der Schluss ist IMHO nicht richtig.
IMHO?
Und warum ist das dann nich richtig? Die 3 wird doch da nich erreicht. Es ist doch nunmal gefragt, ob der spezielle Graph aus (i) das ZÜD für den DFA M=(A,A,*dieseskomischeZeichen*,0,{3})ist. Und dafür ist der Graph ja nun mal nich das ZÜD.
Oder steh ich mal wieder voll auf der Leitung?
Und dafür ist der Graph ja nun mal nich das ZÜD.
Warum? Deine bisherige Argumentation überzeugt mich noch nicht wirklich.
ein DFA ist eine menge von zuständen Z,
ein startzustand aus Z,
eine menge von endzuständen Z' teilmenge Z,
ein alphabet A und
eine überführungsfunktion Z x A -> Z, die nicht total sein muss,
aber keine zwei regeln enthalten darf, auf grund derer man die möglichkeit hat von einem zustand mit einem gelesenen symbol zwei verschiedene folgezustände zu erreichen,
mehr anforderungen an einen DFA gibt es nicht, die angegebenen gilt es zu überprüfen
und insofern ist es unerheblich, ob der endzustand erreichbar ist oder nicht
Hm, also ich habe auch ein paar Probleme mit 2.2.2. Für mich ist es auch kein DFA, da der Endzustand niemals erreichbar sein kann. Nun bin ich mir aber nicht ganz sicher, ob der Endzustand unbedingt erreicht werden muß, damit man von einem DFA sprechen kann. Wer hat dafür eine klare Antwort, im Script habe ich dazu nichts gefunden.
MFG
takahara
Nirgendwo ist gefordert, dass ein Endzustand erreichbar sein muss.
Ich sollte das in meine Signatur schreiben…
Für mich ist es auch kein DFA, da der Endzustand niemals erreichbar sein kann.
Hat Slater das nicht gerade gepostet? [img]
http://www.fb18.de/gfx/22.gif[/img] Ein DFA muss KEINEN Endzustand habenm Die leere Menge ist auch eine Menge Z' die Teilmenge von Z ist…
Falls du es schriftlich willst [img]
http://www.fb18.de/gfx/7.gif[/img] In meiner Ausgabe steht auf Seite 51 (Nach Definition 3.2 falls die Seite nicht stimmt):
Offensichtlich kann ein DFA auch die leere Menge akzeptieren. Dazu muss nur die Menge Z_end der Endzustände als leere Menge definiert werden, was ja nicht ausgeschlossen wurde!
Case closed [img]
http://www.fb18.de/gfx/22.gif[/img]
Falls du es schriftlich willst [img]http://www.fb18.de/gfx/7.gif[/img] In meiner Ausgabe steht auf Seite 51 (Nach Definition 3.2 falls die Seite nicht stimmt):
Das hat jetzt aber nichts mit dem Problem zu tun, oder? Im gegebenen Fall existiert ja ein Endzustand, nur fuehrt kein Weg da hin. Das aendert natuerlich nichts an der Tatsache, dass das Ding ein DFA ist.
Upsa, verlesen [img]
http://www.fb18.de/gfx/8.gif[/img] aber ich finde ncoh was [img]
http://www.fb18.de/gfx/22.gif[/img]
Dann halt so…sei A ein Automat:
+----+ +----+
||z0 | | z1||
+----+ +----+
z_0 sei der Anfangszustand, z_1 der Endzustand, keine Pfeile.
A ist also = ({z0, z1}, {a}, 0, z0, {z1})
Dann ist A ein Automat, denn er erfüllt die Bedingungen:
{z0, z1} ist eine endliche Menge von Zuständen
{a} ist ein endliches Eingabealphabet
0 (leere Menge) ist eine Teilmenge von {z0,z1} X {a} –> Z (die leere Menge ist immer Teilmenge)
z0 ist ein Startzustand
{z1} ist eine Teilmenge von Z der Endzustände.
Also ist A ein DFA. Wie man sieht ist dies ein DFA, auch wenn der Endzustand nicht erreicht wird und wenn das hier geht, dann geht das auch bei anderen DFAs :)
Oh, na da hab ich aber ne Welle angekurbelt. Aber schön, dass wenigstens einer meiner Meinung ist.
Sicher MUSS ein DFA keinen Endzustand haben, aber wenn doch in der Aufgabenstellung ein ganz bestimmter Endzustand - nämlich {3} - explizit angegeben ist und keine (unbestimmte) Menge von Endzuständen, dann gehe ich davon aus, dass auch genau dieser Endzustand vorausgesetzt wird. Denn sonst wäre ja die Angabe Zend ={3} vollkommen überflüssig.
Naja, egal was richtig ist: Eines wurde auf jeden Fall mit dieser Aufgabe erreicht: Man/ Frau beschäftigt sich zur Genüge damit und wälzt die Skripte. Halleluja Mr. Jantzen…!!
Oh, na da hab ich aber ne Welle angekurbelt. Aber schön, dass wenigstens einer meiner Meinung ist.
wenn du takahara meinst, dann solltest du die meinung schnellstens ändern ;)
Sicher MUSS ein DFA keinen Endzustand haben,
richtig
aber wenn doch in der Aufgabenstellung ein ganz bestimmter Endzustand - nämlich {3} - explizit angegeben ist und keine (unbestimmte) Menge von Endzuständen, dann gehe ich davon aus, dass auch genau dieser Endzustand vorausgesetzt wird.
dem widerspricht niemand,
dieser endzustand wird als endzustand des DFA (wenn es denn einer ist) vorausgesetzt,
nicht aber, dass er erreichbar ist (was zwei völlig verschiedene eigenschaften sind..)
Denn sonst wäre ja die Angabe Zend ={3} vollkommen überflüssig.
richtig, ist nicht überflüssig, gibt genau den endzustand an, und das ist doch ok so
Naja, egal was richtig ist: Eines wurde auf jeden Fall mit dieser Aufgabe erreicht: Man/ Frau beschäftigt sich zur Genüge damit und wälzt die Skripte. Halleluja Mr. Jantzen…!!
hmm?
ein endzustand kann übrigens auch einen zweck haben wenn er unerreichbar ist,
das hat nämlich interessante auswirkungen auf die akzeptierte sprache des DFA..
Wie sieht der Graph eigentlich bei (0,0,0) oder (1,2,1)aus?
Gibt es "nur" 16 solcher Mögichkeiten die wir beachten müssen???
(0,0,0) das ist ein pfeil der vom zustand 0 aus sich ein wenig vom zustand entfernt, dann im leichten bogen 90 grad wendet und zum zustand 0 zurückkehrt, beschriftet mit 0,
heisst dann schleife und da gibts sicher im skript ein paar graphische beispiele,
16 möglichkeiten, ja
