Gedächtnisprotokoll FGI109-1

Teil 1: Logik

Aufgabe1: man sollte 3 "Zeichen" erklären 1. implikation 2. folgerbarkeit 3. ableitung durch MP (keine ahnung wie es heißt :/ )

Aufgabe2: Es waren verschiedene Formel gegeben und man sollte ein kreuz bei zutreffenden Antworten machen. (Kontingent, (allgemein)gültig, unerfüllbar) In der Art: Seien F und G Formeln. F ist Tautologie, G unerfüllbar, Ist dann F=>G gültig, kontingent, unerfüllbar? und das für mehrere verschiedene formeln/Bedingungen! Glaube warn 3 oder 4!

Aufgabe3: Noch eine aus dem ersten Teil zum Markierungsalgorithmus: Welche Eingabe nimmt der Algorithmus, welches Resultat liefert er? Dann den Ablauf des Algorithmus aufschreiben. Ich denke hier wäre Pseudocode und ein Diagramm wie es auch im Skript war gefragt gewesen. Dann noch zwei Fragen dazu: Begründen Sie, warum der Algorithmus immer terminiert. Begründen Sie, dass der Algorithmus "unerfüllbar" nur für unerfüllbare Formeln liefert.

Aufgabe4: Resolution folgerbarkeit einer Formel F von einer Formelmenge M zeigen/wiederlegen Formel ma in Implikationsschreibweise gegeben

Aufgabe5: Unifikation 3 Prädikatenlogische Formelmengen waren gegeben und man sollte begründen/wiederlegen warum man sie (nicht) unifizieren kann

waren insgesamt 7 aufgaben im ersten teil, an die andern beiden kann ich mich grad nicht erinnern.

Teil 2: Formale Sprachen, Automaten und Komplexität

1. Alphabet gegeben (a, b). Gib jeweils geforderte Sprache sowie alle Wörter der Länge 3 über Alphabet-Stern an, die nicht enthalten sind! a) Alle Wörter, in denen kein a vor einem b steht

b) Alle Wörter, in denen ab oder ba, aber nicht beide enthalten sind

(Die Aufgabe war glaub ich umfangreicher..)

2. Kellerautomat gegeben - gib an, welche Sprache aktzeptiert wird.

3. Aussagen über formale Sprache, NPSpace, NSpace, Entscheidbarkeit

4. a) Definiere Entscheidbarkeit b) Wieder Aussagen und Fragen

5. Deterministischer Automat gegeben - erstelle nichtdeterministischen (Zustände q0 und q1, q1 Endzustand, q0

Anfangszustand, a-Pfeil von q0 nach q1 und von q0 nach q0, b-Pfeil von q1 nach q0, das wars glaub ich..)

6. Wie würdest du vorgehen, wenn du testen willst, ob ein Problem NP-vollständig ist?