2. Vorlesung Theoretische Informatik (TI) | Endliche Automaten

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

1. 1:09 Eine formale Sprache \(L\) ist eine Teilmenge von \(\Sigma^*\), also der Menge aller endlichen Wörter über dem Alphabet \(\Sigma\). Das Wortproblem fragt, ob ein gegebenes Wort \(P\) in \(L\) enthalten ist.
2. 2:59 Bei allgemein beschriebenen Sprachen wie gültigen Bankleitzahlen kann man nicht alle Wörter einzeln auflisten. Man braucht daher eine allgemeine Charakterisierung und eine mechanische Methode, die Zugehörigkeit eines Wortes zu prüfen.
3. 11:05 Eine automatische Tür lässt sich als Automat mit zwei Zuständen modellieren: geschlossen und offen. Sensorwerte lösen Übergänge zwischen diesen Zuständen aus, etwa das Öffnen bei einer Person vorne und das Schließen bei freien Sensoren.
4. 14:25 Für die Türsteuerung gibt es vier mögliche Sensorkombinationen und zwei Türzustände, also acht Situationen. Eine vollständig ausgefüllte Tabelle stellt sicher, dass jeder mögliche Eingabefall eindeutig behandelt wird und kein undefinierter Zustand entsteht.
5. 19:09 Ein Automat kann sowohl als Tabelle als auch als gerichteter, beschrifteter Graph dargestellt werden. Beide Darstellungen enthalten dieselbe Übergangsinformation; der Graph ist anschaulicher, während sich die Tabelle leichter in ein Computersystem übertragen lässt.
6. 21:32 Der Startpfeil legt fest, in welchem Zustand der Automat beginnt. Danach verarbeitet er fortlaufend Eingaben und läuft aus Sicht der Steuerungslogik beliebig lange weiter, sodass er bereits ein einfaches Berechnungsmodell darstellt.
7. 24:34 Endliche Automaten werden unter anderem zur industriellen Steuerung eingesetzt; spezielle Steuerungssprachen bilden dabei im Wesentlichen komfortablere Oberflächen für solche Automaten. Auch Netzwerkprotokolle wie TCP beschreiben den Ablauf zwischen Client und Server durch Zustände und Übergänge.
8. 29:46 Automaten können Zustandsübergänge steuern, Eingaben in andere Ausgaben übersetzen oder Sprachen erkennen. In dieser Vorlesung steht besonders die Spracherkennung und damit die automatisierte Lösung des Wortproblems im Mittelpunkt.
9. 32:33 Ein endlicher Automat liest ein endliches Wort auf einem Band Zeichen für Zeichen. Abhängig vom aktuellen Zustand und dem gelesenen Zeichen führt er jeweils einen eindeutig festgelegten Zustandsübergang aus.
10. 38:25 Ein doppelt markierter Zustand ist ein akzeptierender Endzustand. Nach dem Lesen des gesamten Wortes wird es akzeptiert, wenn der Automat in einem solchen Zustand endet, und andernfalls abgelehnt.
11. 48:58 Der vorgestellte Automat erkennt genau die Wörter, die mindestens eine Eins enthalten und entweder mit einer Eins oder mit einer geraden Anzahl von Nullen enden. Diese Bedingung ergibt sich aus den möglichen Wegen vom Startzustand zu einem akzeptierenden Endzustand.
12. 51:38 Ein einzelnes Wort wird von einem Automaten akzeptiert oder abgelehnt. Die erkannte Sprache ist dagegen die Menge aller Wörter, die dieser Automat akzeptiert.
13. 54:19 „Endlich“ bedeutet, dass der Automat nur endlich viele Zustände besitzt, nicht dass die Eingabewörter eine begrenzte Länge haben. „Deterministisch“ bedeutet, dass für jeden Zustand und jedes Eingabesymbol genau ein nächster Zustand festgelegt ist.
14. 1:00:00 Ein deterministischer endlicher Automat wird als fünftes Tupel \( (Q,\Sigma,\Delta,q_0,F) \) beschrieben: Zustandsmenge \(Q\), Alphabet \(\Sigma\), Übergangsfunktion \(\Delta\), Startzustand \(q_0\) und Menge der akzeptierenden Zustände \(F\).
15. 1:09:50 Die Übergangsfunktion kann als Tabelle angegeben werden, in der für jedes Zustand-Symbol-Paar genau ein Zielzustand steht. Alternativ beschreibt man sie durch Funktionsgleichungen wie \(\Delta(q_1,0)=q_1\); regelmäßige Fälle lassen sich damit kompakt zusammenfassen.
16. 1:25:27 Für die Sprache aller Binärwörter, die mit \(1\) beginnen und mit \(0\) enden, konstruiert man Zustände, die genau diese Information speichern. Ein Fangzustand nimmt Wörter auf, die etwa mit \(0\) beginnen und deshalb nicht mehr gültig werden können.
17. 1:41:39 Die Sprache aus einer positiven Anzahl von Wiederholungen des Blocks „ab“ lässt sich trotz unendlich vieler Wörter mit endlich vielen Zuständen erkennen. Ein Zyklus für „ab“ erlaubt beliebig viele Wiederholungen; Fangzustände verwerfen falsche Reihenfolgen.
18. 1:52:03 Ob das leere Wort akzeptiert wird, hängt von der Konstruktion des Automaten ab: Ein Startzustand, der zugleich akzeptierend ist, akzeptiert es, ein nicht akzeptierender Startzustand nicht. Für eine Sprache sind daher sowohl akzeptierte als auch abgelehnte Wörter entscheidend.
19. 1:55:53 Bei einem Wort mit \(n\) Zeichen durchläuft der Automat eine Zustandsfolge \(R_0,\ldots,R_n\), also \(n+1\) Zustände. Formal gilt \(R_0=q_0\), \(R_{i+1}=\Delta(R_i,w_{i+1})\), und das Wort wird genau dann akzeptiert, wenn \(R_n\in F\) liegt.
20. 2:09:20 Die Dynamik eines endlichen Automaten lässt sich als Programm simulieren, weil seine Zustände und Übergänge mathematisch eindeutig definiert sind. Programmiersprachen können solche Automaten nachbilden, während ein endlicher Automat umgekehrt keine beliebige Programmiersprache simulieren kann.
21. 2:11:14 Für ein allgemeineres Rechnermodell reichen zwei wesentliche Erweiterungen: Das Band muss in beide Richtungen bewegt werden können, und die Maschine muss Zeichen schreiben dürfen. Diese Erweiterungen führen vom einfachen Automatenmodell zu einem vollständigen Rechnermodell.

Zum Nachlesen