Nabend

Hab eine Frage zum neuen Übungszettel.
Ich verstehe die Aufgabenstellung so, dass wir uns in Aufgabe 6.2.2 zwei gescheite Automaten ausdenken sollen. Seh ich das richtig oder habe ich die Definition dieser Automaten übersehen?

MFG

Du sollst zu zwei (beliebigen) vDFAs A und B (hier benannt mit A_{6.2} und B_{6.2}) einen NFA C angeben, so dass dieser gerade die Sprache L(C) = L(A) shuffle L(B) akzeptiert.

"Beliebig" heisst, dass A und B nicht genau spezifiziert werden, sondern lediglich kler ist, dass es vDFAs sind (und die dafuer noetigen Bedingungen erfuellen).

Vgl. hierzu z.B. Theorem 3.59 (Produktautomat) im Skript wo zu zwei (beliebigen) DFAs A und B ein vDFA konstruiert wird, der gerade den Durchschnitt von L(A) und L(B) akzeptiert.

Cheers.

P.S. Was wuerdest du ueberhaupt mit zwei "gescheiten" Automaten machen wollen? Wie wuerdest du sie dir "ausdenken" wollen (soll heissen, was sollen sie den tun)?

Moin

Danke erstmal für die Antwort; habe nun verstanden.

Vom Wort "beliebig" hab ich schonma gehört, kann es allerdings in der Aufgabenstellung (noch) nicht finden.
Werde weiter suchen… [img]http://www.fb18.de/gfx/6.gif[/img]

Was ich mit den zwei Automaten hätte "machen wollen" wäre die Konstuktion des zugehörige Produktautomaten (Den Automat, der alle Wörter akzeptiert, die sowohl A, als auch B akzeptiert.).

"Ausgedacht" hätte ich mir Zustandsmengen, Alphabete und Überführungsfunktionen, was mir (aufgabentechnisch) nicht umbedingt "gescheit" vorkam.


Lieber fragen, als dumm sterben…

MFG

PS

Dieser Automat soll natürlich die Wörter akzeptieren, die über die Funktion aus den Wörtern von A und B gebildet werden können, nicht einfach den Durchschnitt.

Irgendwie muss ich gestehen, dass ich deinen (frueheren?!) Ansatz nicht verstehe! — Das kann natuerlich vorallem an mir liegen [img]http://www.fb18.de/gfx/28.gif[/img]

Das Wort "beliebig" habe ich in meiner Erklaerung eingestreut um zu verdeutlichen, dass hier zwei vDFAs gegeben sind (!), diese aber nicht so spezifiziert sind, das man ihre Zustandsdiagramme o.ae. aufmalen koennte, sondern eben allgemeinerer Natur.

Das ist ganz so, wie wenn man in einem Beweis so etwas stehen hat wie "Sei n eine natuerliche Zahl". Da steht auch nicht welche Zahl n nun genau ist, nur, dass es eben eine natuerliche Zahl ist (und dann gelten bestimmte Dinge, z.B., dass auf diesen Zahlen eine Ordnung definiert ist, dass man ein neutrales Element bzgl. der Multiplikation hat usw. und mit solchem Wissen kann man dann u.U. arbeiten). Hier ist das aehnlich: Du hast zwei vDFAs und weisst dadurch bestimmte Dinge (z.B. das die Zustandsmenge endlich ist). Nun kann man zu (bzw. aus) diesen zwei vDFAs einen NFA konstruieren, der genau die gewuenschte Menge akzeptiert.

Beim Produktautomaten wird ja bspw. auch die Zustandsmenge des Produktautomaten C zweier Automaten A und B angegeben, ohne dass die Zustandsmenge der Automaten A und B genau (d.h. in der Form Z = {z_0, z_1, z_2} o.ae.) angegeben waere.

Alles klar?

Cheers.

Ja Mathe…schönes Fach wenn man s beherrscht. Weiß auch nich aber irgendwie nett hier zwischen Zahlen, Formel und Definitionen. Liebe Grüsse an " 21=12 "..is das n Kehrwert?..wie auch immer. Mfg =>Die mit den Zahlen tanzt<=

Dass dieses keine konkreten Automaten, sondern allgemein vDFAs sind, die repräsentativ für vDFAs und deren Eigenschaften stehen, habe ich nun begriffen.

Aber nach eben diesen (nicht vorhandenen) Konkreten Automaten habe ich gesucht; daher der Gedanke vielleicht selbst welche zu entwickeln. Was nicht die Lösung ist, aber sicher als Denkanstoß zur Lösung der Aufgabe beiträgt.

Man kann sich natuerlich zwei (kleine) vDFAs basteln und sich dann ueberlegen, wie ein zugehoeriger "Schuffel-Automaten" aussehen muesste. Evtl. bringt einen das auf eine Beweisidee.

Ausserdem macht's Spass [img]http://www.fb18.de/gfx/25.gif[/img]

Cheers.

Wir haben mal ne andere Frage!

In (a) sollen wir die Menge abb shuffle aba aufzählen.

Wieviele Elemente werden das?
Wir haben sieben, und sind relativ sicher daß es noch ein achtes geben muss, das wir noch nicht gefunden haben.

Also sagt mal wieviele ihr gefunden habt!

hab auch sieben und denke auch dass das so stimmt

wie berechnet man shuffle.? hab mir die definition angeguckt, aber nicht so ganz verstanden..
wie kommt ihr auf sieben???

Also ich muss zugeben ich habs auch noch nicht so ganz gecheckt nach meinen Verständnis gibt es z.B. bei ab (shuffle) xy nur jeweils ein mögliches u_i bzw. v_i. Also:
u_1 = a, u_2 = b, v_1 = x, v_2 = y. Und nun würde es nach meinem Verständnis nur eine Mögliche Kombination geben nämlich: u1v1u2v2 = axby. Kommt ja auch in der auf dem Aufgabenzettel angegebenen Menge vor. Aber wieso wird z.b. auch abxy akzeptiert!?

Also ich muss zugeben ich habs auch noch nicht so ganz gecheckt nach meinen Verständnis gibt es z.B. bei ab (shuffle) xy nur jeweils ein mögliches u_i bzw. v_i. Also:
u_1 = a, u_2 = b, v_1 = x, v_2 = y. Und nun würde es nach meinem Verständnis nur eine Mögliche Kombination geben nämlich: u1v1u2v2 = axby. Kommt ja auch in der auf dem Aufgabenzettel angegebenen Menge vor. Aber wieso wird z.b. auch abxy akzeptiert!?

Wenn Sie richtig lesen, sehen Sie dass [img]http://mokrates.de/cgi-bin/texstring?$u_i,%20v_i%20%5Cin%20%5CSigma%5E*$[/img] (also irgend welche passende Teilstücke des Wortes) sein dürfen,
was ja immer(!) das leere Wort einschließt!!
Durch das gegebene Beispiel könnte man/frau doch darauf kommen. oder??

Nun sollte es doch aber wirklich gehen,
denn mehr als alles präzise und eindeutig zu definieren,
sowie noch zusätzlich mit einem Beispiel erläutern,
kann ich nun wirklich nicht!

M.J.

Misst. Kann mir bitte jemand gaaaaanz schnell den LaTeX-Befehl für den Shuffle-Operator nennen? Ich kann den auf den Symbol-Listen leider nicht finden. Das hat man davon, wenn man alles in letzter Minute macht…

\sqcup\sqcup. Oder so ähnlich jedenfalls. Vorausgesetzt, Herr Jantzen hat die richtigen fonts mitgespeichert [img]http://www.fb18.de/gfx/7.gif[/img]

Haut nicht so gut hin. Beide einzelnen Symbole sind dann sehr weit auseinander. Ist eigentlich auch nicht so wichtig, ich definiere mir einfach mein eigenes Symbol….

und wie mach ich das genau? am besten gleich den code, daich in latex noch nich so fit bin thx

Was genau meinst du jetzt?

ich definiere mir einfach mein eigenes Symbol….

vermute ich mal…

Achso. Wenn das gemeint war, dann sollte das nur heißen, dass ich irgendeinen anderen Quatsch nehme und den da rein packe und das Ganze dann als "shuffle" definiere (im umliegenden Text). Also kein LaTeX-Gezauber.

ich dachte du meinst irgend ein latex makro oder so.. nee,
ich hab nun \sqcup\!\sqcup benutzt.
mfg

Haut nicht so gut hin. Beide einzelnen Symbole sind dann sehr weit auseinander. Ist eigentlich auch nicht so wichtig, ich definiere mir einfach mein eigenes Symbol….

Hi, das wars bei mir:

\newcommand{\sh}{\mbox{$\hspace*{0.05em}\,
{\scriptstyle \sqcup}\hspace*{-0.14em}{\scriptstyle\sqcup}\,$}}

Damit rücen die zusammen: \hspace*{-0.14em}
Na, ja, das ist schon Bastelei, zur Not geht doch auch
w_1 "shuffle" w_2 und jeder weiß was gemeint war?

M.J.

Hi, das wars bei mir:

\newcommand{\sh}{\mbox{$\hspace*{0.05em}\,
{\scriptstyle \sqcup}\hspace*{-0.14em}{\scriptstyle\sqcup}\,$}}

Ah, ja. Vielen Dank. Ist ja dann wirklich doch noch ein bisschen Gefrickel dabei. Dachte/hoffte da gibt es vielleicht ein Symbol in irgendeinem LaTeX-Paket. Naja, dann muss ich wohl doch demnächst viel tiefer in die Eingeweide von LaTeX einsteigen…

zur Not geht doch auch
w_1 "shuffle" w_2 und jeder weiß was gemeint war?

So ähnlich hatte ich's dann auch gemacht.