Hallo,
hat einer mit geschrieben, was Herr Jantzen in der Vorlesung als wichtige Tips für die Klausur so alles erwähnt hat?
Also, wenn ich das richtig verstanden habe, hat er mal erzählt, dass die Präsenzaufgaben wichtiger sind als die Übungsaufgaben.
Das schwerste was dran kommen sollte soll wohl die Anwendung des Pumping-Lemma sein. Weiß nicht in wie weit das hilft :)
Die Präsenzaufgaben sind nicht zwingend wichtiger, aber das Niveau und der Umfang der Aufgaben in der Klausur wird sich an ihnen orientieren.
Es empfiehlt sich sicher trotzdem, auch nochmal generell über die Hausaufgaben zu blicken.
Auf der WSV Seite ist auch so eine Art Mini-Probeklausur, also ein paar Aufgaben, wie sie vom Niveau her gestellt werden.
Die ist shit. Von Niveau her sind die Klausuren schwieriger. Aber vielleicht machen sie das wie immer: Schwere Klausur, viele fallen durch und die Benotung wird extrem runter gesetzt…
Hat einer Erfahrung aus den Vorsemestern? Kamen damals viele Aufgaben dran, die nicht in den Übungen gestellt wurden?
Hat Jantzen/Habel mal erzählt wieviele Aufgaben das werden?
12 ?
Das schwerste was dran kommen sollte soll wohl die Anwendung des Pumping-Lemma sein.
Also bei uns (2007) musste man auch die Idee des Pumping-Lemma verstanden haben und erklären können. In der Klausur waren, meiner Meinung nach, ziemlich schwere Fragen zu dem Thema.
Kann mir einer mal beweistechnisch erklären, warum beim
Pumping-Lemma für kontextfreie Sprachen die Bedingung
(2) |vwx| <= n
gilt?
Kann mir einer mal beweistechnisch erklären, warum beim
Pumping-Lemma für kontextfreie Sprachen die Bedingung
(2) |vwx| <= n
gilt?
Es wird ja n so gewählt, dass in einer Ableitung zu einem
Wort z mit Länge >= n ein Pfad existiert, der Länge mindestens
q+1 hat, wobei q die Anzahl der Nonterminale in der Grammatik
ist (also [latex]n\ge 2^{q+1}[/latex]). D.h. ein Nonterminal muss auf dem Pfad
mehrmals auftreten. Von den mehrmals auftretenden wählt man
nun jenes als A, das, vom Ende des Pfades aus betrachtet, sich zum
ersten Mal wiederholt. Das geschieht, wieder vom Ende des Pfades aus
betrachtet, nach spätestens q+1 Ebenen. Damit gilt also: der Teilbaum,
der wiederholt wird, an dessen unterem Rand also vwx steht, hat Höhe <=q+1.
Damit enthält der untere Rand (also vwx) aber höchstens [latex]2^{q+1}[/latex]
Symbole. Also gilt [latex]|vwx|\le 2^{q+1}\le n[/latex].
Ist das klar geworden?
Verstehe es noch nicht ganz.
Also klar ist mir, dass wir uns vom Ende des Pfades das Nonterminal aussuchen, was als erstes wiederholt wird. Sei es zB A.
Jetzt gelangen wir doch, durch maximal q Ableitungsschritte zum wiederholten A.
D.h. dann müsste doch aber |vx| <= n gelten.
Weil, wenn wir beim wiederholten A sind, können wir doch noch maximal q-1 Ableitungsschritte machen, ohne dass wir uns wiederholen. Also könnte das Wort w doch 2^q Zeichen beinhalten?
Wo ist mein Denkfehler?
Nachträglich:
Habs glaub ich verstanden ;)
Nach dem wiederholten Nonterminal( A), darf ja kein anderes Nonterminal wiederholt werden, weil sonst wärs ja nicht das erste vom Ende des Pfades aus gesehen. Daher muss auf dem Pfad vom ersten Nonterminal( also das erste A) max. q Ableitungsschritte bis zum Ende des Pfades erfolgen, weil sich ja sonst das Nonterminal nochmal wiederholt.
Ich hatte vorher gedacht, ok vom ersten A zum wiederholten max. q Ableitungsschritte, und dann vom wiederholten A bis zum Ende noch mal max. q. Aber das geht ja nicht, weil ansonsten ja vom wiederholten A, wenn dort max. q Schritte erfolgen, zwangsläufig ein anderes nonterminal wiederholen müsste(weil wenn vom ersten A bis zum zweiten q Schritte und danach nochmal q, sowiederholt sich ja aufjedenfall noch eins!), und somit wäre das A nicht das erste Nonterminal vom Pfad ausgesehen. Daher dachte ich vorher , dass |w| <= n sowie |vx| <= n gelten muss.
Naja, danke für deine Hilfe Georg ;)
