Theoretische Informatik.... Ahhhh...

    Hallo,

    gibts irgendeinen Informatik-Studenten (oder etwas verwandtes), der sich mit Theoretischer Informatik im Allgemeinen und Pumping-Lemma im Besonderen auskennt? Wir haben dazu Aufgabe und ich komme darauf einfach überhaupt nicht klar und da bin ich hier auch nicht alleine. :ka: Problem: Wir brauchen insgesamt 50 % der Hausaufgabenpunkte um die Klausur in Theo-Inf schreiben zu dürfen.. Mir fehlen wohl noch 3 Punkte, je nachdem wie genau die das nehmen.... Das letzte Aufgabenblatt gibt es unter:
    http://www.iti.cs.tu-bs.de/~milius/teachi…OINF/aufg11.pdf Kann mir vielleicht jemand helfen? 1 - 2 Aufgaben müßten ja reichen. :) Abgabe ist übrigens am Mo....
    Danke im voraus.

    Schau dir mal den Wiki-Eintrag zum Pumping-Lemma für kontextfreie Sprachen an, da ist ein Beispiel wie man das zum Widerlegen benutzt:
    http://de.wikipedia.org/wiki/Pumping-L…tfreie_Sprachen

    Bei Aufgabe 43 kannst du alle Sprachen so widerlegen. Z.b. 43 a):

    Wir nehmen i=j=n. ObdA sollen nur die 0en "gepumpt" werden, für die 1en gilt der Beweis analog.

    Da mit uvwxy auch u v^i w x^i y in L liegen muss, müssten offensichtlich v und x beide nur aus 0en bestehen und v aus denen links von den 1en, x aus denen rechts der 1en (da dann mit steigendem i auf beiden Seiten gleich viele 0en dazukommen, laut Definition der Sprachen müssen es auf beiden Seiten gleich viele sein). Heisst w müsste alle 1en zwischen den 0en sein, das ist aber durch die Voraussetzung |vwx| <= n nicht möglich, da es n 1en sind.

    Also erfüllt die Sprache das Pumping-Lemma nicht und ist demnach nicht kontextfrei.

    5 Mal editiert, zuletzt von Taku (30. Januar 2009 um 23:56)

    Danke für die Hilfe. Ich werde mich damit dann wohl heute Abend oder morgen näher nochmal mit auseinander setzen und hoffe es dann hinzukriegen. Muss mich erstmal noch um ne Präsentation kümmern. Ich hasse die letzten Wochen vor den "Ferien". :full:

    Ich hoffe das war halbwegs verständlich, ich kann das auch nochmal etwas ausführlicher schreiben bzw. die Ansätze für b) und c), wobei die Idee bei allen drei Teilaufgaben gleich ist. Ist das Pumping-Lemma denn soweit klar? Das ist so eine der Sachen von TI die ich nicht nur damals verstanden habe sondern auch jetzt noch weiss :D :alk:

    Unser Dozent scheint ja eine Vorliebe für das Pumping-Lemma zu haben, da es nicht das erste Aufgabenblatt damit ist. Und ich habe schonmal länger damit verbracht und es nicht wirklich hinbekommen. Beweise führen ist etwas, was ich wohl nie kann.... :gähn:
    Auf der Lösung einer anderen Übungsaufgabe hat er auch diese drei Bedingungen aufgeführt (siehe auch: http://www.iti.cs.tu-bs.de/~milius/teachi…NF/uebung10.pdf). Aber ich komme einfach nicht so recht dahinter. Bin einfach zu dumm.... :D
    Für die anderen beiden Aufgabe wäre ich dir sehr dankbar. Die bewerten nämlich teilweise auch sehr komisch. Letztens gabs ne Aufgabe, die quasi genau so in dem Buch stand, dass empfohlen wurde. Ich hab das zum Glück entdeckt und konnte die also abschreiben. Hat aber komischerweise dann nur 6 von 8 Punkten gegeben. Jemand anders hatte auch genau das gleiche wie ich (hatte ihm ja das aus dem Buch eingescannt ;) ) und hatte 7 Punkte. Und bei der Gesamtpunktzahl auf dem Aufgabenblatt hatte er auch Glück, weil bei denen da 5 Punkte + 7 Punkte insgesamt 13 waren.... :damn:
    Aber TI ist für mich neben den Mathescheinen echt das Schlimmste im Hauptstudium... Dummerweise ist TI auch das einzige Pflichtfach, argh.

    Na ja, ich werde noch ein wenig mein Glück versuchen. Vielleicht bekomme ich es ja doch noch selbst hin, auch wenn ich da nicht so recht dran glauben kann. :D

    b)
    n sei die Konstante für das Pumping-Lemma. Wir betrachten das Wort Element von L2, das aus n² 0en besteht. Wir können ausschliesslich weitere 0en zu dem Wort hinzufügen. Das nächste Wort aus L2, das am nähsten an dem mit n² 0en ist, ist das Wort mit (n+1)² 0en, das sind n²+2n+1. Da wir durch die Bedingung |vwx| <= n nur n viele 0en "aufpumpen" können kann uv²wx²z nur n²+n 0en haben und ist damit kleiner als das nächste Wort Element L2.

    c) ist tatsächlich kontextfrei, hab das erste mal falsch gelesen.
    L3 wird durch die kontextfreie Grammatik G beschrieben: G = (N,T,P,S) mit N = A, T = {a, b}, P enthält folgende Regeln:

    S -> A
    A -> aaaAbb
    A -> aab

    2 Mal editiert, zuletzt von Taku (1. Februar 2009 um 15:53)

    Ich seh' gerade euer Dozent benutzt die Aufteilung w = xyzuv statt z = uvwxy wie im Wikipedia-Artikel (ich meine in unserem Buch war das genauso aber ich hab' nicht reingesehen). D.h. du müsstest dann die Variablen entsprechend umbennen, sonst wundert der sich nachher (unsere Korrektoren haben bei Verdacht auf Abschreiben schon mal gerne verstärkt an die Tafel gerufen...)

    EDIT: was studierst du eigentlich? Bei uns war TI teil des Grund-, nicht Hauptstudiums (3. & 4. Semester)...

    Einmal editiert, zuletzt von Taku (1. Februar 2009 um 16:17)

    Ja, das mit den Variablen ist mir auch aufgefallen, aber das war mir dann auch egal... ;) Eine Gefahr an die Tafel gerufen zu werden gibt es ja nicht, da es ja keine Pflichtveranstaltung gibt, wo ich hinmuss....

    Ich studiere Wirtschaftsinformatik (also die, die von nichts Ahnung haben :unschuld:). Bei den Informatikern ist das auch Stoff im ersten Semester (was ich ziemlich hart finde). Die müssen aber nicht die Hausaufgaben abgeben, um die Klausur schreiben zu dürfen. Im Informatikbereich hatte ich im Grundstudium Algorithmen und Datenstrukturen, Programmieren 1 + 2, Software Engineering und nen Softwareentwicklungspraktikum (in den Instituten der Uni). Aber zum Glück ist TI ja nur nen Schein, also 4 gewinnt. Die Klausur ist auch Ende März (am Fr bevor wieder Vorlesungen losgehen - Danke für die 2 Tage Ferien.... :mist:) und wir dürfen nen "Cheat-Sheet" mit reinnehmen... Also mal sehen... :D