Mar 31, 2013 - Bits & Pieces der Informatik

Comments

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~$) \cup 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~$) \cap 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