Kapitel 9 Flashcards
(8 cards)
Was ist ein endlicher Automat?
Ein Programm
Was ist eine endliche Maschine?
Endlicher Automat + Ausgabe
- -> kann nur durch endliche Automaten simuliert werden
- -> transformieren Eingabewörter von Automat in Ausgabewörter
Was ist ein determistischer endlicher Automat?
Für jeden Zustand und Eingabesymbol / Übergang gibt es höchstens einen möglichen Endzustand (im vollständigen Automaten nur genau einen)
Was ist eine Turing-Maschine?
matematisches Modell eines Computers, zerlegt Berechnungen in kleinste Operatoren
[Operationen: Lesen, Schreiben, Band verschieben und Merken (Speichern)]
Was ist ein Kellerautomat?
endliches Gedächtnis, also ein endlicher Automat mit Speicher (LIFO-Prinzip)
Erklären Sie die Aufzählbarkeit in Verbindung mit der Turing Maschine
Mengen der Elemente die durch die Turing Maschine gezählt weredn können
Erklären Sie Entscheidbarkeit
für jedes beliebige Wort kann entschieden werden ob es Teil der Menge ist oder nicht (Spracherkennung)
Was ist die Komplexitätstheorie?
Aussagen über Aufwand algorithmischer Prozesse auf einer Maschine
