Theoretische Informatik:Zusammenfassung

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,$\epsilon$)
    • linkslinear: (V,Va) oder (V,$\epsilon$)

• entscheidbar:
  • wenn L und ${\overline {L}}$ 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 ${\overline {L}}$ r.a. dann sind beide zusätzlich rekursiv
  • wenn L oder ${\overline {L}}$ r.a., die andere aber nicht, ist keine von beiden rekursiv
  • L ist rekursiv, wenn sie entscheidbar ist
  • Vereinigung rekursiver Sprachen ist auch rekursiv