TU Wien:Theoretische Informatik und Logik VU (Fermüller, Oswald)/Zusammenfassung BFSK: Unterschied zwischen den Versionen
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 2: | Zeile 2: | ||
{| class=wikitable | {| class=wikitable | ||
− | ! | + | ! Sprachfamilie !! Grammatiktyp !! Maschinenmodell |
|- | |- | ||
− | | [[# | + | | [[#rekursiv aufzählbar|rekursiv aufzählbar]] || Typ-0: [[#Grammatiken|unbeschränkte Grammatik]] || Turingmaschine (EA + RAM) |
|- | |- | ||
| kontextsensitiv || Typ-1: kontextsensitiv, monoton || linear beschränkter Automat (EA + beschr. RAM) | | kontextsensitiv || Typ-1: kontextsensitiv, monoton || linear beschränkter Automat (EA + beschr. RAM) | ||
Zeile 100: | Zeile 100: | ||
* <math>F \subseteq Q</math> Menge der Endzustände | * <math>F \subseteq Q</math> Menge der Endzustände | ||
− | + | ;Akzeptierte Sprache <math>L(M)</math> | |
− | + | :Besteht aus genau all jenen Wörtern, bei deren Analyse M einen Endzustand erreicht. | |
− | + | ;Rekursiv aufzählbare Sprachen{{anchor|rekursiv aufzählbar}} | |
− | |||
− | ;Rekursiv aufzählbare Sprachen | ||
:Es gibt eine TM, welche die Sprache akzeptiert, aber bei <math>w \notin L</math> unter Umständen unendlich läuft. | :Es gibt eine TM, welche die Sprache akzeptiert, aber bei <math>w \notin L</math> unter Umständen unendlich läuft. | ||
;Rekursive Sprachen | ;Rekursive Sprachen | ||
Zeile 124: | 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. | ||
Zeile 142: | Zeile 142: | ||
* <math>P \subseteq (N \cup T)^+ \times (N \cup T)^*</math> ... Produktionen | * <math>P \subseteq (N \cup T)^+ \times (N \cup T)^*</math> ... Produktionen | ||
* <math>S \in N</math> ... Startsymbol | * <math>S \in N</math> ... Startsymbol | ||
+ | |||
+ | Jede Grammatik dieser Form heißt '''unbeschränkte Grammatik'''. Gilt für alle Produktionen <math>\alpha \to \beta \in P</math>: | ||
+ | |||
+ | * <math>|\alpha| \leq |\beta|</math> so heißt G '''monoton''' | ||
+ | * <math>\alpha = uAv</math> und <math>\beta = uwv</math> für ein <math>A \in N, w \in (N \cup T)^+</math> und <math>u,v \in (N \cup T)^*</math> so heißt G '''kontextsensitiv'''. | ||
+ | * <math>A \to \beta</math> für ein <math>A \in N</math>, so heißt G [[#Kontextfreie Grammatiken|kontextfrei]]. | ||
+ | * <math>A \to aB</math> oder <math>A \to \epsilon</math>, so heißt G [[#Reguläre Grammatiken|regulär]]. | ||
Wörter, die nur aus Terminalsymbolen bestehen, werden Satzformen genannt. | Wörter, die nur aus Terminalsymbolen bestehen, werden Satzformen genannt. | ||
Zeile 170: | Zeile 177: | ||
Alle Produktionen sind von der Form <math>A \to aB</math> oder <math>A \to a</math>. | Alle Produktionen sind von der Form <math>A \to aB</math> oder <math>A \to a</math>. | ||
<math>S \to \epsilon</math> ist erlaubt, sofern S nicht auf einer rechten Seite vorkommt. | <math>S \to \epsilon</math> ist erlaubt, sofern S nicht auf einer rechten Seite vorkommt. | ||
+ | |||
+ | ;Beispiele | ||
+ | |||
+ | * <math>L = \{a\}^* = \{ a^n \mid n \geq 0\}</math> | ||
+ | : <math>G = (\{S\}, \{a\}, \{S \to aS \mid \epsilon\}, S)</math> | ||
+ | * <math>L = \{a\}^+ = \{ a^n \mid n \geq 1\}</math> | ||
+ | : <math>G = (\{S\}, \{a\}, \{S \to aS \mid a\}, S)</math> | ||
=== Kontextfreie Grammatiken === | === Kontextfreie Grammatiken === | ||
Zeile 192: | Zeile 206: | ||
* Schnitt mit regulären Sprachen | * Schnitt mit regulären Sprachen | ||
− | ==== | + | ==== Beispiele ==== |
+ | ;Dyck-Sprachen | ||
<math>D_n</math> ist die Wortmenge der wohlgeformten Klammerausdrücke mit <math>n</math> unterschiedlichen Klammerpaaren. ([[de.wikipedia:Dyck-Sprache|Wikipedia]]) | <math>D_n</math> ist die Wortmenge der wohlgeformten Klammerausdrücke mit <math>n</math> unterschiedlichen Klammerpaaren. ([[de.wikipedia:Dyck-Sprache|Wikipedia]]) | ||
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.