Blatt Theoretische Informatik.md

Hilfsblatt Probeklausur 2013/2014

Bildung der komplementären Sprache L' anhand des DEA der Ausgangssprache L

L und L' (L' = komplementäre Sprache zu L)

1. DEA, der die Sprache L akzeptiert bilden.
2. DEA zu totalem DEA umwandeln.
3. Komplementären DEA L' bilden, wie folgt:

• Endzustände werden normale Zustände
• Normalzustände werden Endzustände

Totalen DEA bilden

Ausgangssituation: DEA vorhanden

1. Toten Zustand (X), der das komplette Alphabet auf sich selbst abbildet
2. Von jedem gegebenen Zustand die nicht verwendeten Zeichen auf den toten Zustand verweisen lassen.

NEA zu DEA umwandeln (Rabin Scott Verfahren)

1. Man beginnt mit der Menge aller Startzustände.
2. Von dort aus geht man mit jedem Zeichen alle Zustände der Menge ab. Alle Zustände in die man so gelangt werden als ein Zustand zusammengefasst.
3. Wiederhole 2. bis keine neuen Zustände mehr entstehen.
4. Jeder Zustand der einen ehemaligen Endzustand enthält wird selbst zum Endzustand.

Minimierung eines DEAs

1. Den DEA zu einem totalen DEA umwandeln.
2. Tabelle erstellen anhand der Zustände.
3. Jedes Zustandspaar das aus einem Endzustand und einem nicht Endzustand besteht wird angekreuzt.
4. Für jedes noch nicht angekreuzte Zustandspaar:
   • man geht die Übergangsfunktionen mit jedem Zeichen des Alphabets von diesem Zustandspaar aus durch.
   • daraus entsteht ein neues Zustandspaar, ist dieses bereits angekreuzt wird auch das Ausgangspaar ein Kreuz.
5. Die nicht angekreuzten Zustandspaare können miteinander verschmolzen werden werden.

CYK Algorithmus

// Per Hand zeichnen (Tabelle)

NKA aus kontextfreier Grammatik bilden

M(ZUSTÄNDE, ALPHABET, KELLERALPHABET, ÜBERGANGSFUNKTION DELTA, STARTZUSTAND, UNTERSTES KELLERZEICHEN)

1. Kelleralphabet = alle Terminale + alle Variablen
2. Zustände = Zustand z (gibt nur einen)
3. Alphabet = Terminale
4. Übergangsfunktion:
   • Regeln als spontane Übergange übernommen
   • Regeln um Terminale zu eliminieren

Wort aus NKA ableiten

1. Wort aus der Grammatik ableiten (nur wenn Grammatik gegeben, macht's einfacher)

DELATA(z, WORT, KELLERZEICHEN) -> DELATA(z, WORT, KELLERZEICHEN) -> …