---
tags: uni-theoInf
---
# Theoretische Informatik

# Endterm preparation

- Stoff
- HS 18
- A1:
- DEA zeichnen mit Zustandsklassen (10P)
- A2:
- Nichtregularitätsbeweis mit Kolmogorov (5P)
- kontextfreie Grammatik (5P)
- Beweis DEA Mindestanzahl Zustände (5P)
- A3:
- Pumpinglemma für kontextfreie Sprachen (2P)
- Beweis mit PL für kontextfreie Sprachen (4P)
- Grammatik entwerfen (4P)
- A4:
- EE Reduktion (3P)
- EE Reduktion (5P)
- Zeigen, dass Sprache $\notin L_R$ (5P)
- R Reduktion kurze Begründung (2P)
- A5:
- Zeigen, dass Problem $\in NP$ (2P)
- Polynomzeitreduktion (8P)
- HS 17
- A1:
- DEA zeichnen mit Zustandsklassen (10P)
- A2:
- Lemma 3.3, Pumping-Lemma oder Kolmogorov-Komplexit (5P)
- Zeigen, dass jeder deterministische Automat x Zustände hat. (5P)
- A3:
- Kontext freie Sprache entwerfen und informell beschreiben. (3P)
- Pumping Lemma für kontextfreie Sprachen formulieren (2P)
- Verwenden des Pumping Lemma für kontextfreie Sprachen und zeigen, dass Sprache nicht kontextfrei ist. (5P)
- A4:
- Zeigen, dass Sprache $\notin L_R$ (2P)
- R Reduktion (4P)
- Zeigen, dass Sprache $\in L_{RE}$
- A5:
- Polynomzeit-Reduktion vom Vertex-Cover-Problem VC auf DS (4P)
- Reduktion anwenden (2P)
- Korrektheit zeigen (4P)
- A6:
- Random NSPACE(s(n)) $\subseteq$ TIME($c^{s(n)}$)

- HS 16
- A1:
- DEA zeichnen mit Zustandsklassen (10P)
- A2:
- Nichtregularitätsbeweis mit Kolmogorov (5P)
- Beweis DEA Mindestanzahl Zustände (5P)
- A3:
- Grammatik entwerfen (4P)
- Pumpinglemma für kontextfreie Sprachen (2P)
- Beweis mit PL für kontextfreie Sprachen (4P)
- A4:
- Kolmogorov Komplexität obere Schranke angeben (4P)
- Beweis, dass $|f(w)| \geq |w|$ (6P)
- A5:
- R Reduktion (4P)
- EE Reduktion (6P)
- A6:
- NTIME(s(n)) $\subseteq$ SPACE($s(n)$)
- HS 15
- A1:
- DEA zeichnen mit Zustandsklassen (10P)
- Bonus: Anzahl Zustände eines minimalen EA für Sprache bestimmen und zeigen, dass dieser mindestens soviele Zustände haben muss. (5P)
- A2:
- Zeigen, dass Sprache nicht regulär ist (5P)
- Zeigen, dass Sprache nicht regulär ist (5P)
- A3:
- Grammatik entwerfen (4P)
- Verwenden des Pumpinglemmas für kontextfreie Sprache um zu zeigen das Sprache nicht kontextfrei ist.
- A4:
- Geben Sie eine steigende unendliche Folge naturlicher Zahlen an, so dass bei der Fakbtorisierung aller dieser Zahlen insgesamt nur endlich viele Primfaktoren vorkommen. (1P)
- Zeigen Sie, dass bei der Faktorisierung aller Zahlen n_i insgesamt unendlich viele Primfaktoren vorkommen. (Nochmals anschauen)
- A5:
- Formale Definiton für Sprachen $L_{diag}$, und $(L_{empty})^c$ (2P)
- konkrete Reduktion (8P)
- A6:
- 5SAT nach E3SAT, korrektheit zeigen (10P)

Auswändig können:
- Nichtregularitäts Beweise
- Pumping Lemma
- Lemma 3.3
- Kolmogorov
- Reduktionsschemen, Beweisrahmen
- Definitionen aller Sprachen
- Komplexitätsklassen
- Sprachen in L_R, L_RE

L1 R Reduktion L2, ist L2 in LR $\Rightarrow$ L1 in LR

Sprachen in L_RE, LH, LU, L_empty_c, L_diag_c aber nicht L_R
Sprachen nicht in L_RE, L_empty, L_H_c, L_U_c, L_diag

Zum zeigen, dass Sprache L1 nicht in L_R ist, man muss eine Reduktion auf L1 zeigen. (also rechts L1)

Zum zeigen, dass Spache L1 in L_RE ist, muss man eine nichtdetermistische TM M beschreiben dann L(M)=L1.

Zum zeigen, dass Sprache nicht in L_RE ist, kann man die Hilfsaussage verwenden, "Sei L eine Sprache über den dem Alphabet $\Sigma$, falls $L \in L_{RE}$ und $L^c \in L_{RE}$ dann gilt $L \in L_R$.

## Grammatiken

Typ-0-Grammatik, man kann machen was man will.
Typ-1 ka
Typ-2, kontextfrei, links darf nur ein X stehen, aber rechts whatever
Typ-3, regulär, auf der rechten Seite darf X nur rechts stehen, und links nur ein Nichtterminales

### Zeigen, das Auotmat minimale Anzahl Zustände hat

Wir verwenden Lemma 3.3 aus dem Buch, um zu zeigen, dass jeder deterministische EA, der L akzeptiert, mindestens x Zusẗande haben muss. Hier f ur betrachten wir die folgenden Wörter und zeigen, dass $w_iz_{i,j} \in L$ und $w_jz_{i,j} \notin L$. Damit folgt dann aus Lemma 3.3, dass w_i und w_j jeden EA fur L in verschiedene Zustande fuhren mussen.

### Kolmogorov nicht Regularität zeigen

f(n+1) - f(n) > f(n) - f(n-1 )

---

Fragen:

Blatt 7, 20b), wie kommt man auf |y|? Warum darf man dies so sagen?

Damit ein Problem $\in NP$ braucht es:
- ein Zertifikat (die Lösung des Problems)
- ein schneller verifikations Algorithmus (schaut das Zertifikat an)

Wenn keine Lösung vorhanden ist, kann man kein Zertifikat ausstellen.

## Reduktionen

$L_U, L_H, (L_{diag})^c, (L_{empty})^c \in \mathcal{L}_{RE} \notin \mathcal{L}_{R}$

In der theoretischen Informatik heißt eine formale Sprache $L$ über einem Alphabet $\Sigma$ **rekursiv (entscheidbar)**, wenn eine Turingmaschine M existiert, die auf allen Eingaben $w\in \Sigma ^{*}$ **hält und jede Eingabe $w\in \Sigma ^{*}$ genau dann akzeptiert, wenn $w\in L$ ist**. Der Unterschied zu den **rekursiv aufzählbaren Sprachen** ist definitionsgemäß, dass eine Turingmaschine für eine rekursive Sprache immer halten muss, während eine für eine rekursiv aufzählbare Sprache **nur halten muss, wenn das Wort in der Sprache liegt**.

## General Information

Dieses File ist eine List vom Behandelten Stoff

https://courses.ite.inf.ethz.ch/theoInf19/

Wenn 50% der Punkte der Übungen erreicht, dann darf man Midterms schreiben. 2 Stück. Die 2 Midterms können als Note angerechnet werden.

Freitag Übungsblatt auf Webseite. Nächsten Freitag in Vorlesung abgeben. Erste Woche keine Übungen.

Die Geschichte der Informatik nicht prüfungsreleEvant bzw. die ersten Slides.

Git Zusammenfassung https://github.com/groggi/eth-ti-zf

## Kapitel 2.2

### Alphabet

Eine endliche Menge voneinander unterscheidbarer Symbole. Wort über ein Alphabet. Wörter sind endliche Folgen aus den Symbolen aus dem Alphabet.

Symbol == Zeichen == Buchstaben

**Konkatenation** ist assoziativ, ist monorid ?, gen. Regeln können

Teilworte, Präfix (Teilwort am Anfang), Suffix (Teilwort am Ende). Lambda is always a prefix of any word. Lambda is an empty word.
Menge ist Teilmenge von sich selbst, echte Teilmengen nicht.

Kanonische Ordnung von Wörtern über ein Alphabet Sigma* sagt aus, dass die Buchstaben von Wörter bei gleicher Länge durchnummeriert werden.

Aus Sprache bezeichnen wir jede Teilmenge von Sigma*, wir erlauben auch den Begriff leere Sprache, also leere Menge oder nur das leere Wort beeinhaltet. Komplement der Sprache von L bezeichnen

Wenn man zwei Sprachen kombiniert, ist es wie das kartesische Produkt. Unterschied zum kartesischen Produkt ist, dass man keine Paare bekommt. Und es kann passieren, dass die Menge schrumpft weil man durch Konkatenation 2 mal das selbe erhält.

Bei Beweisen transformiert in die Ebene der Logik und dann wider in die ursprüngliche Darstellung zurück.

Wenn ein Stern ist, dann steht auch Lambda (leeres Wort) drin. Wenn ein + dann ohne Lambda.

Stern bedeutet Vereinigung über alle Potenzen.

**Kolmogorov**

Kolmogorov complexity K(x) doesn't apply to programs, it applies to a string x. More specifically, the Kolmogorov complexity of a string x is the minimum program length needed to compute a particular string x.

## Übung 2

## Aus der Übung

**Kolmogorov Komplexität**

Wörter aus $\{0,1\}^*$

Def: Die Länge des kürzesten Pascal Programmes das $x^{\in\{0,1\}^*}$ generiert. Jedes Programm ist ein Binärstring.

Programm hat nur eine Ausgabe.
Programm hat keinen Input.

Obere Schranke: Programm aufschreiben.

Untere Schranke: Sagt es gibt kein Programm das kürzer ist.
- Zählen wie viele Wörter man hat
- Zählen wie viele Programme der Länge xy es gibt
- Summenzeichen 2^i = 2^(k+1)-2

Beispiel:
Zu beweisen: Für mindestens die Hälfte der Wörter x aus {0,1}^* mit der Länge kleiner als n gilt K(x) grösser als n-1

Zuerst die Grundlagen aufschreiben. Was ist die Kolgmorov Komplexität. Def KK,Ein Programm geniert nur ein Wort. Jedes Programm ist ein Binärstring und wir zählen Binärstrings.

Beweis: Wir zählen alle Programme ohne leeres Programm der Länge kleiner oder gleich n-2: Summenzeichen i bis n-2, 2^i = 2^(n-1)-2 daraus folgt das alle anderen Programme eine grössere Kolmogorov Komplexität haben.

Anzahl Wörter mit Länge kleiner als n = summenzeichen i = 0 bis n, 2^i = 2^(n+1)-1

Also gibt es 2^(n+1)-1-2^(n-1)+2=3* 2^(n-1)+1

Ist das mind. die Hälfte.

Man zählt wie viele Wörter können eine tiefe Kolmogorov Kompläxität haben und wie viele hat es und man zieht das eine vom anderen ab.

Kolmogorov Komplexität ist definiert durck ()

## Learn Strategy

- [ ] Do current exercises | each week
- [ ] Do exercises from last year | each week
- [ ] Check well for missed steps in solution and train the kind it is written

Aufgaben nicht verstanden: Midterm 18, Ex 4.