TU Wien:Theoretische Informatik und Logik VU (Fermüller, Oswald)/Zusammenfassung BFSK: Unterschied zwischen den Versionen
Zeile 122: | Zeile 122: | ||
* B rekursiv aufzählbar → A rekursiv aufzählbar | * 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 | ;Satz von Rice | ||
:Jede nicht triviale Eigenschaft der rekursiv aufzählbaren Sprachen ist unentscheidbar. | :Jede nicht triviale Eigenschaft der rekursiv aufzählbaren Sprachen ist unentscheidbar. |
Aktuelle Version vom 15. November 2019, 12:00 Uhr
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) |
Inhaltsverzeichnis
Formale Sprachen[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]
Werden von endlichen Automaten akzeptiert und von #Reguläre Grammatiken erzeugt.
Pumping Lemma[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:
- Der Opponent gibt eine Schranke
vor.
- Der Proponent wählt ein Wort
.
- Der Opponent zerlegt
in drei Teile,
wobei
und
gelten muss.
- Der Proponent versucht ein
zu finden, sodass
. Gelingt ihm dies, hat er gewonnen.
Abgeschlossenheit[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]
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]
- 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]
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]
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]
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]
- 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]
- Aus jeder Variablen
ist ein Terminalwort
ableitbar.
- Für jedes Symbol
gibt es eine Satzform v, die a enthält.
- Elimination von ε-Produktionen (
).
- Elimination von Einheitsproduktionen (
)
Abgeschlossenheit[Bearbeiten]
Kontextfreie Sprachen sind abgeschlossen unter
- Homomorphismen
- Schnitt mit regulären Sprachen
Beispiele[Bearbeiten]
- Dyck-Sprachen
ist die Wortmenge der wohlgeformten Klammerausdrücke mit
unterschiedlichen Klammerpaaren. (Wikipedia)
Satz von Chomsky-Schützenberger[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]
gsm (generalized sequential machine)
Komplexität[Bearbeiten]
Siehe auch TU Wien:Algorithmen und Datenstrukturen VU (Szeider)/Zusammenfassung Test 2.
- Co-NP
- Enthält die Sprachen, deren Komplement in NP ist.