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