Komplexität Flashcards
1
Q
Deterministischer endlicher Automat
A
- für jeden Zustand + Eingabesymbol /Übergang höchstens ein möglicher Endzustand
- in vollständigem Automat genau ein möglicher Endzustand
2
Q
Zusammenfassung
A
- Endlischer Automat als Modell Computerprogramm
- Turing-Automat
- akzepiert kontextfreie Sprachen
- Probleme mit polynomialzeitbeschränkten Algorithmus –> Lösbar (für P und NP)
- Wortprobleme für machne Sprachen lösbar, für andere nicht
- Äquivalenzproblem nicht entscheidbar
