Moin,

bei 8.2 steht folgender Hinweis:
Sehen Sie sich im Buch von Vossen & Witt die Konstruktion für den Automaten
an, der die Spiegelwortsprache akzeptiert (Satz 3.8 (7) auf Seite 88-90)! Der hier gesuchte
Automat wird sicherlich ein NFA sein, denn man muss ja irgendwie an jedem beliebigen
Zustand von A8:2 beginnen können und genau dort später wieder fortsetzen.

Da ich das Buch nicht besitze und auch nicht mehr die Gelegenheit hattes es mir zu leihen wollte ich mal Fragen ob mir jmd die angegebenen Seiten online zur Verfügung stellen könnte?
Falls irgendwelche Probleme mit dem Copyright auftreten würde mir sonst auch das Diagramm mit ein paar Kommentaren reichen.

gruß

Auf google gibts die seiten als online book
http://books.google.de/books?id=Zo7I8kutRVIC&dq=grundkurs+theoretische+informatik&pg=PP1&ots=Hir8Gn8Zjb&sig=-isKGH_cquS7QTB1OFV4Oi-M3l0&hl=de&prev=http://www.google.de/search%3Fhl%3Dde%26q%3DGrundkurs%2Btheoretische%2BInformatik%26btnG%3DGoogle-Suche&sa=X&oi=print&ct=title&cad=one-book-with-thumbnail

Ich könnte etwas Hilfe bei Aufgabe 8.2 gebrauchen. :)

Um die Funktionalität des gesuchten Automaten klarer zu bekommen, habe ich mir mal ein einfaches Beispiel gesucht. Sei A1 der Automat, der genau die Sprache L1 = {abcd} akzeptiert. Der ist schnell konstruiert (Achtung, quick'n'dirty-formal-unkorrekte Grafiken):

[img]http://imgur.com/4iFrn.png[/img]

Dann wäre für R gebildet gemäß Aufgabenstellung die akzeptierte Wortmenge R = {abcd, bacd, cbad, dcba}

Auch das Prinzip, wie man aus einem Automaten, der eine beliebige Sprache akzeptiert, den konstruiert, der die Sprache akzeptiert in der alle Wörter gespiegelt sind, ist mir klar: Ich nehme mir meinen Automaten, drehe alle Kanten um, mache alle Start- zu Endzuständen und umgekehrt. Schlimmstenfalls wird dadurch ein DFA zum NFA, aber das ist ja egal. Das lässt sich sicherlich ohne große Probleme auch formal für ein gegebenes (Automaten-)Tupel aufschreiben.

Wie bringe ich das jetzt so zusammen, dass der Automat, den ich suche, erzeugt wird, also der, der genau die obigen vier Zeichenfolgen akzeptiert? Mein Gedanke dazu war folgender:

[img]http://imgur.com/FnZOH.png[/img]

Dabei habe ich immer die entsprechenden Teile des Spiegelautomaten gebildet und sie an die passende Stelle des ursprünglichen Automaten "angehängt". Ich habe allerdings keine Ahnung, wie ich dieses Verfahren für beliebige Ursprungs-DFAs formalisieren würde, die ja Verzweigungen, Kreise und wer weiß was enthalten können. In der Aufgabe steht noch, dass der gegebene Automat ein vDFA ist, das ist bestimmt wichtig, oder?

Bin ich auf dem Holzweg? Hat jemand einen guten Tipp parat?

Finde es auch schwierig, da alle möglichen Verzweigungen ja denkbar sind.
Wenn die reguläre Menge vom Ursprungs vDFA endlich wäre, könnte man für jedes akzeptierte Wort neue Zustände und Kanten bilden(da die resultierende Zustandsmenge dann ja auch endlich wäre).
Da es aber auch eine reguläre Menge sein kann die unendlich groß ist(also mit Schleifen), ist das aber auch nicht so einfach.

Also ich habe die Aufgabe ein wenig anders verstanden. Aber das muss ja nichts heißen.
Da uv Element von L(A), ist es eine reguläre Menge. Daher habe ich zwei Alphabete U:={u1, u2, …, un} und V:={v1, v2, …, vm} definiert und zu ihnen dann entsprechend U* und V*. uv ist dann Element aus U* ° V*, welches das Eingabealphabet bildet. Dies ganze wird von einem vDFA A8.2 akzeptiert, den man in zwei Teilmengen zerlegen kann. Die vorderer Teilmenge akzeptiert Elemente aus U*, die hintere Elemente aus V*.

Der Automat A8.2rev, der Elemente aus rev(u)v akzeptiert, ist dann im vorderen Teilstück die Spiegelung des ersten Stückes des vDFA und im hinteren stimmt er mit diesem dann überein. Das bedeutet, dass er eine Menge an Startzuständen hat (die Endzustände des A8.2), genau einen Übergang zum zweiten Stück (den Startzustand des vDFA). Er ist dann also ein NFA.

Kann man das so machen?

Kann man das so machen?

Hm, mit der Methode akzeptierst du, denke ich, viel zu viel. Wir müssen das mit uv und der Unterteilung mal konkretisieren:

L(A) ist die gegebene reguläre Sprache, zu der ein Automat existiert. Schön und gut.

Die Bildungsvorschrift von R sagt mir, dass ich mir jedes Wort w aus L nehmen kann und mir von diesem Wort einen linken Teil beliebig wählen kann (das wäre dann u), der auch mal die Länge 0 haben kann, der Rest des Wortes ist dann v. Anders gesagt: w = uv (konkateniert), w wird in zwei beliebige Teile geteilt.

Jetzt nehme ich mir das Wort uv und drehe u um. Ich erhalte rev(u)v. Für ein Beispiel siehe meinen Eintrag oben.

Jetzt suche ich einen Automaten, der genau all diese Wörter akzeptiert, die ich auf Basis der Sprache L(A) auf diese Weise bilden kann, nicht mehr und nicht weniger. Für jedes Wort w aus L(A) sind das |w| verschiedene Möglichkeiten. Ist L(A) eine unendliche Menge, so ist dementsprechend auch R eine unendliche Menge.

Wenn ich den Arbeitsauftrag irgendwie falsch verstanden habe, klärt mich auf. :)

P.S.: Ist euch auch aufgefallen, dass es für 8.1 und 8.2 jeweils 6 Punkte gibt? Schön zu wissen, dass sie ungefähr gleich schwer sind. ;)

Es ist m. M. nach nicht all zu kompliziert. Man muss ja nur schauen, was der Automat haben muss, damit er Präfix und Suffix erkennt. Dann kommen die Bedingungen für die Spiegelung hinzu.

So als kleines OT: Ist eigentlich das 2. Skript zu FGI-1 schon da?

Soweit ich weiß noch nicht.
Folien sind aber online verfügbar.