Automatentheorie
- Turingreduktion
- Satz Halteproblem für Turingmaschinen ist unentscheidbar
- Universale Sprache
- Erkannte Sprache einer TM
- Allgemeines Wortproblem für Turingmaschinen
- Satz epsilon-Halteproblem für Turingmaschinen ist unentscheidbar
- epsilon-Halteproblem für Turingmaschinen
- Halteproblem für Turingmaschinen
- Satz Jede reguläre Sprache wird von DKA erkannt
- Erweiterte Folgekonfiguration eines Kellerautomaten
- Durch leeren Keller erkannte Sprache eines NDKA
- Durch Endzustand erkannte Sprache eines NDKA
- Deterministischer Kellerautomat
- Satz Umwandlung NDKA in äquivalenter KFG
- Satz Umwandlung KFG in äquivalenter NDKA
- Nichtdeterministischer Kellerautomat
- Satz durch Endzustand und durch leeren Keller erkannt ist äquivalent
- Satz NDKA von Endzustand zu äquivalenten leeren Kelller
- Satz NDKA von leeren Keller zu äquivalenten Endzustand
- Satz NDKA erkennt w-w-reversed
- Berechnung eines NDKA
- Erkannte Sprache
- Erkannte Sprache eines NDKA
- Akzeptiertes Wort
- Satz ungelese Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht
- Folgekonfiguration eines Kellerautomaten
- Konfiguration eines Kellerautomaten
- Sprache Palindrom
- Satz Jede reguläre Sprache ist auch kontextfrei
- Minimaler DEA
- Satz NEA zu regulärer Ausdruck
- Zustand aus einem GNEA entfernen
- Berechnung eines GNEA
- Berechnung eines NEA
- Generalisierter nichtdeterministischer endlicher Automat
- Nichtdeterministischer endlicher Automat
- Satz Kleene Hülle eines NEAs
- Satz Konkatenation zweier NEAs
- Satz Vereinigung zweier NEAs
- Universelle Turingmaschine
- Kodierung einer TM
- Satz Regulärer Ausdruck zu NEA
- Satz DEA zu NEA
- Satz Korrektheit Potenzmengenkonstruktion ohne epsilon-Kanten
- epsilon-Eliminierung
- epsilon-Pfad
- Epsilon-Kante
- Potenzmengenkonstruktion
- w-Pfad
- epsilon-Hülle
- Satz reverse ist nicht sequentiell
- Satz raise ist nicht sequentiell
- Erkannte Sprache eines DEA
- Berechnung eines DEA
- Endlicher Automat
- Berechnung
- Berechnung einer TM
- Deterministischer endlicher Automat
- Satz Anzahl der Konfigurationen eines LBTM
- Satz Redundanz zusätzlicher Bänder
- Orakel-Turingmaschine
- Orakel
- Nur-Lesen Eingabeband Turingmaschine
- log space transducer
- Satz Anzahl der Konfiguration einer ROITM
- Satz Anzahl der Konfiguration einer TM
- Verstärkungslemma
- Satz Laufzeit zusätzlicher Bänder
- Äquivalenz DEA, NEA und Reg
- Mehrband-Turingmaschine
- Deterministische Turingmaschine
- Sequenzielle Maschine
- Satz Redundanz von Nichtdeterminismus
- Probabilistische Turingmaschine
- Linear beschränkte Turingmaschine
- Äquivalente Automaten