Algebraische und Logische Aspekte der Automatentheorie - Cheatsheet

Minimierung von deterministischen endlichen Automaten (DEA)

Definition:

Minimierungsprozess zur Vereinfachung eines DEA, um die Anzahl der Zustände zu reduzieren.

Details:

• Ziel: Finden eines Automats mit minimaler Zustandsanzahl, der dieselbe Sprache akzeptiert.
• Äquivalenzrelation \(\backsim\) basierend auf Zustandsäquivalenz
• Schritte: Eliminiere unerreichbare Zustände, bestimme äquivalente Zustände, bilde Quotientenautomat.
• Algorithmus von Hopcroft am effektivsten
• Minimierter DEA ist eindeutig bis auf Isomorphie.

Äquivalenz von DEA und Nichtdeterministischen endlichen Automaten (NEA)

Definition:

DEA und NEA sind äquivalent, da beide die gleiche Sprachklasse akzeptieren.

Details:

• Jeder NEA kann in einen äquivalenten DEA umgewandelt werden.
• Konvertierungsprozess: Subset-Konstruktion (auch Powerset-Konstruktion genannt).
• NEA: Zustandsübergänge können nichtdeterministisch sein (mehrere mögliche nächste Zustände).
• DEA: Zustandsübergänge sind deterministisch (ein eindeutiger nächster Zustand).
• Formale Darstellung der Äquivalenz: Sei M ein NEA. Dann existiert ein DEA M', wobei L(M) = L(M').
• Komplexität: DEA kann exponentiell mehr Zustände als NEA haben.
• Akzeptierte Sprachen: Beide akzeptieren reguläre Sprachen.

Pumping Lemma für reguläre Sprachen

Definition:

Wird verwendet, um zu zeigen, dass eine Sprache nicht regulär ist.

Details:

• Für eine reguläre Sprache L existiert eine Konstante p (Pumping-Länge), sodass jedes Wort w in L mit |w| ≥ p geschrieben werden kann als w = xyz.
• wobei |xy| ≤ p und |y| ≥ 1.
• Für alle i ≥ 0 muss xy^i z ∈ L gelten.
• Wird oft durch Widerspruch verwendet.

Chomsky-Normalform

Definition:

Chomsky-Normalform - kontextfreie Grammatik mit speziellen Regeln

Details:

• Jede Regel hat die Form:
  • 1: \(A \rightarrow BC\) (mit Nichtterminalsymbolen \(A, B, C\))
  • 2: \(A \rightarrow a\) (mit Terminalsymbol \(a\))
• Startsymbol nicht auf rechter Seite
• Ermöglicht effizientes Parsing

CYK-Algorithmus

Definition:

Algorithmen zur Entscheidung, ob eine gegebene Zeichenkette zu einer kontextfreien Grammatik gehört.

Details:

• CYK-Algorithmus verwendet Chomsky-Normalform (CNF).
• Laufzeit: \(O(n^3 \cdot |G|)\), wobei \(n\) die Länge der Zeichenkette und \(|G|\) die Anzahl der Produktionsregeln ist.
• Schritt 1: Umwandeln der Grammatik in CNF.
• Schritt 2: Initialisieren der CYK-Tabelle: \(T[1..n, 1..n]\).
• Schritt 3: Füllen der Tabelle von unteren Dreieck.
• Schritt 4: Entscheiden über die Wortzugehörigkeit, indem der Startsymbol in der Tabelle gesucht wird.

Beispiele von berechenbaren und unberechenbaren Funktionen

Definition:

Unterscheidung zwischen Funktionen, die durch Algorithmen berechnet werden können und solchen, die nicht berechenbar sind.

Details:

• Berechenbare Funktionen: Können durch einen Algorithmus berechnet werden. Beispiel: Addition, Multiplikation, Faktorisierung von ganzen Zahlen.
• Unberechenbare Funktionen: Können nicht durch einen Algorithmus berechnet werden. Beispiel: das Halteproblem (entscheiden, ob ein Programm hält), bestimmte Probleme der formalen Sprachen und Automaten.
• Berechenbarkeit formalisiert durch Turing-Maschinen.
• Church-Turing-These: Eine Funktion ist genau dann berechenbar, wenn es eine Turing-Maschine gibt, die sie berechnet.
• Das Halteproblem ist ein bekanntes Beispiel für eine unberechenbare Funktion.

Halteproblem

Definition:

Das Halteproblem ist das Problem der Entscheidung, ob ein gegebenes Programm mit einer bestimmten Eingabe in endlicher Zeit hält oder ewig weiterläuft.

Details:

• Unentscheidbares Problem: Es gibt keinen Algorithmus, der für alle Programme und Eingaben korrekt entscheidet.
• Beweis: Reduktion auf den Widerspruch durch die Annahme eines Entscheidungsalgorithmus.
• Formell: Ein Programmentscheidungsproblem. Ein Programm P und eine Eingabe x, wobei die Frage ist, ob P(x) hält.
• Turingmaschinen: Zentrales Konzept in der Berechenbarkeitstheorie.

Rekursive und rekursiv aufzählbare Mengen

Definition:

Rekursive Mengen (entscheidbare Mengen) sind Mengen, für die ein Algorithmus existiert, der jedes Element in endlicher Zeit bestimmen kann. Rekursiv aufzählbare Mengen (semi-entscheidbare Mengen) sind Mengen, für die ein Algorithmus existiert, der die Elemente der Menge aufzählen kann, aber möglicherweise nie terminiert, wenn das Element nicht in der Menge liegt.

Details:

• Rekursive Mengen sind durch totale Turingmaschinen erkennbar.
• Rekursiv aufzählbare Mengen sind durch Turingmaschinen erkennbar, die immer anhalten, wenn das Element in der Menge liegt.
• Eine Menge ist genau dann rekursiv, wenn sowohl sie, als auch ihr Komplement rekursiv aufzählbar sind.
• Alle rekursiven Mengen sind rekursiv aufzählbar, aber nicht alle rekursiv aufzählbaren Mengen sind rekursiv.
• \textbf{Beispiel:} Sprache der Turingmaschinen, die mit leerem Band anhalten, ist rekursiv aufzählbar, aber nicht rekursiv.