Theoretische Informatik: Automaten, formale Sprachen, Berechenbarkeit
Der Bereich Theoretische Informatik prüft, wie man Sprachen formal beschreibt und welche Maschinen sie erkennen. Erwartet werden das Entwerfen und Minimieren endlicher Automaten, die Umwandlung zwischen regulären Ausdrücken, Grammatiken und Automaten, die Einordnung in die Chomsky-Hierarchie sowie Grundbegriffe der Berechenbarkeit wie Entscheidbarkeit und Halteproblem.
Endliche Automaten
- Ein deterministischer endlicher Automat (DEA) besteht aus Zustandsmenge, Eingabealphabet, Übergangsfunktion, Startzustand und Menge der Endzustände.
- Der DEA muss total determiniert sein: Für jedes Zeichen existiert in jedem Zustand genau ein Übergang, notfalls in einen „Fehlerzustand“.
- Ein NEA darf mehrere Übergänge oder Epsilon-Übergänge haben; jede NEA-Sprache ist auch DEA-erkennbar (Potenzmengenkonstruktion).
- Reguläre Sprachen sind genau die DEA-erkennbaren Sprachen, beschreibbar durch reguläre Ausdrücke und Typ-3-Grammatiken.
Höhere Stufen
- Kontextfreie Sprachen (Typ 2) werden von Kellerautomaten erkannt, etwa a^n b^n; kontextsensitive Sprachen (Typ 1) und allgemeine (Typ 0) brauchen Turingmaschinen.
- Das Pumping-Lemma für reguläre Sprachen ist eine notwendige Bedingung: Wer eine Zerlegung findet, hat nichts bewiesen, wer keine findet, hat Nichtregularität gezeigt.
- Entscheidbar heißt: Es gibt ein Verfahren, das für jede Eingabe in endlicher Zeit ja oder nein liefert. Das Halteproblem ist unentscheidbar.
Durchgerechnetes Beispiel
Gesucht ist ein DEA über {a, b} für alle Wörter mit gerader Anzahl von a. Zustand z0 steht für „gerade Anzahl“ und ist Start- und Endzustand, z1 für „ungerade“. Übergänge: δ(z0,a)=z1, δ(z0,b)=z0, δ(z1,a)=z0, δ(z1,b)=z1. Probe mit „aba“: z0 →a z1 →b z1 →a z0, Endzustand erreicht, also akzeptiert; das Wort enthält zwei a. Probe mit „ab“: z0 →a z1 →b z1, nicht akzeptiert, da ein a. Der Automat ist total, weil für beide Zeichen in beiden Zuständen ein Übergang definiert ist.
Typische Punktverluste
- Unvollständiger DEA: fehlende Übergänge werden als Nichtakzeptanz gewertet, obwohl die Definition verletzt ist.
- Startzustand und Endzustand verwechselt oder den Startzustand nicht als akzeptierend markiert, wenn das leere Wort zur Sprache gehört.
- Das Pumping-Lemma als hinreichendes Kriterium missverstanden.
- Reguläre Grammatik mit kontextfreier Grammatik verwechselt: Typ 3 erlaubt nur A → aB oder A → a.