frosch03.de/posts/2013-03-31-Info3

Bits & Pieces von Innen

ein DFA besitzt nicht unbedingt mehr Zustände als ein NFA
zwei Turingmaschienen M_{1} $\land$ M_{2} werden schritt für schritt auf $x$ angewandt, M_{3} akzeptiert nur dann, wenn M_{1} $\lor$ M_{2} akzeptieren; M_{3} erkennt genau die Sprache $T($M_{1}$) ∪ T($M_{2}$)$
deterministische Kellerautomaten erkennen weniger Sprachen wie nichtdeterministische
durch eine Polynomzeit-Reduktion kann man Laufzeitabschätzungen, enthaltensein in P oder NP-härte zeigen; nicht jedoch direkt die Endlichkeit einer Sprache
a^{n} b^{n}, $n \geq 1$ ist nicht regulär
die Menge der Wörter auf die eine Turingmaschiene angesetzt hält, ist rekursiv aufzählbar
falsch ist: LOOP-Programme sind genauso mächtig wie WHILE-Programme
gegeben: eine Turingmaschiene $M$ mit $\Sigma$, so ist entscheidbar ob $T(M) \subseteq \Sigma^*$ (die Sprache welche die Turingmaschiene erkennt eine Teilmenge von $\Sigma^*$ ist
bei Kellerautomaten unterscheidet sich die Menge der erkannte Sprachen zwischen den deterministischen und den nichtdeterministischen.
der Schnitt $\cap$ einer regulären Sprache mit einer kontextfreien, ist selber wieder kontextfrei (Typ3-Sprache $\cap$ Typ2-Sprache ist eine Typ2-Sprache)
nicht jede Turingberechenbare Funktion ist LOOP berechenbar
eine endliche Menge ist immer entscheidbar
das spezielle Halteproblem ist die Menge der Kodierungen, die halten, wenn sie ihre eigene Kodierungen als Eingabe erhalten
eine Sprache die von einem deterministischen Kellerautomaten erkannt wird, muss nicht von einem nichtdeterministischen Kellerautomaten erkannt werden
zwei Turingmaschienen M_{1} $\land$ M_{2} werden schritt für schritt auf $x$ angewandt; M_{3} akzeptiert nur, wenn M_{1} $\land$ M_{2} akzeptieren; M_{3} erkennt genau die Sprache $T($M_{1}$) ∩ T($M_{2}$)$
der Satz von Myhill-Nerode ist ein Hilfsmittel, um zu zeigen, dass eine Sprache regulär ist; nicht jedoch das Pumping-Lemma
fügt man zu einem NFA/DFA einen Übergang hinzu, so erkennt der neue NFA/DFA eine Obermenge der vom alten NFA/DFA erkennten Sprache
das Pumping-Lemma für Typ2-Sprachen kann begründet werden dadurch, dass eine Typ2-Grammatik endlich viele Variablen besitzt und bei Grammatiken in Chomsky-Normal-Form bei langen Wörtern mehr Ableitungsschritte als Variablen nötig sind
die Konfiguration eines Kellerautomaten enthält Informationen zu: Zustand, Eingabe und Keller (Kellerautomaten-Konfiguration: $k \in Z \times \Sigma^* \times \Gamma^*$
eine Sprache ist vom Typ1, wenn es eine Typ1-Grammatik gibt, mit: $L(G) = L$
es ist entscheidbar, ob die von einer Turingmaschiene erkannte Sprache semi-entscheidbar ist
eine reguläre Sprache ist auch immer vom Typ0
die Vereinigung zweier deterministischer kontextfreier Sprachen ist nicht deterministisch kontextfrei
die leere Sprache enthält kein Wort
$A \leq B \land$ $A$ unentscheidbar $\rightarrow$ $B$ unentscheidbar
formal ist das Halteproblem eine Sprache
der CYK-Algorithmus findet für Teilwörter $x$ von $w$ die Variablen, die nach $* x$ abbilden
das Pumping-Lemma für Typ3-Sprachen begründet sich daraus, dass ein DFA endlich viele Zustände besitzt und keine Information darüber, wie oft er einen Zustand schon durchlaufen hat

Bits & Pieces von Aussen

die Ackermanfunktion ist eine Beispiel für eine totale, berechenbare Funktion, die aber nicht LOOP-Berechenbar ist
Typ2-Sprachen mit einelementigem Alphabet, $|\Sigma| = 1$, sind regulär
$A \leq B$ heißt: $A$ ist auf $B$ reduzierbar