Mitschrieb Informatik 3 Vorlesung

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