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

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Sprachfamilie 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[Bearbeiten | Quelltext bearbeiten]

  • 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 .
  • 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 , dann ist das Spiegelbild von w.
  • Ein Wort w heißt Palindrom, wenn gilt.
  • : Menge aller (nicht-leeren) Wörter über
  • : Menge aller Wörter (inklusive ε) über
  • Formale Sprache: beliebige Teilmenge L von
  • : Menge aller Sprachen
  • 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|.

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 (d.h., mit der Menge der Natürlichen Zahlen) ist, heißt abzählbar (unendlich).

ist abzählbar (falls endlich).

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

Reguläre Sprachen[Bearbeiten | Quelltext bearbeiten]

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

Pumping Lemma[Bearbeiten | Quelltext bearbeiten]

Für alle regulären Sprachen gilt:

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 vor.
  2. Der Proponent wählt ein Wort .
  3. Der Opponent zerlegt in drei Teile, wobei und gelten muss.
  4. Der Proponent versucht ein zu finden, sodass . Gelingt ihm dies, hat er gewonnen.

Abgeschlossenheit[Bearbeiten | Quelltext bearbeiten]

  • definitionsgemäß gegenüber Vereinigung, Verkettung und Stern-Operator
  • Plus-Operator:
  • Komplement bzgl. : konstruire DEA und vertausche End- und Nichtendzustände (Falle nicht vergessen!)
  • Durchschnitt
  • Differenz
  • 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[Bearbeiten | Quelltext bearbeiten]

Mit einem Band:

  • endliche Menge der Zustände
  • endliche Menge der Eingabesymbole
  • endliche Menge der Bandsymbole,
  • Übergangsfunktion
  • Startzustand
  • Blank-Symbol
  • Menge der Endzustände
Akzeptierte Sprache
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 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 und auch ihr Komplement rekursiv aufzählbar, so ist (wie auch ) 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[Bearbeiten | Quelltext bearbeiten]

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

Eine Eigenschaft von Sprachen ist eine Teilmenge P von rekursiv aufzählbaren Sprachen (über einem geeigneten Alphabet).

Eine Eigenschaft ist trivial, wenn sie entweder leer ist, oder aus allen rekursiv aufzählbaren Sprachen besteht. Andernfalls ist sie nicht trivial.

Satz von Rice
Jede nicht triviale Eigenschaft der rekursiv aufzählbaren Sprachen ist unentscheidbar.
Halteproblem
rekursiv aufzählbar, aber nicht entscheidbar

Grammatiken[Bearbeiten | Quelltext bearbeiten]

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

Dargestellt wird eine formale Grammatik durch das 4-Tupel .

  • ... endliche Menge von Nonterminalen
  • ... endliche Menge von Terminalsymbolen ()
  • ... Produktionen
  • ... Startsymbol

Jede Grammatik dieser Form heißt unbeschränkte Grammatik. Gilt für alle Produktionen :

  • so heißt G monoton
  • und für ein und so heißt G kontextsensitiv.
  • für ein , so heißt G kontextfrei.
  • oder , so heißt G regulär.

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

Wir schreiben:

  • statt
  • statt

Chomsky-Hierarchie[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Alle Produktionen sind von der Form oder .

Alternativ:

Alle Produktionen sind von der Form oder . ist erlaubt, sofern S nicht auf einer rechten Seite vorkommt.

Beispiele

Kontextfreie Grammatiken[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

  1. Aus jeder Variablen ist ein Terminalwort ableitbar.
  2. Für jedes Symbol gibt es eine Satzform v, die a enthält.
  3. Elimination von ε-Produktionen ().
  4. Elimination von Einheitsproduktionen ()

Abgeschlossenheit[Bearbeiten | Quelltext bearbeiten]

Kontextfreie Sprachen sind abgeschlossen unter

  • Homomorphismen
  • Schnitt mit regulären Sprachen

Beispiele[Bearbeiten | Quelltext bearbeiten]

Dyck-Sprachen

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

Satz von Chomsky-Schützenberger[Bearbeiten | Quelltext bearbeiten]

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: so existiert, dass

,

wobei R eine reguläre Sprache über bezeichnet.

gsm-Abbildungen[Bearbeiten | Quelltext bearbeiten]

gsm (generalized sequential machine)

Komplexität[Bearbeiten | Quelltext bearbeiten]

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

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