Grenzen regulärer Sprachen

Formalen Sprachen (d.h. Mengen von Strings), für die es einen endlichen Automaten gibt, der sie akzeptiert, werden "regulär" genannt. Eine äquivalente Definition: Sprachen sind regulär, wenn sie von einem regulären Ausdruck beschrieben werden können. Allerdings sind nicht alle sprachen regulär. Der Grund: endliche Automaten haben ein begrenztes Gedächtnis, das niemals länger sein kann, als die Anzahl unterschiedlicher Zustände, über die der Automat verfügt. Akzeptiert ein Automat längere Strings, so kann man diese Strings "aufpumpen", d.h. einzelne Teilstrings beliebig oft wiederholen, ohne dass der Automat das merkt. Dieses Prinzip lässt sich als das "Pumping Lemma" formulieren, mit dessen Hilfe man zu diversen Sprachen beweisen kann, dass sie nicht regulär sind.

0:00 Start
0:33 nicht alle Sprachen sind regulär!
7:08 Pumping Lemma
12:53 Beispiel
17:07 Zyklen in Automaten
19:24 die Intuition hinter dem Pumping Lemma
20:41 Beispiele für nicht-reguläre Sprachen
24:55 Ausblick