Was war das denn für eine Klausur?Kein Präditkatlogik ,kein BNP und kein Skolem.Nichts!!!!!!!

Was war das denn für eine Klausur?Kein Präditkatlogik ,kein BNP und kein Skolem.Nichts!!!!!!!

Ist das jetzt gut oder schlecht? :-)

Ich fand es machbar. Ob jetzt meine Anworten richtig waren??

Genau, wie ist's gelaufen? Erzaehlt mal alle.

naja, Unifikation war ja immerhin dabei. Hätte aber auch gerne mehr Prädikatenlogik gehabt. Der F1-Teil war sehr aussagenlogik-lastig.

F2 war fair.

Prädikatenlogik rockt, ergo -> schlecht…Skolemform fand ich damals auch net so schwer und mit BNP kann ich grad ohne Nachgucken nix anfangen…

Kam ein Pumpinglemma dran?

Ja, Pumping Lemma war auch dabei.
Allerdings hab ich hauptsächlich die ganzen immer wieder in den Übungen dran genommenen Algorithmen wie Kleene, CFG reduzieren, CFG
lambda frei machen, Potenzautomaten, Pränex, Skolemisierung etc. in und auswendig drauf.
Und davon kam NIX dran !
Soll das jetzt heissen, dass man am besten das lernt, was am
wenigsten (am besten gar nicht) in den Übungen dran kommt ?
Ich fands daneben.

Meine Eindrücke zur Klausur:
- Wenn man den Stoff gut verstanden hat, waren alle Aufgaben lösbar
- Zeitlich hätte man gut ne halbe Stunde mehr benötigt um die Aufgaben richtig zu lösen
- In F1 kamen sehr viele Sachen dran, die ich so nicht erwartet hätte
- In F2 kamen viele komische Sachen, die ich als "irrelevant" im Script weniger beachtet habe (etwa lexikographisch, dyadisch etc.), die man sich aber zum Teil durch Aufgabenstellung/ Anhang erschließen konnte, die charakteristische Funktion aber beispielsweise kam in der Vorlesung und den Übungen fast gar nicht vor und hätte auch ruhig im Anhang erklärt werden können, bzw. man hätte Surjektivität an anderer Stelle fragen können, so hatte man keine Chance ohne das Wissen was diese Funktion ist..

Wie kann man beweisen, dass eine Menge regulär ist, ohne einen Automaten anzugeben? (Reicht es, zu zeigen, dass alle Abschlusseigenschaften gelten?)

ich fand es wurde nur sehr wenig Stoff abgeprüft und das war auch definitiv machbar. Hab fast alle Aufgaben gelöst bis auf Charakteristische Funktion(nicht gelernt) und die vollständige Induktion(nicht fertig geworden). Sofern das andere dann einigermaßen stimmt sollte es ganz gut aussehen für mich :-D:-D

hab aber auch von Kommilitonen gehört, die mit F2 überhaupt nicht klar kamen…

Ich hatte mich auch auf wesentlich schwierigere Aufgaben eingestellt.
mein Gedächnisprotokoll:
F1:
- |= in diversen Anwendungsgebieten erklären
- strukturelle Induktion über Formelaufbau auf Grad der Formel anwenden
- Unifikation/Prädikatenlogik
- in Mengendarstellung umformen und Resolution Aussagenlogik (auch Interpretation)
-

F2:
- charakteristische Funktion
- Lexikografische Ordnung (war definiert im Anhang)
- NFA in Grammatik umwandeln
- Grammatik in DPDA umwandeln
- Pumping Lemma auf xa^t, t = 2-adische Darstellung von x
- Abschlusseigenschaften anwenden

noch ein paar andere Sachen, die mir nicht mehr einfallen,,,

jetzt den Kopf erstmal mit vernünftigen Lebenswichtigen Sachen voll hauen :-D

Ich versuche mal, die Aufgaben wiederzugeben:

F1:

1) Beschreibe folgendes

[img]http://mokrates.de/cgi-bin/texstring?A%20%5Cmodels%20G%20%5C%5C%0AG%20%5Cmodels%20F%20%5C%5C%0AM%20%5Cmodels%20F%20%5C%5C%0A%5Cmodels%20F%20%5C%5C%0AG%20%5Cmodels[/img]
wobei A eine Belegung, F und G Formeln und M eine Formelmenge ist.

2) Einen Beweis mit struktureller Induktion

3) Was ist eine DNF?

4) Allgemeines Verfahren zum Erstellen einer DNF aus einer Formel

5) Warum klappt das allgemeine Verfahren?

6) Unifikation

F2:

1) Mehrere Zahlentupel lexikalisch ordnen

2) 2 Mengen definiert, man sollte zeigen, dass die eine Menge regulär ist, ohne einen Automaten zu konstruieren

3) Irgendwas mit charakteristischer Funktion und Surjektivität

4) 2 Homomorphismen gegeben:
a) Ein Wort w finden, so dass g(w) = h(w)
b) Ein Wort w finden, so dass g(w) != h(w)
c) Menge der Wörter beschreiben für die g(w) = h(w) gilt

5) Reguläre Substitution

6) Es sollte zu einer gegebenen Produktion ein deterministischer Kellerautomat erstellt werden (meiner Meinung nach ziemlich gemein die Aufgabe, denn man muss ja schon eine Zeit daran knobeln)

7) Einen NFA lambdafrei machen und danach in eine lineare Grammatik überführen

8) Pumping-Lemma

Ergänzend zu dem von guiltyguy:

Im F1 Teil gabs auch noch eine Resolutionsaufgabe, die immerhin 11 von 100 Punkten brachte.

Zu den Klausuraufgaben muß ich generell sagen, daß auch ich eher überrascht war. Ich hätte mit mehr Aufgaben gerechnet, die eher an die Übungsaufgaben angelehnt sind (Hornformeln, Prädikatenlogik etc.; wurde ja schon oben teilweise genannt). Aber wir befinden uns hier ja nicht im Wunschkonzert, also muß man nehmen, was kommt… [img]http://www.fb18.de/gfx/22.gif[/img] Unterm Strich würde ich aber auch eher sagen, daß die Klausur recht schwer und anspruchsvoll war.

Wie kann man beweisen, dass eine Menge regulär ist, ohne einen Automaten anzugeben? (Reicht es, zu zeigen, dass alle Abschlusseigenschaften gelten?)

Z.B. mit regulären Ausdrücken oder indem man sie aus bekannten
regulären Mengen mit Abschluss-Operatoren konstruiert (z.B.
Homomorphismen). Wie sah denn die Menge aus?

Also ich fand die Zeit viel zu knapp. Ich hatte eigentlich alles drauf, musste trotzdem sehr viel auslassen, eben weil die Zeit nicht gereicht hat. Lag wohl daran, dass ich mich an der Aufgabe mit der strukturellen Induktion ziemlich lange dran aufgehängt habe.

Ob die Aufgabe stabil genug war ein Strik zum aufhängen zu halten, wage ich zu bezweifeln. [img]http://www.fb18.de/gfx/23.gif[/img]

Anmerkungen:
-Die Resolutionsaufgabe sag in etwa so aus: Man hat ne Formelmenge M und eine Formel G. Nun soll man erst erklären wie man mit Resolution beweisen kann, das G aus M folgt, dann das ganze durchführen und tun.

-Homomorphismen: Die sahen etwa so aus:
g(x)=zz, g(y)=lambda
h(x)=lambda, h(y)=z

Frage:
Die Zahlentupel beim Lexikographischen ordnen, da sortierte man doch nach der ersten Ziffer, und danach nach der zweiten, wenn die erste Gleich ist, oder? Habe davon keine rechte ahnung haben wollen, und diese aufgabe in nur einer Minute so hingeklatscht nach der ersten Idee die ich hatte. Zeit war ja schließlich Punkte wert. [img]http://www.fb18.de/gfx/28.gif[/img]

Frage:
Die Zahlentupel beim Lexikographischen ordnen, da sortierte man doch nach der ersten Ziffer, und danach nach der zweiten, wenn die erste Gleich ist, oder? Habe davon keine rechte ahnung haben wollen, und diese aufgabe in nur einer Minute so hingeklatscht nach der ersten Idee die ich hatte. Zeit war ja schließlich Punkte wert. [img]http://www.fb18.de/gfx/28.gif[/img]

Ja, lexikographisch ist "wie im Lexikon". Im Gegensatz zu lexikalisch, wo vorher noch nach der Länge sortiert wird.

Frage:
Die Zahlentupel beim Lexikographischen ordnen, da sortierte man doch nach der ersten Ziffer, und danach nach der zweiten, wenn die erste Gleich ist, oder? Habe davon keine rechte ahnung haben wollen, und diese aufgabe in nur einer Minute so hingeklatscht nach der ersten Idee die ich hatte. Zeit war ja schließlich Punkte wert. [img]http://www.fb18.de/gfx/28.gif[/img]

Ja, lexikographisch ist "wie im Lexikon". Im Gegensatz zu lexikalisch, wo vorher noch nach der Länge sortiert wird.

Sollte man nicht lexikalisch ordnen?

Sollte man nicht lexikalisch ordnen?

Keine Ahnung - womit wir wieder beim "Aufgabenstellung gründlich lesen" wären :)

Ich habe meinen F-Kram schon sicher im Schrank verstaut und mein Tisch unter T-Kram vergraben, deswegen kann ich jetzt nciht nachgucken, aber das Wort bestand aus zwei Wörtern. lex-l…?? ich denke mal damit ist lexikographisch gemeint gewesen. [img]http://www.fb18.de/gfx/10.gif[/img] Wie schön.

Sollte man nicht lexikalisch ordnen?

AFAIR Ja.

Wie kann man beweisen, dass eine Menge regulär ist, ohne einen Automaten anzugeben? (Reicht es, zu zeigen, dass alle Abschlusseigenschaften gelten?)

Abschlusseigenschaften nennen reicht natürlich nicht,
denn auch andere Sprachfamilien können die gleichen Abschlusseigenschaften erfüllen:
z.B. sind auch die kontextsensitiven Sprachen unter Vereinigung, Durchschnitt, Komplement, Produkt, Stern abgeschlossen.

Logisch ist das nur eine Implikation: WENN regulär DANN Abschlusseigenschaft. Die Umkehrung ist i.A. nicht erfüllt!

Man beweist Regularität von Mengen z.B. dadurch, das man dafür
a) einen rationalen Ausdruck
b) eine einseitig lineare Grammatik
c) ein spezielles lineares Gleichungssystem (hatten wir in F2 nicht!)
d) oder einen NFA
angibt

Man beweist Regularität von Mengen z.B. dadurch, das man dafür
a) einen rationalen Ausdruck
angibt

klingt als wäre das Die Lösung[tm] gewesen…

Man beweist Regularität von Mengen z.B. dadurch, das man dafür
a) einen rationalen Ausdruck
angibt

klingt als wäre das Die Lösung[tm] gewesen…

jawoll, oder in Mengenschreibweise:

[img]http://mokrates.de/cgi-bin/texstring?$%5CSigma%5E*%5Ccdot%20E$[/img]

Ich fand das nicht zu schwer…, oder?

einen automaten sollte man doch nicht angeben.

Ich fand das nicht zu schwer…, oder?

tja, wenn ich meinen professurtitel habe, würde ich das auch sagen;-)