Und wiedermal habe ich Probleme mit diesen blöden Notationen der Sprachen. Es geht um die Aufgabe 12.3
L12.3 = {w element {a,b}* | es gibt ein u element {a,b}* : w = uu}
Das will mir nicht einleuchten. Es gibt EIN u, sodass gilt w= uu. Das ist schön, aber was ist mit dem Rest der Sprache? Oder gilt dieses eine u für jedes Wort?
Kann ich damit nur Wörter alá aa, aaaa, aaaaaa oder bb, bbbb,bbbbbb … bilden?
Das kann ich mir nicht votstellen, weil die Sprache ja dann viel zu trivial wäre, ich bräuchte kein Markieren der Ränder und kein Umtaschen. Das kann es also nicht sein.
Dann muss u auch aus a's und b's bestehen können? Also abab, aabaab, aaabaaab,abbbabbb … ?
Doch dann wäre sie ja schon fast zu umfangreich, oder nicht?
Könnte mir jemand einen Tipp geben oder sagen, ob eine meiner beiden Interpretationen passt?
FGI wäre so viel leichter, wenn man uns die Dinge einfach auf Deutsch hinschreiben würde. Oder am besten beides, sodass man mit der Zeit lernt, wie man das eindeutig liest und deutet.
L12.3 = {w element {a,b}* | es gibt ein u element {a,b}* : w = uu}
Ich lese das so:
w besteht aus einer beliebigen Kombination aus a's und b's. Das w besteht dabei aus zwei Teilen, welche genau gleich sind (w = uu). Jedes dieser Teile besteht wiederum aus beliebigen a's und b's.
Ich finde aber auch, dass der Existenzquantor hier für unnötige Verwirrung sorgt. Meiner Meinung nach ist folgendes die selbe Menge:
[latex]\{w \in \{a,b\}^*| w = uu, u \in \{a,b\}^*\}[/latex]
L12.3 = {w element {a,b}* | es gibt ein u element {a,b}* : w = uu}
Ich lese das so:
w besteht aus einer beliebigen Kombination aus a's und b's. Das w besteht dabei aus zwei Teilen, welche genau gleich sind (w = uu). Jedes dieser Teile besteht wiederum aus beliebigen a's und b's.
Ich finde aber auch, dass der Existenzquantor hier für unnötige Verwirrung sorgt. Meiner Meinung nach ist folgendes die selbe Menge:
[latex]\{w \in \{a,b\}^*| w = uu, u \in \{a,b\}^*\}[/latex]
das sehe ich auch so, aber Puristen nörgeln dann bisweilen!
Noch eine Frage. Steht bei einer DTM (Aufgabe 12.1) vor und nach dem Wort auf dem Eingabeband das Blankozeichen und darf ich es für den Kontrollfluss verwenden?
ja, sonst wäre es ja schwierig das ende der eingabe auszumachen.
Ich finde 12.3 verflucht schwer :/ . "Wenn man Wortränder markiert und Regel für geordnetes Vertauschen anwendet ist das nicht schwierig" - soll ja wohl ein Witz sein.
Kann mir einer einen Tipp geben wie man da am besten vorgeht? Ich habe schon zich Sprachen nach Gefühl einfach ins Blaue konstruiet, dass das nicht wiirklich zielführend ist muss ich wohl nicht erst erwähnen. :(
Ich finde 12.3 verflucht schwer :/ . "Wenn man Wortränder markiert und Regel für geordnetes Vertauschen anwendet ist das nicht schwierig" - soll ja wohl ein Witz sein.
Kann mir einer einen Tipp geben wie man da am besten vorgeht? Ich habe schon zich Sprachen nach Gefühl einfach ins Blaue konstruiet, dass das nicht wiirklich zielführend ist muss ich wohl nicht erst erwähnen. :(
Ins Blaue konstruieren und ohne Plan wird meistens scheitern!
Also erst einen Plan finden,
z.B. diese Anfangsidee:
Zuerst die kontextfreie Sprache {wcw^{rev} | w in {a,b,c}^* } erzeugen.
Nun wie weiter?
Das gespiegelte Wort rechts vom $ ist dort falsch herum! Also viell. dieses durch symbolweises und fortgesetztes Vertauschen über das $-Zeichen hinweg nach links transportieren? Aber wo darf man das Symbol dann "Absetzen" oder stehen lassen? Was passiert denn, wenn jedes Symbol dann stets gleich nach dem $ abgesetzt wird?
Bitte einmal mit ab$ba ausprobieren!
Wie das nun weiter gehen könnte, darf ich nicht auch noch verraten…,
nur viell. soviel:
transportierte Symbole könnten "markiert" (wie denn?) bleiben, bis alles fertig ist, d.h., nichts mehr rechts vom $ steht. Ach so, wie kann man das denn merken? Vielleicht besser zuerst
{wcwd^{rev} | w in {a,b,c,d}^* } erzeugen…
So kann man sich langsam durch hangeln.
Ein wenig selbst Probieren muss sein.
Das könnte viel helfen, aber was bedeutet denn das ^{rev}? Sehe ich so das erste mal.
Schonmal vielen Dank für diesen Ansatz.
Heisst das reverse? Und ich darf das einfach so machen? Woher soll man sowas denn wissen o.O?
Bezieht sich das rev bei dieser Notation auf die Reihenfolge des anderen w oder wird alles, was durch dieses w^{rev} gebildet wird falschherum dargestellt?
Darf eigentlich die cantorsche Paarungsfunktion für den Beweis von M abzählbar also MxM abzählbar benutzt werden?
So kann man sich langsam durch hangeln.
Ein wenig selbst Probieren muss sein.
So in der Art habe ich das auch gemacht; fand die aber wirklich nicht soooo wahnsinnig leicht die Aufgabe. Naja, unser Übungshelfer wird uns noch schön viel beim zweiten teil (Text) abziehen…
Heisst das reverse? Und ich darf das einfach so machen? Woher soll man sowas denn wissen o.O?
Bezieht sich das rev bei dieser Notation auf die Reihenfolge des anderen w oder wird alles, was durch dieses w^{rev} gebildet wird falschherum dargestellt?
In der Vorlesung wurde zur Erklärung der Existent von kontextfreien Sprachen, die nicht deterministisch sind (Folienseite 228) bei der Definition der Sprache PAL :={ww^{rev} | w \in {a,b}^* } diese Notation erklärt.
In Vossen/Witt wird das auf (Seite 18) als sp(w) geschrieben und mit Spiegelung bezeichnet.
Sipser (Seite 14) nennt dies "reverse of w" und notiert es durch w^R.
Solche Fragen sollten doch in der Übungsgruppe bei der Vorbesprechung geklärt werden können, oder nicht?
(man muss 1. dort natürlich hingehen und 2. dann auch dieses nachfragen!)
Das stand bei der Vorlesung an der - ach so kleinen - Tafel:
[latex] $$(abc)^{rev} = \mathrm{cba} $$[/latex]
(oder in Großbuchstaben?)
Darf eigentlich die cantorsche Paarungsfunktion für den Beweis von M abzählbar also MxM abzählbar benutzt werden?
Warum denn nicht? dafür kam diese Paarfunktion doch sicher auch an die Reihe…?
Aber wie denn konkret, wenn die Funktion doch
[latex] $$f:{I\!N}\to M\times M$$ [/latex]
sein sollte?
Ja, sorry habe es inzwischen auch gefunden, das "woher soll man sowas wissen" war wohl etwas unüberlegt dahingeschrieben. Dieses Semester sind die Veranstaltungen so blöd verteilt, dass ein arbeitender Mensch unmöglich alle besuchen kann, so verpasse ich die meisten FGI Vorlesungen. Da ich nichts von solchen Sachen höre kann mir auch nicht einfallen danach in den Übungen zu fragen.
Inzwischen bin ich mit der Sprache aber weit gekommen, vielen Dank nochmal für die Hilfe. Ich glaube ich bin kurz davor etwas fertig zu haben, das auch funktioniert.
[…] sind die Veranstaltungen so blöd verteilt, dass ein arbeitender Mensch unmöglich alle besuchen kann, so verpasse ich die meisten FGI Vorlesungen.[…]
Wer Gründe angeben kann, warum er nicht durchgängig am Studium teilnehmen kann, könnte VOR BEGINN des Semesters ein Teilzeitstudium beantragen. Da wären dann die Referenzsemesterzeiten verdoppelt, und es würde Zeit bleiben, wichtige Veranstaltungen auch zu besuchen. Ich würde mir das mal überlegen, ob das ginge…
Als Grund fürs komplette Versagen beim Studium, wäre eine Aussage wie
"Ich konnte ja nicht wirklich studieren, weil ich immer Geld verdienen musste"
auch im Lebenslauf nicht günstig; von der vertanen Zeit mal ganz abgesehen! Oder?
Wer Gründe angeben kann, warum er nicht durchgängig am Studium teilnehmen kann, könnte VOR BEGINN des Semesters ein Teilzeitstudium beantragen. Da wären dann die Referenzsemesterzeiten verdoppelt, und es würde Zeit bleiben, wichtige Veranstaltungen auch zu besuchen. Ich würde mir das mal überlegen, ob das ginge…
Das Teilzeitstudium wird nur unter bestimmten Voraussetzungen gewährt (15-20h Arbeit/Woche, Kindererziehung und Pflege). Mein Antrag wurde abgelehnt, weil ich 13h/Woche arbeite und mein Arbeitgeber mir nicht mehr gestatten wollte. Nun habe ich mir zwar einen neuen Job gesucht, kann das Teilzeitstudium aber erst zum nächsten Semester beantragen.
Soviel dazu, denn es gehört ja eigentlich nicht in diesen Thread.
Wer Gründe angeben kann, warum er nicht durchgängig am Studium teilnehmen kann, könnte VOR BEGINN des Semesters ein Teilzeitstudium beantragen. Da wären dann die Referenzsemesterzeiten verdoppelt, und es würde Zeit bleiben, wichtige Veranstaltungen auch zu besuchen. Ich würde mir das mal überlegen, ob das ginge…
Als Grund fürs komplette Versagen beim Studium, wäre eine Aussage wie
"Ich konnte ja nicht wirklich studieren, weil ich immer Geld verdienen musste"
auch im Lebenslauf nicht günstig; von der vertanen Zeit mal ganz abgesehen! Oder?
Ich konnte VOR BEGINN des Semesters leider nicht wissen, wie blöd die Veranstaltungen durch den Stundenplan gewürfelt werden würden. Im letzten Semester hat alles wunderbar geklappt und weil es in diesem jetzt dumm ist heisst es nicht, dass das im nächsten auch so sein wird.
Ein Teilzeitstudium würde alles unendlich viel länger machen und nur weil ich etwas Probleme bei FGI habe heisst es nicht, dass ich komplett versage. Das haben alle und ich kenne viele Leute die nicht arbeiten und viel schlechter sind als ich.
Wie man beim Vorposter sieht bin ich nicht alleine mit solchen bzw. ähnlichen Problemen, denn es kann überall auf verschiedenste Weisen einfach nicht passen.
Ach ja und wenn die Angaben vom Vorposter stimmen komme ich mit meinen paar Stunden auch nicht bis zur 15h Grenze, womit ich nichtmal einen Antrag stellen könnte (bzw dieser würde sowieso abgelehnt werden).
Steht im skript irgendwo etwas über die Regeln zum geordneten Vertauschen bei Grammatiken?
Komm irgendwie partout nicht drauf :/
Beispiel:
aA –> Aa
(nur die aA Kombination kann vertauscht werden)
So wie ich die Aufgabe 12.3 verstehe, sollte w aus zwei gleichen Teilen bestehen, z.B "aabaab", und das zweite Teil solte nicht gespiegelt sein, wie kommt ihr aufs Spiegeln??
weil es wohl einfacher ist zunächst das wort aabbaa zu konstruieren, und dann den zweiten teil des wortes wieder zu spiegeln.
Bis dahin auch einfach, aber ich hb kp wie man das sortieren könnte.
Wieso hilft dieses
https://www.fb18.de/mybb/showthread.php?tid=10677&pid=106343#pid106343 denn gar nicht weiter?
statt (kontextfrei) aabbaa zu erzeugen also besser aabcBAAd generieren und dann weiter machen. Z.B. jeden Großbuchstaben solange nach links geschickt vertauschen bis er stehenbleiben kann und dann erst klein wird. Nur wer mit dem Buchstabentauschen herumspielt findet das Passende dann wohl auch heraus.
