Cheat Sheet


Normalformen

Chomsky-Normalform (CNF)

  • Regeln: Jede Produktionsregel hat die Form oder , wobei , , Nichtterminalsymbole sind (wobei und nicht das Startsymbol sind) und ein Terminalsymbol ist.

  • Eigenschaften: Jede kontextfreie Grammatik kann in CNF umgewandelt werden.

  • Beispiel:

    • Gegebene Grammatik:
    • Umgewandelt in CNF:
  • Anwendung: Erleichtert Parsing-Algorithmen wie den CYK-Algorithmus.

Greibach-Normalform (GNF)

  • Regeln: Jede Produktionsregel hat die Form , wobei ein Terminalsymbol ist und eine (möglicherweise leere) Folge von Nichtterminalen.

  • Eigenschaften: Jede kontextfreie Grammatik kann in GNF umgewandelt werden.

  • Beispiel:

    • Gegebene Grammatik:
    • Umgewandelt in GNF:
  • Anwendung: Nützlich für Beweise und für die Konstruktion von Kellerautomaten.

Kuroda-Normalform

  • Regeln:

    • Produktionsregeln haben die Form:
    • Hierbei sind , , , Nichtterminal- und ein Terminalsymbol.
  • Eigenschaften: Jede kontextsensitive Grammatik kann in die Kuroda-Normalform umgewandelt werden.

  • Beispiel:

    • Gegebene kontextsensitive Grammatik:
    • Umgewandelt in Kuroda-Normalform:
  • Anwendung: Theoretische Untersuchungen von kontextsensitiven Sprachen.


Sätze

Satz von Rice

  • Aussage: Alle nicht-trivialen semantischen Eigenschaften von Turing-erkennbaren Sprachen sind unentscheidbar.

  • Bedeutung: Es gibt keine allgemeine Methode, um bestimmte Eigenschaften von Programmen zu bestimmen, z.B. ob ein Programm eine bestimmte Funktion berechnet.

Satz von Cook (Cook-Levin-Theorem)

  • Aussage: Das Erfüllbarkeitsproblem (SAT) ist NP-vollständig.

  • Bedeutung: Begründet die Theorie der NP-Vollständigkeit und zeigt, dass viele wichtige Probleme gleichermaßen schwierig sind.


Abschlusseigenschaften

Abschlusseigenschaften von Sprachklassen

Sprache / OperationVereinigungDurchschnittKomplement
RegulärJaJaJa
KontextfreiJaNeinNein
KontextsensitivJaJaJa
RekursivJaJaJa
Rekursiv AufzählbarJaJaNein

Legende:

  • Ja: Die Sprachklasse ist unter der Operation abgeschlossen.
  • Nein: Die Sprachklasse ist unter der Operation nicht abgeschlossen.

Hinweise:

  • Kontextfreie Sprachen sind nicht unter Durchschnitt und Komplement abgeschlossen.
  • Rekursiv aufzählbare Sprachen sind nicht unter Komplement abgeschlossen.

Primitive Rekursion und μ-Rekursion

Primitiv Rekursive Funktionen

  • Definition: Primitiv rekursive Funktionen sind Funktionen, die aus den Grundfunktionen mithilfe von Funktionskomposition und primitiver Rekursion aufgebaut werden.

  • Grundfunktionen:

    • Nullfunktion:
    • Nachfolgerfunktion:
    • Projektionen:
  • Konstruktionsregeln:

    • Komposition: Wenn und primitiv rekursiv sind, ist auch primitiv rekursiv.
    • Primitiv Rekursion: Wenn (Basisfunktion) und (Rekursionsfunktion) primitiv rekursiv sind, dann ist definiert durch:
  • Beispiele:

    • Addition ():
      • Basisfall:
      • Rekursionsschritt:
    • Multiplikation ():
      • Basisfall:
      • Rekursionsschritt:

μ-Rekursive Funktionen

  • Definition: μ-rekursive Funktionen erweitern die primitiven rekursiven Funktionen durch Einführung des μ-Operators (Minimierungsoperator).

  • μ-Operator:

    • Für eine gegebene Funktion ist die μ-rekursive Funktion definiert als:
      • findet das kleinste , für das gilt.
  • Bemerkung: Durch den μ-Operator können wir total rekursive Funktionen darstellen, die nicht primitiv rekursiv sind.

  • Beispiel:

    • Prüfung auf Null:
      • Funktion
      • μ-Rekursive Funktion sucht das kleinste , sodass :
        • Ergebnis:

NP-Vollständigkeits-Hierarchie

Übersicht der NP-vollständigen Probleme

                SAT
                 |
             3-CNF-SAT
            /    |     \
       CLIQUE  SETCOVER  SUBSETSUM   GRAPHCOLORING
         |                 |           |
    INDEPENDENT SET      KNAPSACK   DIRECTED HAMILTON CYCLE
         |                 |           |
      VERTEX COVER     PARTITION   UNDIRECTED HAMILTON CYCLE
                           |           |
                       BIN PACKING   TRAVELLING SALESMAN
  • SAT (Erfüllbarkeitsproblem): Entscheidet, ob eine boolesche Formel erfüllbar ist.
  • 3-CNF-SAT: Spezialfall von SAT, bei dem die Formel in konjunktiver Normalform mit höchstens drei Literalen pro Klausel vorliegt.

Verwandte Probleme:

  • CLIQUE:

    • Problem: Finden eines vollständigen Teilgraphen (Clique) der Größe in einem ungerichteten Graphen.
    • Verwandte Probleme:
      • INDEPENDENT SET: Finden einer Menge unverbundener Knoten.
      • VERTEX COVER: Finden einer minimalen Knotenmenge, die alle Kanten abdeckt.
  • SET COVER:

    • Problem: Bestimmen der kleinsten Anzahl von Mengen aus einer Mengensammlung, die die Gesamtmenge abdecken.
    • Verwandte Probleme:
      • KNAPSACK: Objekte mit maximalem Wert unter Gewichtslimit auswählen.
      • PARTITION: Aufteilung einer Menge in zwei Teilmengen mit gleicher Summe.
      • BIN PACKING: Objekte in minimaler Anzahl von Behältern unterbringen.
  • SUBSET SUM:

    • Problem: Prüfen, ob eine Teilmenge von Zahlen existiert, deren Summe einen gegebenen Wert ergibt.
  • GRAPH COLORING:

    • Problem: Färben der Knoten eines Graphen mit minimaler Anzahl von Farben, sodass keine benachbarten Knoten die gleiche Farbe haben.
    • Verwandte Probleme:
      • DIRECTED HAMILTON CYCLE: Finden eines Hamiltonkreises in einem gerichteten Graphen.
      • UNDIRECTED HAMILTON CYCLE: Finden eines Hamiltonkreises in einem ungerichteten Graphen.
      • TRAVELLING SALESMAN: Finden der kürzesten Rundreise durch gegebene Städte.

Hinweis: Die meisten dieser Probleme sind NP-vollständig, was bedeutet, dass sie in polynomieller Zeit auf einem nichtdeterministischen Rechner lösbar sind und dass eine polynomielle Lösung für eines dieser Probleme polynomielle Lösungen für alle NP-Probleme implizieren würde.