Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 10 Aufgabe 34
Hallo,
hat von euch zufällig schon jemand die Aufgabe 34 auf dem 10. Übungsblatt gemacht? Wenn, ja wie habt die die Teilaufgaben b) und c) gelöst? Beis mir da grad die Zähne aus. Vielleicht kann mir jemand einen Tip geben (ach ja und noch ne Frage, seh ich das falsch oder sind b) und c) im endeffekt mit den gleichen Widerspruchsbeweis zu lösen?).
Danke schonmal.
Also ich habs jetzt nicht direkt gemacht, aber wenn ich das richtig sehe könnte man die Beweise zu b und c in einem zusammenfassen, ja. Sind die echt anspruchsvoll? Hätte ich jetzt so vom Erscheinungsbild nicht wirklich erwartet. :>
Bei der b könnte man so ein Lemma für Komplementsprachen anwenden, bin mir aber nicht sicher wo ich das gesehen habe. Müsste eigentlich reichen zu zeigen, das 0^n1^n nicht regulär ist.
ja ganz recht es gibt einen Satz der besagt wenn eine Sprache regulär ist so ist das Komplement ebenfalls regulär(ist ja auch ganz einleuchtend wenn man sich das als Automaten vorstellt). Das ist ja alles schön und gut, aber leider hatten wir das nicht in der Vorlesung und soweit ich gesehen habe kommt das auch dieses Semester nicht mehr. Und als einziges Mittel eine nichtregularität nachzuweisen haben wir ja bloß das Pumping-Lemma, es ist auch gut denkbar das es mit diesem Satz von Myhill-Nerode einfacher zu zeigen ist. Ich denk halt das deswegen noch mit dem P.L. gehen müsste.
Das Problem was ich bisher habe ist das ich einen Widerspruch für alle Zerlegungen meines Wortes x bekommen muss und das schaff ich bisher nur für einige aber leider nicht für alle. Naja ich grüble mal noch ein paar stunden über dem viech…
Also eigentlich kannst du das einfach mit der Abgeschlossenheit von L_3 (nach Chomsky natürlich, sprich reg Sprache <=> lineare Grammatik) gegen Komplementbildung begründen. (Hierzu einfach den Automaten mit der Komplementmenge als finalen Zuständen betrachten, Kleene macht den Rest. ;P)
Hat jemand die 34d) direkt als irregulär entlarvt ohne über eine Teilsprache des Komplements zu gehen? Ich hab da zwecks Faulheit einfach die Sprache bei (a) hergenommen.
Ja, ok wenn man so macht ists einfach, hätt mich nur interessiert ob es mit P.L. auch geht.
die 34 d) hab ich mit dem P.L. gemacht. Als x hab ich folgendes gewählt: x = 0^(n-1) 1 0^n somit ist mein
uv = 0^k 1 wobei k>=0 ist. wähle ich nun für i = 0 so bekomm ich 0^(2n-|v|) was ja offensichtlich ein Palindrom ist, also Widerspruch.
Wie hast das du das gemacht, über die Teilsprache des Komplements? (Was soll eine Teilsprache sein??), vielleicht kannst mir mal kurz deinen lösungsweg erklären, würd mich interessieren wie man das anders auch einsehen kann das die Sprache irregulär ist.
Ach stimmt, so geht das auch recht einfach. Hab mich wohl zu sehr aufs Komplement konzentriert. :>
Also ich hab das Komplement ¬L={w∈{0,1}* | w ist Palindrom } mit der Teilsprache M=0^n1^m0^n=L aus Aufg (a)⊂¬L betrachtet. Aus M irreg folgt dann dass ¬L irreg und schliesslich L irreg.
ja es scheint das man auch so argumentieren kann, zumindest rein intuitiv erstmal, wenn mans genau nimmt müsste man halt das ganz zeug erstmal noch beweisen, das das aus der Abgeschlossenheit der regulären Sprachen bzgl. dem Komplemnt folgt. Ich frag mich nur ob eine solche Argumentation auch in der Klausur die volle Punktzahl bringt (bei unserem jetzigen Wissenstand wohlgemerkt)?
Bis zur Klausur im 3. Semester sollten wir das schon noch lernen. :>
BTW: bei dem (Konstruktions-)Beweis der 33 ist es mir echt krass ergangen. Der formale Beweis war eigentlich garnicht so schlimm, aber wenn man sich das an konkreten (indeterministischen) Automaten durchspielt versagt einem gerne mal die Intuition. Hab echt ne ganze Weile an der Richtigkeit des Beweises gezweifelt. ^^
Zum Beispiel gilt tatsächlich (L(A))^R =({0,1}0)^R=0{0,1}= L(A^R) mit den angefügten Automaten A und A^R, obwohl man intuitiv erstmal diverse Worte ausschliessen würde. Hab dabei auch noch gelernt das die Mengenschreibweise bei Zustandsübergängen bei i.d.e.a. in solchen Fällen echt hilfreich sein kann.
Attachment:
33-expl.png: https://fsi.cs.fau.de/unb-attachments/post_30969/33-expl.png
Ja, formal gesehen ist die 33 ganz nett gewesen zu beweisen, aber dann auch noch zu zeigen das dieser konstruierte Automat A^R auch wirklich L^R erkennt ist irgendwie nicht so einfach.
Aber nochmal zu deinem Beispielautomaten:
Wenn ich das jetzt richtig sehe erkennt dein Automat A doch folgende Sprache: L(A) = 0∪(100)∪(1001)* bin mir jetzt nicht ganz sicher ob das wirklich das gleiche wie (0,1)*0 ist kann womoeglich schon sein… ja doch das ist schon das gleiche, hat mich jetzt nur verwirrt wie der Automat konstruiert ist.
Ja aber da hast schon recht wenn man das mal an beispielen durchspielt kann man ganz schoen ins schleudern kommen.
Das L(A^R)=L^R gilt, ist ja der eigentlich Beweis. Hab ich unter Verwendung eines kleinen Hilfsbeweises in 5 Zeilen. :>
Der Knackpunkt hierbei ist δ^_R ordentlich zu definieren und dann mit δ^ in Bezug zu setzen.