Hallo alle zusammen,
Ich habe gleich zwei Fragen zu der ersten Aufgabe:

1. Was ist mit der Rechnung der Wörter gemeint?
2. Sollen nur die Wörter akzeptiert werden, die auch der Automat akzeptiert? Denn wenn ja, dann gibt es meiner meinung nach gar keinen NFA, oder irre ich mich?

EDIT: GNA, ist es denn wirklich so schwer mal das F2 or whatever dazuzuschreiben?

Die Anmeldung scheint einigen aber auch schwer zu sein. Ich kann das ja verstehen, dass es zu großer Zeitaufwand ist und überhaupt… na ja

Also zur Antwort, weiter im Skript bei den NFAs wird das mit der Rechnung erklärt. Muß man ja nicht vollst. hier hinschreiben. Und einen NFA gibt es laut Jantzen bestimmt, sonst hätte er die Frage nicht gestellt.

Zu empfehlen ist auch das Buch "Einführung in die Automatentheorie und Komplexität" (oder so ähnlich) von Ullman. In der Bibl. zu bekommen.

1. Was ist mit der Rechnung der Wörter gemeint?

Kurzgesagt ist das der Weg, den du durch den Automaten gehst.
Die Notation müsstest du allerdings shcon im Skript nachschlagen, ich glaube sowas wie Zustand, Pfeil mit Buchstabe drüber, Zustand oder so,

2. Sollen nur die Wörter akzeptiert werden, die auch der Automat akzeptiert?

Falls du den äquivalenten NFA meinst. Die Definition von Äquivalent ist doch gerade, dass die Sprachen der beiden NFAs gleich sind.

Denn wenn ja, dann gibt es meiner meinung nach gar keinen NFA, oder irre ich mich?

Würde ich atm auch tippen, solltest das aber gut begründen [img]http://www.fb18.de/gfx/22.gif[/img]

Denn wenn ja, dann gibt es meiner meinung nach gar keinen NFA, oder irre ich mich?

Würde ich atm auch tippen, solltest das aber gut begründen [img]http://www.fb18.de/gfx/22.gif[/img]

Och, zu jedem DFA gibt es mindestens einen äquivalenten NFA, nämlich ihn selber… Nur die Frage, ob es einen KLEINEREN äquivalenten NFA gibt, wage ich auch mal zu bezweifeln (gibts da 'ne anständige Begründung für, ausser alle 2^10 NFAs mit 2 Zuständen durchzuprobieren?)

Nur die Frage, ob es einen KLEINEREN äquivalenten NFA gibt, wage ich auch mal zu bezweifeln (gibts da 'ne anständige Begründung für, ausser alle 2^10 NFAs mit 2 Zuständen durchzuprobieren?)

Ja, gibt es, ne ähnliche Aufgabe hatten wir im letzten Jahr. Das kann man bei diesem hie rgut begründen, wenn man sich die Sprache anguckt (nicht vergessen, der neue NFA muss jedes Wort bis zum Ende lesen)

Wo wir gerade dabei sind: Wie ist "jedes zu akzeptierende Eingabewort" gemeint? L(A) oder {a,b}*?

Wo wir gerade dabei sind: Wie ist "jedes zu akzeptierende Eingabewort" gemeint? L(A) oder {a,b}*?

Ei, so genau habe ich das wieder garnicht gelesen. Also die Formulierung sagt mir, dass L(A) gemeint ist, die anderen Wörter sind nicht zu akzeptieren. *denk* Ich bleibe aber bei meiner Meinung.

*mehrdenk* unter den Beidngungen soeben revidiert *g*

Ich hätt auch mal 'ne Frage zu Aufgabe 3.2(ii):
Kann es sein, dass es statt
mit $\psi(w_i) \leq^\triangledown \psi(w_{i+1})$
mit $\psi(w_{i_j}) \leq^\triangledown \psi(w_{i_{j+1}})$
heissen muss?

Ich hätt auch mal 'ne Frage zu Aufgabe 3.2(ii):
Kann es sein, dass es statt
mit $\psi(w_i) \leq^\triangledown \psi(w_{i+1})$
mit $\psi(w_{i_j}) \leq^\triangledown \psi(w_{i_{j+1}})$
heissen muss?

Steht da doch?

Steht da doch?

Hmpf. Dann haben die das nachträglich korrigiert, in meine gedruckten Version stehts noch falsch.

ne kurze frage zu 3.1: muss so ein wort unbedingt im endzustand-knoten enden??

damit es akzeptiert wird ja!
Aber nochmal zu 1. Muss man eine Rechnung von jedem zustand aufzeigen also z0->z1 und z1->z2 oder nur von z0->z2???
Gibt es nun ein NFA?

Aber nochmal zu 1. Muss man eine Rechnung von jedem zustand aufzeigen also z0->z1 und z1->z2 oder nur von z0->z2???
Gibt es nun ein NFA?

natürlich alle zwischenstationen, sonst muss man ja nur Start- und Endzustand angeben. Und das wäre bei den meisten Automaten sehr witzlos

was iss den die "rechnung" für ein wort?
die folge der 3er tupel die das wort dann ergeben?
zB abab:
(z0,a,z2),(z2,b,z2),(z2,a,z2),(z2,b,z2)
oda wie jetzt?

was iss den die "rechnung" für ein wort?
die folge der 3er tupel die das wort dann ergeben?
zB abab:
(z0,a,z2),(z2,b,z2),(z2,a,z2),(z2,b,z2)
oda wie jetzt?

Ja, das ist die Rechnung formal aufgeschrieben (Definition 3.11 im Skript (meine Version)).

ach damn tut mir leid das ich gleich mit der darauf folgenden frage wieder ankomme, aba die hat ich auch beim letzten zettel falsch, und in der ü-gruppe wurde mir nich wirklich geholfen. Wenn darum gebeten wird L(A) anzugeben, was wird erwartet? Ich hab schon verstanden das es sich dabei um die akzeptierte sprache handelt, zB baaa, aba wie wird das formal geschrieben um auf so eine frage zu antworten?

ach damn tut mir leid das ich gleich mit der darauf folgenden frage wieder ankomme, aba die hat ich auch beim letzten zettel falsch, und in der ü-gruppe wurde mir nich wirklich geholfen. Wenn darum gebeten wird L(A) anzugeben, was wird erwartet? Ich hab schon verstanden das es sich dabei um die akzeptierte sprache handelt, zB baaa, aba wie wird das formal geschrieben um auf so eine frage zu antworten?

Habt ihr schon die rationalen ausdrücke gehabt?

öööööööööööööööööööööh… weissu das iss relativ relativ ;-)
da ich den dozent nich so recht verstehe bin ich auch nich inner vorlesung, und daran das ich so viele fragen hab, solltest du erkenn das mir das skript auch keine grosse hife iss ;-)

weiss ma jemand schnell ob rationale ausdrücke schon dran waren?

habe das selbe problem. den dozenten versteht man nicht. war aber immer da und denke rationale ausdrücke hatten wir nicht!

Okay, dann müsst ihr die Wörter wohl sprachlich beschreiben. Sowas wie "Alle wörter die mit a anfangen und danach jeweils abwechselnd b und c haben". Ohne rationale Ausdrücke wirds sonst schwer :)

Das L(A) kann man beliebig schreiben. <– Jantzen-Zitat

Entweder formal L(A):= {w element E| bla bla* bla} oder L(A):={die Menge aller Wörter, die…}

Gibt es eigentlich nun dieses äquivalente NFA?

Das hängt ganz davon ab, wie Du die Aufgabenstellung interpretierst.

wieso welche möglichkeiten gibt es denn???

Wo wir gerade dabei sind: Wie ist "jedes zu akzeptierende Eingabewort" gemeint? L(A) oder {a,b}*?

ups… man sollte nicht alles auf sich beziehen! [img]http://www.fb18.de/gfx/8.gif[/img]

oki, und mal profilaktisch gefragt: angenommen ich will das rational ausdrücken, wie würde es dann aussehen?

oki, und mal profilaktisch gefragt: angenommen ich will das rational ausdrücken, wie würde es dann aussehen?

Was willst du denn ausdrücken [img]http://www.fb18.de/gfx/28.gif[/img]

ich wil sagen das L(A) die sprache ist die alle wörter akzeptiert die mit b als ersten buchstaben haben, wo mann dann beliebig viele a's ranhängen kann. und nur b. und das leere Wort.

ich wil sagen das L(A) die sprache ist die alle wörter akzeptiert die mit b als ersten buchstaben haben, wo mann dann beliebig viele a's ranhängen kann. und nur b. und das leere Wort.

Das wäre dann wenn ich mich richtig erinnere:

\lambda + (b(a)*)

das + bedeutet oder, der * bedeutet 0 oder beliebig viele. Siehe auch 3.4 Rationale Ausdrücke

k, und zu dem DFA A' der kleiner iss als A aba seine sprache aktzeptiert, ich würde sagen das es ihn gibt:

z0---b--->z1-----| ^__a__| wobei z0 start und endzustand und z1 endzustand
oda gibt es da einsprüche?

k, und zu dem DFA A' der kleiner iss als A aba seine sprache aktzeptiert, ich würde sagen das es ihn gibt:

z0---b--->z1-----| ^__a__| wobei z0 start und endzustand und z1 endzustand
oda gibt es da einsprüche?

Sofern die Aufgabe so gelesen wird, dass nur die Wörter aus L(A) zuende gelesen werden müssen sehe ich nur einen Einwand. lambda (leeres wort) wird noch nicht ankzeptiert :)

öhm, ich meinte doch wobei z0 start und endzustand ist, heisst das den nich das lambda drin ist. oda war das jetzt n wink das ich mit meiner akzeptierten sprache falsch liege ?

öhm, ich meinte doch wobei z0 start und endzustand ist, heisst das den nich das lambda drin ist. oda war das jetzt n wink das ich mit meiner akzeptierten sprache falsch liege ?

Ne, ein wink, dass ich mich verlesen habe [img]http://www.fb18.de/gfx/28.gif[/img]

Ich hab L(A) auch mit Worten geschrieben, denn ich kann mich nich erinnern, dass wir in der Vorlesungen mit den benannten Ausdrücken gearbeitet haben.

Aber mal was anderes: Ich hab da ein Verständnisproblem bei 3.2(i)

Soll da nach den Ziffern -wenn gleiche Länge von x und y; im Beispiel also 2- oder nach den Buchstaben (drei < zwei) geordnet werden?

Denn 3 is ja nur kleiner als 2, wenn man die Anfangsbuchstaben betrachtet…

Aber mal was anderes: Ich hab da ein Verständnisproblem bei 3.2(i)

Soll da nach den Ziffern -wenn gleiche Länge von x und y; im Beispiel also 2- oder nach den Buchstaben (drei < zwei) geordnet werden?

Denn 3 is ja nur kleiner als 2, wenn man die Anfangsbuchstaben betrachtet…

Naja, es soll so geordnet werden, wie da definiert [img]http://www.fb18.de/gfx/25.gif[/img]

Im Beispiel ist [img]http://mokrates.homeip.net/cgi-bin/texstring?(3,4)%20%5Cleq%5E%7B%5Cbigtriangledown%7D%20(2,5)[/img], da [img]http://mokrates.homeip.net/cgi-bin/texstring?aaabbbb%20%5Cpreceq%5E%7Blg-lex%7D%20aabbbbb[/img].

<edit>JAAAAAAAA, es funktioniert!</edit>

Aso, und welche Definition aus dem Skript soll man dafür anpassen? Ich dachte es wär 2.57 und 2.58.

Aber irgenwie passt das ja doch nich.

Ich vermute mal, dass man die Definition von lg-lex als Vorlage verwenden soll.

k, und zu dem DFA A' der kleiner iss als A aba seine sprache aktzeptiert, ich würde sagen das es ihn gibt:


z0—b—>z1—–|
^__a__|



wobei z0 start und endzustand und z1 endzustand

das ist doch aber immer noch ein DFA oder nicht?

das ist doch aber immer noch ein DFA oder nicht?

Ja, und? Jeder DFA ist auch ein NFA.

Ja, aber da gibt es doch mehrere, wenn ich das richtig sehe. So ist 2.58 die Def. für lg-lex auf m-Tupeln (Vektoren).

Ist die Ordnung dann so richtig? w2<w5<w3<w4<w1 Muss man da dann noch viel bla drumrumschreiben, oder würde dat so reichen?

ist def. 2.52 nicht besser zum abändern geeignet?

Hm, ich hab für die Aufgabe auch Def. 2.52 als Vorlage genommen; aber was mit ii) gemeint ist versteh ich nicht.

das ist doch aber immer noch ein DFA oder nicht?

Ja, und? Jeder DFA ist auch ein NFA.

ööö, was ist den der unterschied zwischen DFA und NFA, praktisch gesehen (was das skript sagt weiss ich, ich verstehs nur nich ;) )??

Ich *glaube* bei einem DFA gibt es von einem Zustand z1 in den nächsten Zustand z2 immer nur eine Möglichkeit, also einen Kantenzug. Beim NFA kann es von z1 auch mehrere Kanten zu z2 geben.

Vor allem können bei einem NFA auch von einem Zustand aus mehrere Kanten zu verschiedenen Folgezuständen aber dem gleichen gelesenen Zeichen existieren, so dass eben nicht eindeutig ist, in welchem Zustand sich der Automat befindet, wenn z.B. ein 'a' gelesen wurde, weil sowohl Z1 als auch Z2 entsprechender Folgezustand sein könnten (zusammenhangloses Beispiel).

Nochmal zu 3.2
i) Wie soll die Ordnung denn Aussehen? was bedeutet denn eigentlich: a1(hoch)x1, <lexlg-lex a1(hoch)y1
Kann mir Jemand mal diese Ordnung erklären?

ja, würde mich auch intressieren…

Wenn ich das richtig sehe, soll das so sein:

Seien a_1, a_2 etc. sortierte Buchstaben, also a_1 muss vor a_2 vor a_3 etc. liegen. Dann bedeutet a_1^x_1 z.B. das x_1-fache hinschreiben von a_1. So, die Ordnung soll nun so aussehen: Wenn man ein Tupel nimmt (x_1, x_2, x_3, …) erhält man das dazugehörige Wort, indem man x_1-mal den kleinsten Buchstaben hinschreibt, x_2-mal den zweitkleinsten etc. Genauso verfährt man mit dem zweiten Tupel (y_1, y_2, y_3, …). jetzt soll das x-Tupel genau dann kleiner/gleich dem y-Tupel sein, wenn das Wort was man beim x-Tupel rausbekommt nach lg-lex kleiner/gleich ist, also im Lexikom vorher stehen würde [img]http://www.fb18.de/gfx/28.gif[/img].

Hoffe das hilft fürs verständnis der Aufgabe

jo, das is jetzt (eigentlich) klar, weiß aber trotzdem immer noch nich, womit man das am besten definieren kann. Wenn ich das richtig verstanden habe, dann gilt Def. 2.52 im Skript für Buchstaben. Aber bei der Aufgabe soll das ganze doch trotzdem über Zahlen laufen. Würde sich da nich die Def. 2.58 eignen? Im Prinzip laufen doch beide auf das gleiche raus…

Was haben die anderen so (außer die 2, die dazu schon gepostet haben)?

Und wie schreibt man unter (ii) die Ordnung auf. Da es da 4 Punkte gibt, denke ich, dass es nicht ausreicht, einfach nur die < Beziehungen in einer Reihe zu schreiben, oder!?

jo, das is jetzt (eigentlich) klar, weiß aber trotzdem immer noch nich, womit man das am besten definieren kann. Wenn ich das richtig verstanden habe, dann gilt Def. 2.52 im Skript für Buchstaben. Aber bei der Aufgabe soll das ganze doch trotzdem über Zahlen laufen. Würde sich da nich die Def. 2.58 eignen? Im Prinzip laufen doch beide auf das gleiche raus…

Sie sind ähnlich, ich würde sagen, vermutlich kann man es am besten in der Art von 2.57 machen. Auf jeden Fall mutet die Bemerkung zu 3.2 an, dass man eine der Definitionen gut ausschlachten kann.

Und wie schreibt man unter (ii) die Ordnung auf. Da es da 4 Punkte gibt, denke ich, dass es nicht ausreicht, einfach nur die < Beziehungen in einer Reihe zu schreiben, oder!?

Es steht nichts anderes als Aufgabe da, von daher würde ich vermuten, dass das alles ist. Die Parikh-Abbildung sieht aber ansich auhc shcon schlimm genug aus [img]http://www.fb18.de/gfx/22.gif[/img]

Wieso, was ist denn die Parikh-Abbildung?
Steht dazu was im Skript?

Schau doch nach ?!
Ich hab nichts gefunden.

Wieso, was ist denn die Parikh-Abbildung?
Steht dazu was im Skript?

So genau kenne ich das Skript nicht mehr, denke nein. Aber aufgabe 3.2 definiert die Parikh-Abbildung doch gerade

Ansonsten schau in http://3773.rapidforum.com/topic=101684853908&search=&reverse=1 dort habe ich geraten was sie wohl macht [img]http://www.fb18.de/gfx/22.gif[/img]

Also ich komme immernoch nicht mit der Aufgabe 2. i) klar!
Wie soll man dass denn definieren?!
Ich habe nun zwar endlich verstanden was da von mir verlangt wird aber eine deifnition? - Fehlanzeige! Wer kann mir noch einige nützliche Tipps geben? Oder bin ich schon hoffnungslos verloren?!

Also den Unterschied von DFA zu NFA ist mir auch immer noch nicht so wirklich klar.
Die Frage dabei ist ob beim DFA von einem Zustand nur eine oder genau eine Kante mit jedem Buchstaben abgehen kann.
Das macht ja einen großen Unterschied.
Beim NFA können ja auf jeden Fall mehrere Kanten mit dem gleichen Buchstaben abgehen.

Die Frage dabei ist ob beim DFA von einem Zustand nur eine oder genau eine Kante mit jedem Buchstaben abgehen kann.

In einem DFA darf von einem Zustand pro Buchstabe höchstens eine Kante abgehen. Wenn pro Zustand/Buchstabe genau eine Kante abgeht, nennt man es einen vollständigen DFA.

Aber die Frage die ich mir stelle ist jetzt, ob der NFA, den jemand da vor n paar Seiten hingemalt hat (mit den 2 Zuständen) wirklich äquivalent zu A ist… ich meine, er hätte ja keinen Zustand, der nicht Endzustand ist…
Bei A führen ja alle falschen Eingaben zum Nicht-Endzustand, aus dem man auch nciht mehr rauskommt, bei dem NFA hier führen aber soweit ich sehe alle falschen Eingaben zu gar nichts, sie sind einfach nciht vorhanden… ist der NFA damit denn äquivalent? Ich würde jetzt sagen nein. Belehrt mich eines Besseren, wenn ich mich irre. :)

äquivalent sind sie, wenn sie die gleiche sprache akzeptieren,
du must also für dein 'nein' ein wort finden, das der eine akzeptiert und der andere nicht,

ob jedes einbabewort bis zum ende gelesen werden kann ist ein anderes problem,
und dass das in diesem beispiel besonders problematisch ist wurde ja schon aussreichend diskutiert

Bei A führen ja alle falschen Eingaben zum Nicht-Endzustand, aus dem man auch nciht mehr rauskommt, bei dem NFA hier führen aber soweit ich sehe alle falschen Eingaben zu gar nichts, sie sind einfach nciht vorhanden… ist der NFA damit denn äquivalent? Ich würde jetzt sagen nein. Belehrt mich eines Besseren, wenn ich mich irre. :)

Zwei NFAs sind äquivalent, wenn sie die selbe Sprache akzeptieren, d.h. L(A) = L(B). EIn NFA akzeptiert ein Wort, wenn er es bis zum Ende lesen kann un ddann in einem Endzustand ist. Von daher würd eich sagen, nicht akzeptierte Wörter müssne nicht bis zum Ende gelesen werden.

Ja, aber in diesem NFA, der ja von z0 (Start- und Endzustand) aus nur die Kante mit "b" hat und keine mit "a" … Was macht der, wenn er zu Anfang ein "a" bekommt? Wenn er dann einfach in z0 bleibt, wäre er ja nicht mehr äquivalent.

Ja, aber in diesem NFA, der ja von z0 (Start- und Endzustand) aus nur die Kante mit "b" hat und keine mit "a" … Was macht der, wenn er zu Anfang ein "a" bekommt? Wenn er dann einfach in z0 bleibt, wäre er ja nicht mehr äquivalent.

Sobald ein Wort nicht weitergelesen kann, wird es nicht akzeptiert. Er bleibt also nicht in irgendeinem zustand sondern weist das Wort sofort ab.

Ah, OK, das war was ich wissen wollte :)
Steht das auch irgendwo im script dmait ich nen Beleg für den Aufgabenzettel hab? (nicht "Der Triphoenix hat gesagt, …" ;))

Ah, OK, das war was ich wissen wollte :)
Steht das auch irgendwo im script dmait ich nen Beleg für den Aufgabenzettel hab? (nicht "Der Triphoenix hat gesagt, …" ;))

Nun die akzeptierte Sprache eines NFAs ist definiert in 3.9. Dort steckt drin, dass nicht zuende gelesene Wörter nicht akzeptiert werden, denn die Überführungsfunktion bildet dabei auf die leere Menge ab. So erhält man für $griechischerbuchstabemitdach(Z_Start, w) genau die leere Menge raus. Geschnitten mit Z_end ist das die leere Menge. Und mdait ist das wort nicht akzeptiert. Im übrigen finde ich "Der TriPhoenix hat gesagt" ausreichend [img]http://www.fb18.de/gfx/15.gif[/img])

Och, zu jedem DFA gibt es mindestens einen äquivalenten NFA, nämlich ihn selber… Nur die Frage, ob es einen KLEINEREN äquivalenten NFA gibt, wage ich auch mal zu bezweifeln (gibts da 'ne anständige Begründung für, ausser alle 2^10 NFAs mit 2 Zuständen durchzuprobieren?)

Wie begründet man, dass ein DFA auch ein NFA ist?

QUOTE:
Wie begründet man, dass ein DFA auch ein NFA ist?

Man konstruiert ihn. Sei A = (Z, \Sigma, \delta, z0, Z_end) ein DFA.

Dann ist der äquivalente NFA B = (Z, \Sigma, \delta2, Z_Start, Z_End) ist nun leicht zu bauen:
Z ist bei beiden dasselbe, ebenso \Sigma und Z_End.

Z_Start := {z0}
Schließlich die Überführungsfunktion:
\delta2 Z X \Epsilon -> 2^Z ist definiert als \delta2(zustand, buchstabe) = {\delta(zustand, buchstabe)}

fertig ist der NFA [img]http://www.fb18.de/gfx/28.gif[/img]

Wie begründet man, dass ein DFA auch ein NFA ist?

Irgendwie glaub ich nicht, dass man das noch begründen muss. Das Skript sagt (S. 54 oben): "Eine andere Vorstellung sieht einen nichtdeterministischen endlichen Automaten lediglich als eine Erweiterung des bekannten DFA."

Quote [TriPhoenix]
Ich bin enttaeuscht… wofuer hab ich mir die ganze Arbeit gemacht?

MoKrates

Quote [TriPhoenix]
Ich bin enttaeuscht… wofuer hab ich mir die ganze Arbeit gemacht?

MoKrates

Hab ich das mal gesagt? [img]http://www.fb18.de/gfx/22.gif[/img] Außerdem bin ich Kind der Günther-Mathematik…ich bin es gewohnt alle Dinge zu genau zu formalisieren [img]http://www.fb18.de/gfx/7.gif[/img]

Ich rede davon, dass Du TeX schreibst, aber mein Prog nicht benutzt ,)

MoKrates

Ich rede davon, dass Du TeX schreibst, aber mein Prog nicht benutzt ,)

MoKrates

Tu ich doch, aber nicht bei ganz simplen Formeln, da ist mri das schreiben des TeX-Codes und der URL zu mühsam für [img]http://www.fb18.de/gfx/28.gif[/img] Für komplexere Formeln benutze ichs wohl.