TU Wien:Theoretische Informatik und Logik VU (Fermüller, Oswald)/Zusammenfassung BFSK

From VoWi
Jump to navigation Jump to search

Diese Seite fasst den Stoff von Teil 1: Berechenbarkeit, Formale Sprachen und Komplexitätstheorie (BFSK) zusammen.

Sprachklasse Grammatiktyp Maschinenmodell
rekursiv aufzählbar Typ-0: unbeschränkte Grammatik Turingmaschine (EA + RAM)
kontextsensitiv Typ-1: kontextsensitiv, monoton linear beschränkter Automat (EA + beschr. RAM)
kontextfrei Typ-2: kontextfreie Grammatik Kellerautomat (EA + Stack)
regulär Typ-3: reguläre Grammatik endlicher Automat (EA)

Formale Sprachen

  • Alphabet: endliche, nicht-leere Menge atomarer Symbole (Σ, T)
  • Wort über Σ: endliche Folge von Symbolen aus Σ
  • Länge eines Wortes w über Σ (geschrieben |w|): Anzahl der Symbole, die w enthält
  • Leerwort: Wort mit der Länge 0, geschrieben ε, d.h. |ε| = 0
  • Für ein Wort w über Σ und ein Symbol a ∈ Σ bezeichnen wir die Anzahl der Symbole a in w mit |w|_a.
  • Konkatenation: Hintereinanderschreiben von Wörtern
Seien x, y Wörter mit |x| = n, |y| = m, dann ist x · y = xy und |xy| = n + m
  • Potenzbildung: Verkettung eines Wortes w mit sich selbst, wobei w0 = ε und wn = wwn−1
  • Sei w = a_1a_2 \dots a_{n-1}a_n, dann ist w^r = a_na_{n-1} \dots a_2a_1 das Spiegelbild von w.
  • Ein Wort w heißt Palindrom, wenn w = w^r gilt.
  • \Sigma^+: Menge aller (nicht-leeren) Wörter über \Sigma
  • \Sigma^*: Menge aller Wörter (inklusive ε) über \Sigma
  • Formale Sprache: beliebige Teilmenge L von \Sigma^*, L \subseteq \Sigma^*
  • \mathcal P(\Sigma^*): Menge aller Sprachen L \subseteq \Sigma^*
  • Operationen auf Sprachen
    • Konkatenation
    • Potenzbildung
    • Kleene-Stern
  • Mengenoperationen auf Sprachen
    • Vereinigung
    • Durchschnitt
    • Differenz
    • Komplement

Die Anzahl der Elemente einer Menge M bezeichnet man als Kardinalität, geschrieben als card(M) oder |M|.

|\mathcal P(A)| = 2^{|A|}

Zwei Mengen A und B heißen gleichmächtig, wenn es eine bijektive Abbildung von A auf B gibt.

Jede Menge, die gleichmächtig mit \N (d.h., mit der Menge der Natürlichen Zahlen) ist, heißt abzählbar (unendlich).

\Sigma^* ist abzählbar (falls \Sigma endlich).

Jede unendliche, nicht abzählbare Menge heißt überabzählbar.

Reguläre Sprachen

Werden von endlichen Automaten akzeptiert und von #Reguläre Grammatiken erzeugt.

Pumping Lemma

Für alle regulären Sprachen gilt:

\exists {\color{red} m} \geq 0 \quad
\forall {\color{blue} w} \in L \text{ mit } |w| \geq m \quad
\exists {\color{red} x,y,z} \text { mit } xyz = w, |xy|\geq m, y\neq \epsilon \quad
\forall {\color{blue} i} \geq 0 : \quad
xy^iz \in L

Um zu zeigen, dass eine Sprache nicht regulär ist, muss der Proponent folgendes Spiel immer gewinnen können:

  1. Der Opponent gibt eine Schranke \color{red}m vor.
  2. Der Proponent wählt ein Wort \color{blue}w.
  3. Der Opponent zerlegt w in drei Teile, \color{red}xyz wobei |xy|\geq m und y\neq \epsilon gelten muss.
  4. Der Proponent versucht ein {\color{blue}i} \geq 0 zu finden, sodass xy^iz \notin L. Gelingt ihm dies, hat er gewonnen.

Abgeschlossenheit

  • definitionsgemäß gegenüber Vereinigung, Verkettung und Stern-Operator
  • Plus-Operator: A^+ = A^* \cdot A
  • Komplement bzgl. \sigma^*: konstruire DEA und vertausche End- und Nichtendzustände (Falle nicht vergessen!)
  • Durchschnitt A \cap B = \overline{\bar A \cup \bar B}
  • Differenz A - B = A \cap \bar B
  • Spiegelung: Konstruiere EA, vertausche Start- mit Endzustand, kehre alle Zustandsübergänge um.
  • Homomorphismen: repräsentiere L durch regulären Ausdruck und ersetze alle Vorkommnisse von a durch Ausdruck für h(a).

Turingmaschinen

Mit einem Band:

M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)

  • Q endliche Menge der Zustände
  • \Sigma endliche Menge der Eingabesymbole
  • \Gamma endliche Menge der Bandsymbole, \Sigma \subset \Gamma
  • \delta : Q \times \Gamma \to Q \times \Gamma \times \{ L, R, S \} Übergangsfunktion
  • q_0 \in Q Startzustand
  • B \in \Gamma - \Sigma Blank-Symbol
  • F \subseteq Q Menge der Endzustände
Akzeptierte Sprache L(M)
Besteht aus genau all jenen Wörtern, bei deren Analyse M einen Endzustand erreicht.
Rekursiv aufzählbare Sprachen
Es gibt eine TM, welche die Sprache akzeptiert, aber bei w \notin L unter Umständen unendlich läuft.
Rekursive Sprachen
Auch entscheidbare Sprachen genannt: Es gibt eine TM, welche die Sprache akzeptiert und immer anhält.
  • Das Komplement einer rekursiven Sprache ist rekursiv.
  • Ist eine Sprache L und auch ihr Komplement \bar L rekursiv aufzählbar, so ist L (wie auch \bar L) rekursiv.
Church-Turing-These
Gibt es ein endlich beschreibbares Verfahren zur exakten Spezifizierung einer formalen Sprache L, so gibt es eine Turingmaschine, die L akzeptiert.

Reduktionen und Entscheidbarkeit

Reduktion

Seien A und B Sprachen mit A ≤ B. Dann gilt:

  • A nicht entscheidbar → B nicht entscheidbar
  • A nicht rekursiv aufzählbar → B nicht rekursiv aufzählbar
  • B entscheidbar → A entscheidbar
  • B rekursiv aufzählbar → A rekursiv aufzählbar
triviale Eigenschaft
Ist entweder leer oder besteht aus allen rekursiv aufzählbaren Sprachen.
Satz von Rice
Jede nicht triviale Eigenschaft der rekursiv aufzählbaren Sprachen ist unentscheidbar.
Halteproblem
rekursiv aufzählbar, aber nicht entscheidbar

Grammatiken

Eine formale Grammatik dient der eindeutigen Erzeugung und Beschreibung einer formalen Sprache.

Dargestellt wird eine formale Grammatik durch das 4-Tupel G = (N, T, P, S).

  • N ... endliche Menge von Nonterminalen
  • T ... endliche Menge von Terminalsymbolen (N \cap T = \{\})
  • P \subseteq (N \cup T)^+ \times (N \cup T)^* ... Produktionen
  • S \in N ... Startsymbol

Jede Grammatik dieser Form heißt unbeschränkte Grammatik. Gilt für alle Produktionen \alpha \to \beta \in P:

  • |\alpha| \leq |\beta| so heißt G monoton

Wörter, die nur aus Terminalsymbolen bestehen, werden Satzformen genannt.

Wir schreiben:

  • \alpha\to\beta statt (\alpha, \beta) \in P
  • \alpha\to\beta_1 \mid \cdots \mid \beta_n statt \alpha \to \beta_1, \dots, \alpha \to \beta_n

Chomsky-Hierarchie

Typ-0 rekursiv aufzählbar Turingmaschine (EA + RAM)
Typ-1 kontextsensitiv linear beschränkter Automat (EA + beschr. RAM)
Typ-2 kontextfrei Kellerautomat (EA + Stack)
Typ-3 regulär endlicher Automat (EA)

Reguläre Grammatiken

Alle Produktionen sind von der Form A \to aB oder A \to \epsilon.

Alternativ:

Alle Produktionen sind von der Form A \to aB oder A \to a. S \to \epsilon ist erlaubt, sofern S nicht auf einer rechten Seite vorkommt.

Kontextfreie Grammatiken

  • Linksableitung — es wird immer das erste Nonterminal ersetzt
  • Rechtsableitung — es wird immer das letzte Nonterminal ersetzt
  • Parallelableitung — es werden alle Nonterminale gleichzeitig ersetzt

Chomsky-Normalform

  1. Aus jeder Variablen A \in N ist ein Terminalwort w \in T^* ableitbar.
  2. Für jedes Symbol a \in (N \cup T) gibt es eine Satzform v, die a enthält.
  3. Elimination von ε-Produktionen (a \to \epsilon).
  4. Elimination von Einheitsproduktionen (A \to B\quad A, B \in N)

Abgeschlossenheit

Kontextfreie Sprachen sind abgeschlossen unter

  • \cup, \cdot, *
  • Homomorphismen
  • Schnitt mit regulären Sprachen

Dyck-Sprachen

D_n ist die Wortmenge der wohlgeformten Klammerausdrücke mit n unterschiedlichen Klammerpaaren. (Wikipedia)

Satz von Chomsky-Schützenberger

Jede kontextfreie Sprache ist eine homomorphes Bild des Durchschnitts einer regulären Sprache mit einer Dyck-Sprache.

Eine Sprache L über Σ ist genau dann kontextfrei, wenn zu einem n ≥ 0 ein Homomorphismus h: \Gamma^*_n \to \Sigma^* so existiert, dass

L = h(D_n \cap R),

wobei R eine reguläre Sprache über \Gamma_n bezeichnet.

gsm-Abbildungen

gsm (generalized sequential machine)

Komplexität

Siehe auch TU Wien:Algorithmen und Datenstrukturen VU (Szeider)/Zusammenfassung Test 2.

Co-NP
Enthält die Sprachen, deren Komplement in NP ist.