Inhaltsverzeichnis
Sprachen
„Sprache entscheidbar“ = Wortproblem entscheidbar
Äquivalent
- Wortproblem semi-entscheidbar
- Sprache semi-entscheidbar
- Sprache rekursiv aufzählbar
- Sprache ist Typ 0
- Es existiert TM für Sprache
- $\chi_A$ ist Turing-berechenbar
- Sprache ist Definitionsbereich einer berechenbaren Funktion
- Sprache ist Wertebereich einer berechenbaren Funktion
(formale) Sprache
Menge von Wörtern die als korrekt erachtet werden
$L \subseteq \Sigma$
Typ
Sprache ist vom Typ $x$, wenn Grammatik vom Typ $x$ existiet.
Vom Typ einer Grammatik kann nicht auf Typ der Sprache geschlossen werden.
Chomsky
„0 hat nix Vorgeschrieben“
| Typ 0 | Typ 1 | Typ 2 | Typ 3 | |||
|---|---|---|---|---|---|---|
| ND | D | |||||
| Name | Alle Grammatiken | Kontextsensitiv | Kontextfrei | Regulär | ||
| Bedingung $w_1 \rightarrow w_2$ | - | $|w_1| \le |w_2|$ | $|w_1| \le |w_2|$ $w_1$ Exakt eine Variable | $|w_1| \le |w_2|$ $w_1$ Exakt eine Variable $V \rightarrow t$ oder $V \rightarrow tV$ |
||
| Produktionsgröße | kann schwanken | monoton Steigend | ||||
| Probleme | Wort~ | semi-entscheidbar | entscheidbar O($2^n$) NP-hart | entscheidbar O(n³) | entscheidbar O(n) | entscheidbar O(n) |
| Leerheits~ | nicht entscheidbar | entscheidbar | ||||
| Endlichkeits~ | nicht entscheidbar | entscheidbar | ||||
| Äquivalenz~ | nicht entscheidbar | entscheidbar | entscheidbar NP-hart |
|||
| Schnitt~ | nicht entscheidbar | entscheidbar | ||||
| Abschluss- Eigenschaften | Vereinigung | Ja | Ja | Ja | Nein | Ja |
| Schnitt | Ja | Ja | Nein | Nein | Ja | |
| Kompliment | Nein | Ja | Nein | Ja | Ja | |
| Produkt | Ja | Ja | Ja | Nein | Ja | |
| Stern | Ja | Ja | Ja | Nein | Ja | |
| Syntaxbaum | - | Ja | Ja (String nach links/rechts) |
|||
| (Extended) BNF | - | Ja | ||||
Typ 3
DFA ⇔ NFA ⇔ Typ(L) =3
Satz von Kleene Die Menge der durch reguläre Ausdrücke beschreibbaren Sprachen ist genau die Menge der regulären Sprachen.
- Hat kein gedächtniss
- Kann minimal gemacht werden
- Kann eindeutig gemacht werden (Minimal)
Grammatik -> DFA
- Grammatik → NFA
- NFA → DFA
Grammatik -> NFA
Gegeben
$G = (V, \Sigma, P, S)$
Ergebniss
$M = (V \cup \{X\}, \Sigma, \delta, \{S\}, E)$
mit
\[ E = \begin{cases} \{S, X\} & \text{ wenn } S \rightarrow \epsilon \in P \\ \{X\} & \text{ sonst } \end{cases} \]
mit
| Grammatik Regel | NFA Produktions- Regel |
|---|---|
| A → aB | $\delta(A, a) = B$ |
| A → a | $\delta(A, a) = X$ |
NFA -> DFA
$M' = (Z', \Sigma, \delta', z_0, E')$ mit
- $Z' = \mathcal P(Z)$
- $z_0' = "S"$ z.B. „{$S_1, S_2, S_3$}“
- $E'$ alle $Z'$ die mindestens einen der alten Endzustände enthalten.
Danach: Aufräumen (alle nicht erreichbaren knoten löschen)
Pumping Leamma
Schlüsse
Typ 3 Sprachen $\subset$ Pumping Lemma $\subset$ Sprachen
„Mehr Sprachen erfüllen das Pumping Leamma als in T3 sind.“
- $L \in T3 \Rightarrow L \in PL$
- $L \not\in T3 \Rightarrow L \in PL \vee L \not\in PL$
- $L \in PL \Rightarrow L \in T3 \vee L \not\in T3$
- $L \not\in PL \Rightarrow L \in T3$
Bedingungen
Für alle Wörter $x = uvw$, die mindestens $n$ lang sind muss gelten:
| $|v| \ge 1$ | uvw muss existieren |
| $|uv| \le n$ | uvw mindestens n lang |
| $uv^iw \in L \forall i \ge 0$ | uvw pumpbar |
Beweisidee
Mit $x = uvw$ beliebig, aber von $n$ abhängig, einen Widerspruch in den Regeln herbeiführen.
Minimalautomat
Achte auf den Versatz von Zeilen und Spalten!
| Unmarkierte Zustände | $\sigma_1$ | $\sigma_2$ | … | Ergebniss |
|---|---|---|---|---|
| {0,1} | $\{\delta(0, \sigma_1), \delta(1, \sigma_1)\} \times$ | $\{\delta(0, \sigma_2), \delta(1, \sigma_2)\} \checkmark$ | Markieren | |
| {0,2} | $\{\delta(0, \sigma_1), \delta(2, \sigma_1)\} \times$ | $\{\delta(0, \sigma_2), \delta(2, \sigma_2)\} \times$ | Zusamenfassen | |
| {0,3} | $\{\delta(0, \sigma_1), \delta(3, \sigma_1)\} \checkmark$ | - | Markieren | |
| {1,2} | $\{\delta(1, \sigma_1), \delta(2, \sigma_1)\} \checkmark$ | - | Markieren | |
| {1,3} | $\{\delta(1, \sigma_1), \delta(3, \sigma_1)\} \times$ | $\{\delta(1, \sigma_2), \delta(3, \sigma_2)\} \times$ | Zusamenfassen | |
| {2,3} | $\{\delta(2, \sigma_1), \delta(3, \sigma_1)\} \checkmark$ | - | Markieren |
- Alle Paare parkieren wo ein $\in E$ das andere nicht (XOR).
- Loop über Tabelle
- Wenn Ergebnis markiert, markiere auch diese
- Unmarkierte zusamenfassen
Typ 2
- Typ(L) ⇔ nichtdeterministischer Kellerautomat
- deterministisch kontextfreie Sprache ⇔ deterministischer Kellerautomat
- deterministisch kontextfreie Sprachen $\subset$ kontextfreie Sprachen
Chomsky Normalform (CNF)
Nur
- A → a
- A → CD
⇒ Ableitungsbaum = Binärbaum
- $\epsilon$-Produktionen entfernen.
A → afür jede Konstante einfürenU → Xyz⇒U → XYZ
Konstanten durch Variablen in allen alten Regeln ersetzenU → XYZ⇒U → XV&V → YZ
Aufsplitten wenn rechte Seite länger als 2X → Y&Y → X⇒ ÜberallXundYdruchZersetzen
Zyklen entfernen- Ketten entfernen (von hinten)
Greibach Normalform (GNF)
Nur
- $A \rightarrow aB_1B_2B_3 \dots B_k$ (Mindestens 2
B)
Pumping Leamma
Bedingungen
Für alle Wörter $x = uvwxy$, die mindestens $n$ lang sind muss gelten:
| $|vx| \ge 1$ | uvwxy eins von beiden muss existieren |
| $|vwx| \le n$ | uvwxy mindestens n lang |
| $uv^iwx^iy \in L \forall i \ge 0$ | uvwxy pumpbar |
Beweisidee
Mit $x = uvwxy$ beliebig, aber von $n$ abhängig, einen Widerspruch in den Regeln herbeiführen.
Grammatik -> Kellerautomat
$G = (V, \Sigma, \delta, S)$ ⇒ $M = (\{z\}, \Sigma, V \cup \Sigma, \delta, z, S)$
- Nur ein Zustand
z - Startvariable
Sder Grammatik wird zu unterstem Kellerelement (entspricht #) - Für jede Produktion
A → Xyzergänze Produktion $(z, \epsilon, A) \rightarrow (u, Xyz)$
(Mache Variablenableitungen (Auflösungen) im Keller) - Für jedes $a \in \Sigma$ ergänze Produktion $(z, a, a) \rightarrow (z, \epsilon)$
(Wenn Keller und Wort übereinstimmen, lösche sie)
CYK-Algorithmus
CNF Normalform
Typ 1
Typ(L) = 1 ⇔ Nicht deterministische, linear beschränkte TM
Wort ist akzeptiert wenn TM
- hält
- in Endzustand
- (Band ist egal)
Church-Turing-These
Alles was man „intuitiv“ berechnen kann, kann man auch mit einer Turingmaschine berechnen.
Kuroda Normalform
Nur
- A → a
- A → CD
- A → C (neu)
- AB → CD (neu)
⇒ Ableitungsbaum = Binärbaum
- $\epsilon$-Produktionen entfernen.
A → afür jede Konstante einfürenU → Xyz⇒U → XYZ
Konstanten durch Variablen in allen alten Regeln ersetzen- $A_1A_2A_3 \rightarrow B_1B_2B_3B_4B_5$
$\Rightarrow$
$A_1A_2 \rightarrow B_1X_1$
$X_1A_3 \rightarrow B_2X_2$
$X_2 \rightarrow B_3X_3$
$X_3 \rightarrow B_4B_5$
Aufsplitten wenn rechte Seite länger als 2 (neu) U → XYZ⇒U → XV&V → YZ
Aufsplitten wenn rechte Seite länger als 2X → Y&Y → X⇒ ÜberallXundYdruchZersetzen
Zyklen entfernen- Ketten entfernen (von hinten)
Typ
Typ(L) = 0 ⇔ (Nicht) deterministische TM
Wort ist akzeptiert wenn TM
- hält
- in Endzustand
- (Band ist egal)
Probleme
Wortproblem (Sprache)
Gefragt
„Ist Wort in Sprache?“
Beweis
Typ 2: CYK
Leerheitsproblem (Sprache)
Gefragt
„Gibt es akkzeptierte Wörter?“
Beweis
Kein Pfad von Start zu Ende.
Endlichkeitsproblem (Sprache)
Gefragt
„Gibt es nur endlich viele Wörter?“
Beweis
Zyklus
Schnittproblem (Sprache)
Gefragt
„Haben zwei Sprachen die selben Wörter?“
Beweis
- $L = L_1 \cap L_2$
- Leerheitsproblem von $L$
Äquivalenzproblem (Sprache)
Gefragt
„Sind zwei Sprachen gleich?“
Beweis
Typ 3: Isomorphie von Minimalautomaten
(Allgemeines) Halteproblem
Gegeben
- TM (codiert)
- Eingabe
Gefragt
„Hält das Programm?“
Entscheidbarkeit
nicht entscheidbar & semi-entscheidbar
Spezielles Halteproblem
Gegeben
- TM (codiert)
Gefragt
„Hält das Programm auf sich selbst angewendet?“
Entscheidbarkeit
nicht entscheidbar & semi-entscheidbar
Leerband TM
Gegeben
- TM (codiert)
Gefragt
„Hält das Programm auf leerem Band?“
Entscheidbarkeit
nicht entscheidbar & semi-entscheidbar
Satz von Rice
Gegeben
- Sei $R = \{g \mid g \text{Truing berechenbar}\}$
Unendliche und konstante Menge an Funktionen - Sei $S \subset R$ mit $\emptyset \neq S \neq R$
Gewünschtest funktionales Verhalten einer TM verhalten
Gefragt
„Berechnet die TM $M_w$ mindestens eine Funktion aus S?“
Entscheidbarkeit
nicht entscheidbar (semi-entscheidbar?)
Postsche Korrespondenzproblem (PCP)
Gegeben
- Endliche Folge von
nTupeln (Dominosteinen) $(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)$ mit $x_i, y_i \in \Sigma^+$ (Ohne 𝞮)
Gefragt
„Gibt es eine Folge $i_1, i_2, \dots i_n$ so dass $x_{i_1} x_{i_2} \dots x_{i_n} = y_{i_1} y_{i_2} \dots y_{i_n}$ (obere Zeile = untere Zeile)?“
Entscheidbarkeit
nicht entscheidbar und semi-entscheidbar
Erfüllbarkeitsproblem der Aussagenlogik (SAT)
Gegeben
- Endliche Folge von
nTupeln (Dominosteinen) $(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)$ mit $x_i, y_i \in \Sigma^+$ (Ohne 𝞮)
Gefragt
„Gibt es eine Belegung, so das F erfüllbar ist?“
Härte
SAT ∈ NP
Abschlusseigenschaften
Wenn $L_1$ und $L_2$ von Typ $n$. Ist dann auch $L_1 \text{op} L_2$ vom Typ $n$.
Vereinigung
$L_1 \cup L_2$
Typ 3: L|K
Schnitt
$L_1 \cap L_2 = C(C(L_1) \cup C(L_2))$
Typ 3: L|K
Komplement
$C(L) = \Sigma^* \setminus L$
Vertausche Endzustände mit nicht Endzuständen.
Produkt
Konkatenation
Typ 3: LK
Stern
Wiederholung
Typ 3: L*
Notationen
Grammatik
- Regelsystem
- Ausgehend von Startsymbol
- Ableiten/komplexer werden $u \Rightarrow_G v$
$G = (V, \Sigma, P, S)$
| FZ | Art | Heist | Besteht aus |
|---|---|---|---|
| $V$ | Menge | Variablen/nicht-Terminalsymbolen | |
| $\Sigma$ | Menge | Alphabet/Signatur | Konstanten / Terminalsymbolen |
| $P$ | Menge | Produktionsregeln | |
| $S$ | Element | Startsymbol | |
| $\epsilon$ | Element | leere Sequenz | |
$S \in \Sigma$
- Relation
$u \Rightarrow_G v$ - Reflexiv-transitive Relation
$S \Rightarrow_G^* w$
$L(G) = L$
- Es ist nicht vorgeschrieben, das von links ersetzt wird.
- Sind mehrere Ableitungen möglich ⇒ Nicht deterministisch
Mathematische Notation
Ist direkt menge und damit Sprache.
$L = \{a^nb^n | n > 0\}$
???
???
| $ab$ | Konkatination |
| $\{a,b\}$ | Auswahl |
| $a^n$ | $n$ Mal |
| $a^*$ | $0-\infty$ Mal |
| $a^+$ | $1-\infty$ Mal |
| $a?$ | $0-1$ Mal |
| $\epsilon$ | Leeres Wort |
(Extended) Backus-Naur-Form
Nur Typ 2 und 3
a|b | Auswahl |
[a] | $0-1$ Mal |
{a} | $0-\infty$ Mal |
Regulärer Ausdruck
Nur Typ 3
| $\emptyset$ | Leere Sprache (Menge) |
| $\epsilon$ | Leeres Wort (Element) |
| $a \in \Sigma$ | Konstante |
| $ab$ | Konkatination |
| $(a|b)$ | Auswahl |
| $(a)^*$ | $0-\infty$ Mal |
Entscheidungsverfahren
Parser
= Programm
Automaten
Nicht deterministisch ⇒ Backtracking
| Typ | Äquivalent |
|---|---|
| 3 | Ja |
| 2 | Nein |
| 1 | ? |
| 0 | Ja |
DFA
- DFA
Deterministic Finite Automaton - DEA
Deterministischer Endlicher Automat
$M = (Z, \Sigma, \delta, z_0,E)$
| FZ | Art | Heist | Besteht aus | Bedingung |
|---|---|---|---|---|
| $Z$ | Menge | Zuständen | $z_0 \in Z$ | |
| $\Sigma$ | Menge | Eingabealphabet | Konstanten / Terminalsymbolen | |
| $z_0$ | Element | Startzustand | $z_0 \in Z$ | |
| $E$ | Menge | Endzustände | $E \subseteq Z$ | |
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Sigma \rightarrow Z$ | total (überall Def.) | |
Konfiguration
Tupel $(z_i, v)$
- $z_i$
Zustand - $v$
Restwort
$(z_0, \text{foo}) \rightarrow (z_1, \text{oo}) \rightarrow (z_2, \text{o}) \rightarrow (z_2, \epsilon)$
NFA
- NFA
Nondeterministic Finite Automaton - NEA
Nichtdeterministischer Endlicher Automat
$M = (Z, \Sigma, \delta, S,E)$
| FZ | Art | Heist | Besteht aus | Bedingung |
|---|---|---|---|---|
| $Z$ | Menge | Zuständen | $z_0 \in Z$ | |
| $\Sigma$ | Menge | Eingabealphabet | Konstanten / Terminalsymbolen | |
| $S$ | Menge | Startzustände | $S \subseteq Z$ | |
| $E$ | Menge | Endzustände | $E \subseteq Z$ | |
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Sigma \rightarrow \mathcal P(Z)$ | total (überall Def.) | |
Konfiguration
Tupel (z, v)
- z: Zustand
- v: Restwort
$(z_0, \text{foo}) \rightarrow (z_1, \text{oo}) \rightarrow (z_2, \text{o}) \rightarrow (z_2, \epsilon)$
Kellerautomat
- Kellerautomat
- Push-Down Automaton (PDA)
$\epsilon$-Übergang ⇒ Nichtdeterministisch (es gibt aber auch weitere Fälle)
$M = (Z, \Sigma, \Gamma, \delta, z_0, \#)$
| FZ | Art | Heist | Besteht aus | Bedingung |
|---|---|---|---|---|
| $Z$ | Menge | Zuständen | $z_0 \in Z$ | |
| $\Sigma$ | Menge | Eingabealphabet | Konstanten / Terminalsymbolen | |
| $\Gamma$ | Menge | Kelleralphabet | $\# \in \Gamma$ Es kann $\Gamma \ne \Sigma$ gelten |
|
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Sigma \rightarrow \mathcal P(Z)$ | total (überall Def.) | |
| $z_0$ | Element | Startzustand | $z_0 \in Z$ | |
| # | Element | Unterstes Kellerelement | $\# \in \Gamma$ | |
(Keine Endzustände)
Start
Keller leer oder #.
Ende
Akzeptiert
- Restwort leer
- Keller leer
Nicht Akzeptiert
- sonst
Übergang
$(z, \sigma, S_1) \rightarrow (z', S_1'S_2'\ldots)$
| $(z, \sigma, S_1) \rightarrow (z', )$ | POP() |
| $(z, \sigma, S_1) \rightarrow (z', S_nS_1)$ | PUSH($S_n$) |
| $(z, \textbf{$\epsilon$}, S_1) \rightarrow (z', S_1'S_2'\ldots)$ | Restwort bleibt unverändert |
| $(z, \sigma, \textbf{$\epsilon$}) \rightarrow (z')$ | Restwort und Keller bleiben unverändert |
Vereinfacht
- $\sigma, S_1: \text{POP}()$
- $\sigma: \text{PUSH}(S_\text{neu})$ (Achtung: Top of Stack egal)
Konfiguration
Tupel (z, v, K)
- z: Zustand
- v: Restwort
- K: Kellerinhalt $(S_1, S_2, \ldots)$
$(z_0, \text{foo}, (\#)) \rightarrow (z_1, \text{oo}, (x\#)) \rightarrow (z_2, \text{o}, (\#)) \rightarrow (z_2, \epsilon, ())$
- $S_1$ = neustes Stackelement
Turingmaschiene
Deterministische TM ⇔ Nichtdeterministische TM
$M = (Z, \Sigma, \Gamma, \delta, z_0, \square, E)$
| FZ | Art | Heist | Besteht aus | Bedingung |
|---|---|---|---|---|
| $Z$ | Menge | Zuständen | $z_0 \in Z$ $E \subseteq Z$ |
|
| $\Sigma$ | Menge | Eingabealphabet | Konstanten / Terminalsymbolen | $\Sigma \subset \Gamma$ |
| $\Gamma$ | Menge | Arbeitsalphabet | $\square \in \Gamma$ $\Sigma \subset \Gamma$ |
|
| $\delta$ | Funktion | Überführungsfunktion $\delta: Z \times \Gamma \rightarrow Z \times \Gamma \times \{\text{L}, \text{R}, \text{N}\}$ (D) Überführungsfunktion $\delta: Z \times \Gamma \rightarrow \mathcal P(Z \times \Gamma \times \{\text{L}, \text{R}, \text{N}\})$ (ND) | total (überall Def.) | |
| $z_0$ | Element | Startzustand | $z_0 \in Z$ | |
| $\square$ | Element | Blank | $\square \in \Gamma$ | |
| E | Menge | Endzustände | $E \subseteq Z$ | |
Übergang
$(z, \sigma) \rightarrow (z', \sigma', m)$
Für m
- L Links
- N Neutral (stehen bleiben)
- R Rechts
Konfiguration
Tupel $(\alpha z \beta)$
- $\alpha$: Links vom Lesekopf
- z: Zustand
- $\beta$: Unterm und rechts vom Lesekopf
Linear beschränkt
Der Lesekopf liest noch nicht mal $\square$
- Zu keiner Zeit
- Bei jedem Startband
- Linken Rand kann man sich in Zustand merken oder selber markieren
- Rechter Rand wir mit zusätzlichem Zeichen markiert
| Eigentlicher Bandinhalt | $a_1a_2a_3a_4$ |
|---|---|
| Markierter Bandinhalt | $a_1a_2a_3a_4\hat a_4$ |