FoSy Sätze

Question 1

Satz Myhill & Nerode

Answer 1

Eine Sprache ist regulär genau dann wenn sie endliche viele Äquivalenzklassen bzgl. der Nerode-Rechtskongruenz hat

Question 2

Pumping-Lemma für reguläre Sprachen

Answer 2

Für jede reguläre Sprache gibt es eine Zahl n (die größer gleich null ist) so dass gilt:
für jedes Wort z (Teil der Sprache, mit z größer gleich n) gibt es eine Zerlegung z=uvw (mit v größer gleich eins, uv kleiner gleich n) so dass:
für jede Zahl k größer null gilt: uv^kw Element der Sprache

Question 3

Pumping-Lemma für kontextfreie Sprachen

Answer 3

Für jede kontextfreie Sprache L gibt es eine Zahl n (größer gleich 0, so dass gilt: für jedes Wort z (Element der Sprache, z größer gleich n) gibt es eine Zerlegung z=uvwxy ( vx größer gleich 1, vwx kleiner gleich n), so dass: für jede Zahl k (größer gleich 0) gilt: uv^kwx^ky ist immer noch Element der Sprache

Question 4

Church-Turing-These

Answer 4

Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein

Question 5

Satz von Rice

Answer 5

Jede nicht triviale Frage ( weder wahr noch falsch für alle Programme) über die von einer Turingmaschine ausgeführten Berechnungen ist unentscheidbar

Question 6

Ersetzungstheorem

Answer 6

wenn eine Teilformel, durch etwas ersetzt wird, was äquivalent ist, dann bleibt die Gesamtformel gleich

Question 7

Satz von Cook und Levin

Answer 7

Alle Probleme in NP können in polynomieller Zeit auf SAT reduziert werden