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

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

• 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|\leq 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|\leq 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

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

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
• $\alpha = uAv$ und $\beta = uwv$ für ein $A \in N, w \in (N \cup T)^+$ und $u,v \in (N \cup T)^*$ so heißt G kontextsensitiv.
• $A \to \beta$ für ein $A \in N$, so heißt G kontextfrei.
• $A \to aB$ oder $A \to \epsilon$, so heißt G regulär.

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.

Beispiele

• $L = \{a\}^* = \{ a^n \mid n \geq 0\}$

$G = (\{S\}, \{a\}, \{S \to aS \mid \epsilon\}, S)$

• $L = \{a\}^+ = \{ a^n \mid n \geq 1\}$

$G = (\{S\}, \{a\}, \{S \to aS \mid a\}, S)$

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

Beispiele

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.