Theoretische Informatik:Zusammenfassung

Aus II-Wiki
Wechseln zu: Navigation, Suche

Hier auf mehrere Anfrage eine kleine Alternativversion, die aber auch noch ausbaufähig ist...

  • zu jedem nichtdeterministischen endl. Automaten gibt es einen äquivalenten deterministischen endl. Automaten

Sprachen

  • bei den Grammatiken verstehen sich die Kleinbuchstaben als beliebig viele Elemente des Alphabets (sofern es aus dem Kontext nicht anders hervorgeht) und Großbuchstaben als mögliche Variablen
  • rekursiv aufzählbar/allgemein:
    • Sprache vom Typ 0
    • ist die Klasse der von Touringmaschienen erkennbaren Sprachen
    • Vereinigung rekursiv aufzählbarer Sprachen ist auch rekursiv aufzählbar
    • zugehörige Grammatik:
      • naja allgemeine Grammatik halt
  • kontextsensitiv
    • Sprache vom Typ 1
    • zug. Grammatik (bzw. aussehen der Produktionen):
      • um Variable muss Kontext stehen, der erhalten bleibt
      • z.B.: P:(aVb,afoob), (aV,afoo), (Vb, fooCb)
  • kontextfrei:
    • Sprache vom Typ 2
    • ist identisch mit der Klasse der von nichtdeterministischen Kellerautomaten akzeptierbaren Sprachen
    • zug. Grammatik:
      • Produktionen müssen immer so aussehen, dass eine Variable durch eine andere Variable oder ein Element des Alphabets ersetzt wird (oder kombinationen daraus)
      • also quasi kontextsensitive Grammatik, nur das zwangsweise kein kontext um Variable stehen darf
      • z.B.: (V,a), (A,foo), (B,aV)
  • regulär:
    • Typ 3
    • Durch regulären Ausdruck erzeugbar
    • ist identisch mit der Menge der durch endl. Automaten akzeptierbaren Sprachen
    • jede Reguläre Sprache "besitzt" einen det. Kellerautomaten, der sie erkennt (aber nicht jeder DPDA repräsentiert reg. Sprache)
    • alle endlichen Sprachen sind auch regulär
    • zug. Grammatik:
      • zwei Möglichkeiten entweder rechtslinear oder linkslineare
      • rechtslinear: (V,aV) oder (V,)
      • linkslinear: (V,Va) oder (V,)
  • entscheidbar:
    • wenn L und semientscheidbar sind
  • rekursiv:
    • echte Teilmenge von rekursiv aufzählbaren Sprachen
    • falls sie von einer Touringmaschine erkannt wird, die auf jeder Eingabe hält
    • Wenn L und r.a. dann sind beide zusätzlich rekursiv
    • wenn L oder r.a., die andere aber nicht, ist keine von beiden rekursiv
    • L ist rekursiv, wenn sie entscheidbar ist
    • Vereinigung rekursiver Sprachen ist auch rekursiv