Automata, formal languages and computability
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.
- In der hier verwendeten totalen DEA-Definition gibt es für jedes Zustands-Zeichen-Paar genau einen Übergang. Bei einer partiellen Konvention bedeuten fehlende Übergänge Verwerfen; ein zusätzlicher Fehlerzustand liefert einen äquivalenten totalen Automaten.
- 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) werden durch linear beschränkte Automaten erkannt. Allgemeine Typ 0-Sprachen sind Turing-erkennbar; ein Erkenner muss bei Wörtern außerhalb der Sprache nicht immer halten.
- Das Pumping-Lemma für reguläre Sprachen ist eine notwendige Bedingung: Zum Nachweis der Nichtregularität muss für jede mögliche Pumping-Länge ein geeignetes Wort gewählt und für jede zulässige Zerlegung ein Pumpfaktor mit einem Wort außerhalb der Sprache gezeigt werden. Eine nicht gefundene Zerlegung ist für sich kein Beweis.
- 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 z 0 steht für „gerade Anzahl“ und ist Start- und Endzustand, z 1 für „ungerade“. Übergänge: δ(z 0,a)=z 1, δ(z 0,b)=z 0, δ(z 1,a)=z 0, δ(z 1,b)=z 1. Probe mit „aba“: z 0 →a z 1 →b z 1 →a z 0, Endzustand erreicht, also akzeptiert; das Wort enthält zwei a. Probe mit „ab“: z 0 →a z 1 →b z 1, nicht akzeptiert, da ein a. Der Automat ist total, weil für beide Zeichen in beiden Zuständen ein Übergang definiert ist.
Typische Punktverluste
- Die verwendete Automatenkonvention nicht nennen: totale DEA benötigen alle Übergänge, partielle DEA können fehlende Übergänge als Verwerfen behandeln.
- 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: Bei der hier betrachteten rechtslinearen Form sind etwa A → aB und A → a erlaubt; passende Epsilonregeln und Konventionsdetails müssen ausdrücklich berücksichtigt werden.