Endliche Automaten = Reguläre Ausdrücke

Zwei völlig unterschiedliche Methoden, formale Sprachen (d.h. Mengen von Strings) zu definieren, stellen sich als gleich mächtig heraus: Endliche Automaten (egal ob deterministisch oder nicht) und reguläre Ausdrücke. Das wird in diesem Video bewiesen. Wir zeigen: Jeder reguläre Ausdruck kann in einen endlichen Automaten verwandelt werden und umgekehrt jeder endliche Automat in einen regulären Ausdruck.
0:00 Übersicht
4:28 reguläre Ausdrücke
7:02 strukturelle Induktion
10:12 RegExp zu Automat
23:48 Automat zu RegExp
36:36 Fazit