BFS Vorlesungsnotizen

• Was geht und was nicht (mit welchen Ressourcen)
• Erkennung und Erzeugung (→ Compiler, Gramatik) von Objekten mit unendlichen Mengen mit endlichen Mitteln

• Einfaches Modell für Berechnungen
• Engl. Random Access Machine (wörtlich "Maschine mit Wahlfreiem Zugriff", nicht sequenziell, analog zu Von Neumann Maschinen)
• Eigenschaften:
  • Endliches Programm + Befehlzähler
  • Unendlicher Speicher (nummeriert von c(1), c(2), …), alle auf 0 vorinitialisiert
  • Akkumulator (c(0)) auf dem gerechnet wird
• Befehlssatzt mit Operationen auf…
  • Registern (ADD c(i) auf c(0))
  • Konstanten (ADD 3 auf c(0))
  • Indirekten Zugriffen ala. Arrays/Pointer

• Rechnen ist die Manipulation von Zeichenfolgen (Zahlen sind Zeichen, Wörter, etc.)
• Bestandteile einer Turingmaschine
  • Programm δ
  • Anzeige mit n Zuständen von \(q_0\) bis \(q_n\)
  • Unendlich Langes Band mit Lese/Schreib-Kopf
    • LSK steht zu Begin des ersten Eingabesymols, außer die Eingabe ist leer
  • Ausgabeleuchte für nein und ja
• (1. Band, Deterministisch) Turing Maschinen \(M\) Definition:

  \(Q\)

  Endliche Zustandsmenge \(Q = \left\{ q_0, q_1, \ldots \right\}\)

  \(\Sigma\)

  Endliches Eingabealphabet

  \(\Gamma\)

  Endliches Bandalphabet \(\Sigma \subset \Gamma\) (\(\Sigma \neq \Gamma\))

  \(B\)

  Blanksymbol, \(B \in \Gamma\), \(B \not\in \Sigma\)

  \(q_{0} \in Q\)

  Startsymbol

  \(F \subseteq Q\)

  Akkzeptierter Zustandsbereich (F für Final)

  \(\delta: Q \times \Gamma \to Q \times \Gamma \times \left \{ R, L, N \right\}\)

  "Programm" der Turing Maschine

• Eingabe Wort der Länge n: \(w = w_1, w_2, w_3, \ldots, w_n \in \Sigma^{\ast}\)
  • Leeres Wort ε
  • Sprache (Language) \(L \subseteq \Sigma^{\ast}\)
• Konfiguration \(K\)
  • Besteht aus \(\Gamma^{\ast} \times Q \times \Gamma^{\ast}\)
  • Bspw. "0000 q₁ 0001111", wobei q₁ die Position des LSK designiert; wird von Blanks umgeben
  • Eine Konfiguration ist erreichbar wenn der Zustand durch eine Funktion δ "berechnet" werden kann.

• Eine Konfiguration \(K^{\prime}\) ist die i'te Nachfolgekonf. von \(K\) wenn:
  • für \(i = 0\) gilt \(\alpha q \beta = \alpha\prime q\prime \beta\prime\)
  • für \(i \geq 0\) gilt \(\alpha q \beta \vdash^{\ast} \alpha\prime q\prime \beta\prime\)
• Wenn gilt bedeutet es das die TM diesen Zustand erreichen kann, aber ohne eine Effizienz oder Zeitaussage zu treffen

• Eine Turing Maschine \(M\) Akzeptiert eine Eingabe \(x \in \Sigma^{\ast}\) wenn es ein \(\alpha, \beta \in \Gamma^{\ast}, q \in F\) gibt sodass \[ q_{0} x \vdash \alpha q \beta \]
  • Allgemein gilt dass wenn \(q \in F\), dass keine Nachfolgekonfigurationen mehr gegeben werden
• Eine \(L\) Sprache einer TM \(M\) wird als \(L(M)\) bezeichnet, und ist die Menge aller Wörter welche von \(M\) akzeptiert werden.
  • \(M\) Akzeptiert die Sprache \(L(M)\)
  • Keine Aussage darüber wie \(M\) sich verhält wenn \(x\) nicht von \(M\) akzeptiert wird
  • Wenn eine TM für alle Eingaben \(x \in \Sigma^{\ast}\) hält und diese Maschine \(L\) akzeptiert, entscheidet sie die Sprache \(L\).

• Akzeptiert eine beliebige TM nur alle Wörter welche in \(L \subseteq \Sigma^{\ast}\) sind, aber keine die nicht in \(L\) liegen (\(L(M) = L\)), nennt man \(L\) rekursiv auszählbar
• Existiert eine TM welche \(L\) entscheidet, ist \(L\) entscheidbar
• Es existieren Sprachen welche rekursiv aufzählbar (RA) sind aber nicht entscheidbar
• Akkzeptiert eine TM \(L\) nicht, kann dieses ein da der Endzustand nicht in \(F\) liegt, oder die TM sich in einer Endlosschleife auffängt

• Eine Partielle Funktion hat die Form \(f: \Sigma^{\ast} \to (\Gamma \setminus \left\{ B \right\})^{\ast}\)
  • Falls es ein \(q \in Q\) gibt, für dass eine TM mit \(x\) gestartet hält, und \(q_0 x \vdash^{\ast} qy\) gilt, berechnet die TM \(f\)
  • Wenn die TM nicht hält, berechnet diese \(f\) nicht
• Eine Totale Funktion hat die Form \(f: \mathbb{N}^r \to \mathbb{N}\)
  • Falls für alle \(a_1, \ldots, a_r \in \mathbb{N}\) und \(\Sigma = \left\{ 0, 1, \# \right\}\) gilt dass \[ q_0 \mathrm{bin}(a_1) \# \ldots \# \mathrm{bin}(a_n) \vdash^{\ast} q \mathrm{bin}\left(f\left(a_1, \ldots, a_n \right)\right) \] und hält
    • \(\mathrm{bin}(x)\) ist die Binärdarstellung von \(x\)

• Endlicher Speicher ("Im Zustand Merken")
  • Auslesung aller Zustände als \(Q = (\left\{ q_0 \right\} \times \Sigma ) \cup \left\{ q_0, q_1 \right\}\)
  • Dadurch ermöglicht es zb. Prüfung ob ein Zeichen auf dem Band enthalten ist
• Spurtechnik (oder k-Spur)
  • Jede Stelle auf dem Speicher wird als Tupel interpretiert, eg. \(\left\{ A, \ldots, Z \right\}^{n}\)
  • Unterscheidet sich von k-Band da es nur ein lese-schreib Kopf gibt
  • Ermöglicht nicht neue aber effizientere Berechnungen

• Definitionen

  Zeitkomplexität \(T_M(x)\)

  Anzahl der "Schritte" (Zustandsübergänge) welche \(M\) gestartet mit \(x\) ausführt

  Platzkomplexität \(S_M(x)\)

  "Platzbedarf" (Anzahl verschiedener Speicherstellen) welches \(M\) gestartet mit \(x\) benötigt

• Weiterführend \[T_M(n) := \mathrm{max}\left\{ T_M(x) | x \in \Sigma^{\ast}, \left| x \right| \leq n \right\}\] und \[S_M(n) := \mathrm{max}\left\{ S_M(x) | x \in \Sigma^{\ast}, \left| x \right| \leq n \right\}\]

  Zeitbeschränkt

  \(\forall n \in \mathbb{N}: T_M(n) \leq t(n)\) für \(t: \mathbb{N} \to \mathbb{N}\)

  Platzbeschränkt

  \(\forall n \in \mathbb{N}: S_M(n) \leq s(n)\) für \(s: \mathbb{N} \to \mathbb{N}\)

• Jede \(t(n)\) zeitbeschränkte und \(s(n)\) platzbeschränkte det. k-Band TM \(M^\prime\) kann durch eine \(\mathcal{O}(t(n) \cdot s(n))\) zeitbeschränkte und \(\mathcal{O}(s(n))\) platzbeschränkte 1-Band-TM simuliert werden.

• Programmiertechnik auf TM
• "Wenn man für ein Problem eine det. 1-Band TM hat, kann sie auch auf einer Anderen TM benutzt werden, und fungiert so wie ein Unterprogramm"

• Definitionen für RAM \(M\) und Eingabe \(x\)

  \(T_M(x)\)

  Anzahl Schritte von \(M\) gestartet mit \(x\)

  \(S_M(x)\)

  Adresse der höchsten benutzten Speicherzelle bei der Rechnung gestartet mit \(x\)

• \(t(n)\) Zeitbeschränkt und \(s(n)\) Platzbeschränkt analog definiert zu TM
• Eine TM kann eine RAM Simulieren
  • Dann gilt für eine \(t(n)\) zeitbeschränkte RAM, dass die TM \(\mathcal{O}(t(n^3)\) zeitbeschränkt sein wird
  • Eine RAM kann mit 3 TM Bändern übersetzt werden, wo das \(n\mathrm{te}\) Band:
    1. Den Speicherband mit abwechselnden Addressen und Speicherinhalten, delimitiert mit # enthält
    2. Den Befehlzähler mit der Binärdarstellung des PC und zwei # enthält
    3. Ein Arbeitsband darstellt, auf dem Komplexere Operationen ausgeführt werden
  • Benötigt riesige aber endliche δ-Tabelle

• Jedes Modelle der Berechenbarkeit (TM, RAM, Typ-0-Gramatiken, …) beschreiben letztendlich die "gleiche" Berechenbarkeit
• Nach Diskussionen über Automatische beweisführung (Hilbert, 1900), Widerlegung des Konzepts (Gödel, 1934), beschrieb Turing die (heute genannte) Turing Maschine, um die "Unentscheidbarkeit" des Halteproblems zu beweisen
• Church-Turing-These: Die im intuitiven Sinne berechenbare Funktionen sind genau die die von einer TM berechenbar sind

• TM wird mit dem Alphabet \(\left\{ 0, 1, \# \right\}\) kodiert, damit Zustände, Delta-Tabelle, etc. alle nur mit 3 Zeichen dargestellt werden können
• Kodiert man \(\left\{ 0, 1, \# \right\}\) in \(\left\{ 0, 1 \right\}\) um, kann jede TM als natürliche Zahl dargestellt werden, genannt Gödel Nummer der Maschine \(M\): \[ \left\langle M \right\rangle := \mathrm{code}(M) \]
• TM ist dann universell wenn sie gestartet mit \(\left\langle M \right\rangle x\) sich verhält wie \(M\) gestartet mit \(x\).
  • Eine det. 2-Band TM \(\tilde{M}\) kann \(M\) (\(Ot(n)\) zeit und \(s(n)\) platz beschränkt) simulieren, falls \(M\) hällt, in \(\mathcal{O}(s(n))\) Platz und \(\mathcal{O}(t(n))\) Zeit

• Es gibt unentscheidbare Probleme, da es mehr Sprachen als Maschinen gibt
• Das Wortproblem (kurz "Problem") stellt die Frage ob für \(L \subseteq \Sigma^{\ast}\) ein Wort \(x \in L\) ist.
  • Die Charachterische Funktion ist definiert als \[ \chi_L(x) \begin{cases} 1 & \text{wenn } x \in L\\ 0 & \text{ansonsten} \end{cases} \]
  • Für eine 1-Band det. TM \(M\), ist die Menge \[ \mathrm{H} := \left\{ \left\langle M \right\rangle w \;|\; \mathrm{H}\;\text{ hält für w}\right\} \] und heißt das (allgemeine) Halteproblem
    • \(\mathrm{H}\) ist unentscheidbar! (Turing, 1936)

• Annahme es gibt eine Maschine \(M_\mathrm{H}\) welche \(\mathrm{H}\) entscheidet
  1. Dieser Maschine wird ein Programm übergeben, welches ein weiteres annimmt, und falls diese Halten wird, nicht halten wird, und Fall sie nicht halten wird haltet
  2. Frage: Was passiert wenn man diese Maschine sich selbst übergibt?
     • Falls das Programm halten wird, wird es nicht halten
     • Falls das Programm nicht halten wird, wird es halten
  3. Widerspruch bedeutet das \(M_\mathrm{H}\) nicht existieren kann (Halteproblem)
• \(\mathrm{H}\) ist rekursiv aufzählbar ("da ein TM das macht")
  • Das Komplement \(\bar{\mathrm{H}} = \left\{ 0, 1 \right\}^{\ast} \setminus \mathrm{H}\) ist nicht rekursiv aufzählbar

• Für alle 1-Band det TM \(M\) gilt Die Menge \[ \mathrm{H}_{\varepsilon} := \left\{ \left\langle M \right\rangle | \text{M gestartet mit leerem Band hält} \right\} \] heißt initiales Halteproblem
  • \(\mathrm{H}_{\varepsilon}\) ist unentscheidbar, da \(\mathrm{H}_{\varepsilon}\) auf \(\mathrm{H}\) reduzierbar ist.
  • Beweis der Reduktion muss zeigen dass wenn ein \(x \in \mathrm{H}\), dass dann \(f(x) \in \mathrm{H}_{\varepsilon}\), und \(x \notin \mathrm{H}\), dass \(f(x) \notin \mathrm{H}_{\varepsilon}\).

• Ist eine Sprache total berechenbar, gibt es eine Charachterisctische Funktion, welche total und *berechenbar:

  total

  über der ganzen Domäne definiert; eine TM würde halten

  berechenbar

  es existiert eine TM \(M_f\) die die Funktion \(f: \{0, 1\}^{\ast} \rightarrow \{0, 1\}^{\ast}\) mit der Eingabe \(x \in \{0, 1\}^{\ast}\) berechnen kann

• Ist eine Sprache rekursiv Aufzählbar, gibt es eine (partielle-)Funktion \[ \chi^{\prime}_{L}(x) = \begin{cases} 1 & \text{wenn } x \in L\\ \mathit{undef} & \text{ansonsten} \end{cases} \]
  • Diese Funktion ist nicht Total, da der "ansonsten" Fall nicht definiert ist!

• Bei einer Reduktion spricht man von einer total Berechenbaren Funktion, welche alle Wörter \(x\) aus einer Sprache \(L_1\) in einer andere Sprache \(L_2\) Abbildet, ie.: \[ x \in L_1 \Leftrightarrow f(x) \in L_2 \]
  • Dieses wird "\(L_1 \leq L_{2}\)" geschrieben, "\(L_1\) wird auf \(L_2\) reduziert" gesprochen.
  • Surjektivität (ie. jedes Wort in \(L_2\) hat ein "Urwort" in \(L_1\)) ist nicht notwendig
    • Die Funktion muss Total Berechenbar sein, damit die notwendige Injektivität gewährleistet sein kann
  • Entscheidbarkeit und Rekursive Aufzählbarkeit wird von \(L_2\) auf \(L_1\) übertragen im "Ja-Fall", und von \(L_1\) auf \(L_2\) im "Nein-Fall"

• Die Menge der Berechenbaren Funktionen sei \[ \mathcal{R} = \{ f: \{0, 1\}^{\ast} \rightarrow \{0, 1\}^{\ast} \text{ ist berechenbar}\} \]
  • Auf \(\mathcal{S} \subseteq \mathcal{R}\) sei \[ \mathrm{Prog}(\mathcal{S}) = \left\{ \left\langle M \right\rangle | M \;\text{berechnet eine Funktion}\;f \in \mathcal{S}\right\} \], dh. auch alle Programme die \(\mathcal{S}\) berechnen.
  • Laut Reis (1953) ist für \(\emptyset \neq \mathcal{S} \neq \mathcal{R}\), \(\mathrm{Prog}(\mathcal{S})\) nicht berechenbar, dh. man kann nicht die Menge aller nicht-trivialen Programme berechnen, die jeweils eine Sache berechnen (bspw. "Menge der Quadratfunktionen") (beweisbar mittels Reduktion auf das Initiale Halteproblem \(\mathrm{H}_{\varepsilon} \leq \mathrm{Prog}(\mathcal{S})\))

Sprachklasse (oder Sprachfamilie)

Eine Menge \(\mathcal{L}\) von Sprachen \(L_1, L_2, L_3, \ldots\) (bspw. Menge der Entscheidbaren oder r.a. Sprachen)

Abgeschlossen unter \(\mathrm{op}\)

Wenn \(k\) stelliger Operator \(\mathrm{op}\) ein Element aus einer Sprachklasse in die selbst abbildet (bspw. \(\cup\), \(\cap\), aber nicht Komplementbildung)

• Unter einer Nicht-Deterministischen Turing Maschine (nicht-det TM, NTM), versteht man ein Tupel der Form \(M = (Q, \Sigma, \Gamma, B, \delta, q_0, F)\), wo bis auf \(\delta\) alles gleich definiert ist wie bei einer üblichen TM.
  • Die Übergangsfunktion \(\delta\) hat nun den Datentypen \[ \delta: Q \times \Gamma \rightarrow \wp(Q \times \Gamma \times \{ R, L, N \}),\] Wo \(\wp\) die Potenzmenge ist. Dh. jeder Zustand + Eingabe bildet auf einer Menge möglicher neuer Übergänge ab.
  • All diese Zustände werden von der nicht-det TM abgearbeitet,
    • Siehe Jeff Erickson's verschiedene Intuitionen für Nicht-Determinismus in Automaten (Seite 2).
  • Eine NTM kann eine Sprache nicht entscheiden, aber dafür akzeptieren.
  • Jede \(t(n)\) Zeitbeschränkte NTM kann in \(2^{\mathcal{O}(t(n))}\) Zeitbeschränktheit von einer "üblichen" TM simuliert werden, indem alle möglichkeiten (baum-artig) durchlaufen werden

Es sind folgende Sprachklassen definiert:

• "DTIME": \[ \mathrm{DTIME}(t(n)) = \left\{ L \;|\; \text{es gibt eine $\mathcal{O}(t(n))$ zeitbeschr. TM die $L$ entscheidet} \right\} \]
• "NTIME": \[ \mathrm{NTIME}(t(n)) = \left\{ L \;|\; \text{es gibt eine $\mathcal{O}(t(n))$ zeitbeschr. NTM die $L$ akzeptiert} \right\} \]

Ferner gibt es noch:

• "P": \[ P = \bigcup_{k \in \mathbb{N}} \mathrm{DTIME}(n^k)\] Es werden Polynome aus dem Grund genommen, da \({a^x}^y = a^{x \cdot y}\), was bedeutet das die Anzahl an Spuren keinen Einfluss auf die Laufzeitklasse haben
• "NP": \[ NP = \bigcup_{k \in \mathbb{N}} \mathrm{NTIME}(n^k)\]

Die Frage die nun offen Steht ist \(P \stackrel{?}{=} NP\).

CLIQUE

\[ \left\{ \left\langle G, k \right\rangle | \text{$G$ ist eine ungerichteter Graph, der einen vollständigen Teingraphen der Größe $k \in \mathbb{N}$ enthällt.} \right\}, \] wobei \(\left\langle G, k \right\rangle\) eine sinnvolle Kodierung darstellen soll

HAMILTON (Hamilton-Kreis-Problem, \(HC\))

Ein Hamilton-Kreis ist ein Kreis in einem Grpah \(G\), der jeden Knoteng genau einmal enthält.

Daher \[ HC = \left\{ \left\langle G \right\rangle | \text{$G$ ist ungerichteter Graph, der einen Hamilton-Kreis enthällt} \right\} \]

Kann als Optimierungsproblem aufgefasst werden unter der Bedienung dass der längste Kreis gefunden werden soll.

Knotenüberdeckungsproblem (Vertex-Cover, \(VC\))

Gegeben ist ein Graph \(G = (V, E)\). \(A \subseteq V\) ist eine Knotenüberdeckung, wenn jede Kante aus \(E\) mindestens einen Knoten aus \(A\) berührt.

\[ VC = \left\{ \left\langle G, k \right\rangle | \text{$G$ hat einen Knotenüberdeckung, die $A$ mit $\left| A \right| = k \in \mathbb{N}$} \right\} \]

Ist eine Kante nicht in \(VC\), ist bekannt das dessen Nachbar in \(VC\) liegen muss.

Traveling Salesperson Problem (\(TSP\))

\[ TSP = \left\{ \left\langle G, c, k \right\rangle | \text{Der gewichtete Graph $G$ enthällt einen Hamilton-Kreis mit Gewicht $\leq k$. $c: E \rightarrow \mathbb{N}$ sind die Kantengewichte.} \right\} \]

Weitere Problem dieser Art ("besonders Schwer", NP-Vollständig) sind das Rucksackproblem oder das Erfüllbarkeitsproblem.

Für eine Sprache \(L\) über \(\left\{ 0, 1 \right\}\) ist eine det. TM \(V_L\) ein \(t(n)\) beschränkter Verifizierbar, wenn:

1. Die Eingaben von \(V_L\) von der Form \(x \# w; x, v \in \left\{ 0, 1 \right\}^{\ast}\)
2. Die Laufzeit ist \(\mathcal{O}(t(\left| W \right|))\)
3. Für alle \(x \in \left\{ 0, 1 \right\}^{\ast}\): \[ x \in L \Leftrightarrow \exists w: \left| w \right| \leq t(\left| x \right|) \text{ und } V_L \text{ akzeptiert } x \# w\]
   • \(\exists\) weist darauf hin das es einen "relativ kurzen Beweis", dass \(x \in L\) ist.

Eine Sprache ist in \(\mathtt{NTIME}(n)\), gdw. es einen \(t(n)\) zeit-beschränkten Verifizierter \(V_L\) für \(L\) gibt, woraus folgt \[ NP = \left\{ L | \text{es gibt einen polynomiellen Verifizierer für $L$} \right\}. \]

• Wenn \(\forall L \in NP: L \leq VC\), ist \(VC\) NP-Vollständig.

• Eine Grammatik vom Typ Chomsky-0, wird als Tupel \(\left( V, \Sigma, P, S \right)\) definiert, wo

  \(V\)

  Eine endliche Menge von Variablen

  \(\Sigma\)

  Ein endliches Alphabet

  \(S \in V\)

  Startsymbol

  \(P \subseteq (V \cup \Sigma)^{\ast} \setminus \Sigma^{\ast} \times (V \cup \Sigma)^{\ast}\)

  Produktionen, Menge von Ersetzungsregeln, um Variablen mit weiteren Variablen und Elementen des Alphabets zu ersetzen

  Statt \((u, v)\) wird \(u \rightarrow v\) geschrieben.

• Gibt es eine Regel \((u \rightarrow v) \in P\), dann kann aus \(w = \alpha u \beta \in (V \cup \Sigma)^{+}\) das neue Wort \(w^{\prime} = \alpha v \beta \in (V \cup \Sigma)^{\ast}\) direkt abgeleitet werden, geschrieben \(w \rightarrow w^{\prime}\).
• Gibt es mehrere, aber endlich viele solcher Produktionen, um \(w^{\prime}\) aus \(w\) durch Verkettung herzuleiten, sagt man \(w^{\prime}\) kann indirekt abgeleitet werden aus \(w\) (\(w \stackrel{\ast}{\longrightarrow} w^{\prime}\)).
• Alle Wörter die demnach eine Grammatik produzieren kann, werden mit \[ L(G) = \left\{ w | S \stackrel{\ast}{\longrightarrow} w \right\}\] umschrieben

• Grammatiken werden nach Art ihrer Produktionen hirarchisiert

  Kontext-Sensitiv (Typ-1)

  \(\forall (u \rightarrow v) \in P: |u| \leq |v|\)

  Kontext-Frei (Typ-2)

  \(\forall (u \rightarrow v) \in P: u \in V\)

  Alternativ kann ein "Epsilon-Übergang" (\(v \varepsilon\)) nur bei Produktionen der Form \(S \rightarrow \varepsilon\) erlaubt sein, aber dafür darf \(S\) nicht auf der rechten Seite aller Produktionen stehen.

  Regulär (Typ-3)

  \(\forall (u \rightarrow v) \in P: u \in V \land (v \in \left\{ \varepsilon \right\} \cup \Sigma \lor v \in \Sigma \circ V)\)

Allgemein gilt, eine Sprache ist dann und nur dann Rekursiv Aufzählbar wenn es eine Chomsky-0-Grammatik gibt mit \(L(G) = L\)

• Ein DFA (en. deterministic finite Automaton) wird beschrieben durch ein Tupel der Form \((Q, \Sigma, \delta, q_0, F)\), wo:

  \(Q\)

  Endliche Menge von Zuständen

  \(\Sigma\)

  Endliches Eingabealphabet

  \(\delta: Q \times \Sigma \rightarrow Q\)

  Übergangsfunktion.

  Die "Kanonische Fortsetzung" von \(\delta\) erlaubt ein Wort \(w = w_0 w_1 \ldots w_{n-1} w_n \in \Sigma^{\ast}\) als Argument übergeben werden kann, und dieses nacheinander (vollständig) Abgearbeitet wird, und zuletzt der Endzustand nach einlesen von \(w_n\) berechnet wird.

  \(q_{0}\)

  Startzustand

  \(F \subseteq Q\)

  Akzeptierende Endzustände.

  Es gilt, dass wenn ein Wort \(w \in \Sigma^{\ast} \Leftrightarrow \delta(q_0, w) \in F\).

• Alternativ können DFAs (bzw. derren \(\delta\) Funktionen) mit Graphen oder Tabellen angegeben werden.

Akzeptiert ein DFA eine Sprache \(L\), dann gibt es eine Grammatik \(G\) vom Type Chomsky-3 mit \(L = L(G) = L(A)\).

• Analog zur Nicht-Deterministischen TM, teil ein nicht-det. endlicher automat (NFA, engl. nondeterministic finite automaton) mit einem DFA alle Komponenten, nur mit einer \(\delta\) Funktion, auf die Potenzmenge der Zustände abbildet
  • Da für jede Menge \(S\), \(\varepsilon \in \wp(S)\) gilt, kann ein NFA ohne Eingabe von einem Zustand in einen anderen übergehen ("Epsilon-Übergang")
  • Die Menge der Zustände die erreicht werden können von einer Menge von Zuständen über ε-Übergänge kann somit beschreiben werden mittels \[ E(R) = \left\{ q \in Q | \exists r_1, \ldots, r_k \in Q, r_k = q: r_{i+1} \in \delta (r_i, \varepsilon), i = 1, \ldots, k - 1 \right\} \]
• Jede NFA \(N\) kann sowohl in ein DFA \(A\) wie auch eine Typ-3 Grammatik \(G\) umgewandelt werden, damit \(L(N) = L(A) = L(G)\)
  • Die Umwandlung von einem NFA in ein DFA erfordert eine "Potenzmengen Konstruktion", wobei ein deterministischer Automat beschrieben wird in dem jeder Zustand einer Menge von erreichbaren Zuständen symbolisiert

Die reguläre Pumping-Eigenschaft ist für eine Sprache \(L\) über \(\Sigma\) wie folgt definiert: \[ \exists n_L \in \mathbb{N} \forall z \in L, n_{L} \geq |z| \exists u, v, w \in \Sigma^{\ast}: z = uvw \]

Die notwendigen, aber nicht hinreichenden Eigenschaften für eine reguläre Sprache \(L\) sind dann

1. \(|uv| \leq n_L\)
2. \(v \neq \varepsilon\)
3. \(\exists i \geq 0: uv^iw \in L\)

• Alle regulären Sprachen haben die reguläre Pumping-Eigenschaft
  • Existenz der reg. PE beweist nicht das eine Sprache regulär ist (bspw.: \(H\) hat reg. PE)
  • Negation der reg. PE kann beweisen das eine Sprache nicht regulär ist

• Über einem endlichem Alphabet \(\Sigma\) sei eine reguläre Ausdruck rekursiv definiert mittels:
  • \(a\), für \(a \in \Sigma\)
  • \(\varepsilon\)
  • \(\emptyset\)
  • \((R_1 \cup R_2)\) für reg. Ausdrücke \(R_1, R_2\) (Veroderung)
  • \((R_1 \circ R_2)\) für reg. Ausdrücke \(R_1, R_2\) (Konkatenation)
  • \((R^{\ast})\) für reg. Ausdruck \(R\) (Wiederholung)

• Die Chomsky-Normalform kann algorithmisch Konstruiert werden:
  1. Eliminiere alle \(\varepsilon\) Regeln
  2. Eliminiere alle Kettenregeln (\(A \rightarrow B\) und \(B \rightarrow C\) wird zu \(A \rightarrow C\))
  3. Erweitere die Variablen Menge um \(\left\{ A_a \rightarrow a | a \in \Sigma \right\}\) und ersetzte jedes "\(a\)" mit dessen entsprechender Variablen
  4. Jede Regel \(A \rightarrow BCD \ldots Z\) kann baumartig umstrukturiert werden: \(A_1 \rightarrow B A_2\), \(A_2 \rightarrow C A_3\), usw.
  5. Alle Nutzlosen Variablen (dh. eine Variable \(A\) kein Wort herleiten kann) können gelöscht werden.

• Der CYK-Algorithmus löst das Wortproblem (\(w \stackrel{?}{\in} L\)) für Kontext-Freie Sprachen.

  Für diese Sprache muss eine KF. Grammatik in CNF vorliegen, mit ausschließlich nützlichen Variablen. Mit \[ V(i, j) = \begin{cases} \left\{ A | A \rightarrow a_i \in P \right\} & \text{ wenn } i = j \\ \left\{ A | A \rightarrow BC \in P, B \in V(i, k), C \in V(k+1, j), k \in \{ i, \ldots, (j-1) \} \right\} & \text{ sonst} \end{cases} \] wo stets \(A, B, C \in V\)

  • Alternative nicht-rekursive Fassung: \[ V(i,j) = \left\{ A | A \stackrel{\ast}{\rightarrow} w_i, \ldots, w_j \right\} \] für \(i \leq j\) und \(w = a_1, \ldots, a_n \in \Sigma^{\ast}\)
• Es gilt dann \(w \in L(G) \Leftrightarrow S \in V(1, n)\) für \(w = w_1 \ldots w_n\).

• Eine Sprache \(L\) hat die kf. Pump-Eigenschaft, wenn für \[ \exists n_L \in \mathbb{N} \forall z \in L; |z| \geq n_L \exists u, v, w, x, y \in \Sigma^{\ast}: z = uvwxy \] mit
  1. \(|uwx| \leq n_L\)
  2. \(vx \neq \varepsilon\)
  3. \(\forall i \geq 0: uv^iw^iy \in L\)

• Ein nicht-det. Kellerautomat (NPDA, engl. non-deterministic pushdown automaton) wird mittels \((Q, \Sigma, \Gamma, S, Z_0, F)\) definiert, wobei \(Q\), \(\Sigma\) und \(F\) wie bei NFA's definiert sind, und ansonsten

  \(\Gamma\)

  Das Kelleralphabet

  \(\delta: Q \times (\Sigma \cup \left\{ \varepsilon \right\}) \times (\Gamma \cup \left\{ \varepsilon \right\}) \rightarrow \wp(Q \times L^{\ast})\)

  Zustandsübergangsfunktion

  \(S\)

  wie \(q_0\), der Startzustand

  \(Z_{0}\)

  "Kellergrundsymbol"

• Ein Kellerautomat ließt eine Eingabe nacheinander ein, uns kann währenddessen auf einen "Stapel" Symbole aus \(\Gamma\) abspeichern. Die Übergangsfunktion kann das oberste Elemente benutzen um verschiedene Verhaltensweisen zu bestimmen
• Es ist zu beachten dass \(L_2 = L_{NPDA} \supset L_{DPDA}\), wobei \(L_{DPDA}\) die Sprachklasse ist die von einem deterministischen Kellerautoaten erkannt werden kann.

• Ein kf. Sprache ist unter Vereinigung \(\cup\), Konkatenation \(\circ\) und Wiederholung \(\ast\) abgeschlossen, aber nicht unter Durchschnitt \(\cap\) und Komplementbildung.