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

[@inesdhawedi4581]

vielen Dank🙏

[@SmokingSoni]

5:14 kann mann nicht ein a machen das auf sich selbst zeigt im startzustand und von da aus auf den endzustand geht mit o und der endzustand zeigt auf sich selbst mit o - das wär auch noch ein dea - der automat würde halt nicht nur A^nO^n akzeptieren sondern mehr und weniger aber auch a^nO^n weil man a beispielsweise für n= 3 3 mal ein "a" produzieren kann dann ein "o" produziere indem ich vom startübergang auf den zweiten zustand gehe welcher ein endzustand wäre und dort die möglichkeit habe zwei mal ein "o" zu produzieren sodass ich insgesamt aaaooo habe - ich glaub ich hab etwas falsch verstanden vielleicht liegt es dran dass deas nur endliche strings akzeptieren aber ist n nicht endlich groß? ich hab irgendwas falsch verstanden

[@SmokingSoni]

ah das ist ja eigentlch ein beweis für nicht reguläre sprachen also heisst das, dass wir immer ein nea oder epsilon nea als automat brauchen um die sprache zu erkennen? weil nicht reguläre sprachen die nicht endlich lang sind nicht von einem dea gelesen werden können? - also ist das nur eine möglichkeit zu zeigen, dass der String zu lang ist? ahh oder stimmt sie haben zyklen erwähnt. meinen sie dass durch die zyklen ein nea entsteht weil der string zu lang wird und die Länge des Wortes weist drauf hin dass es einen Zyklus geben muss den man mit dem pumping lemma beschreiben kann? aber ich erinnere mich auch daran dass sie gesagt haben dass das pumping lemma nicht ganz zuverlässig ist - kann es sein dass A^nO^n doch regulär ist aber mein vorgeschlagener automat ist auch ein zyklus also das hat sich erledigt aber wieso ist a^nb^c^dann nichtmehr regulär - also ab einer gewissen anzahl von zuständen nichtmehr regulär - ganz komisch ich hab mich total verfahren

[@Gogol-Doering]

Ja, die Kette von Zuständen, in denen A gelesen wird, kann auch aus nur einem einzelnen Zustand bestehen, der einen Übergang mit Buchstaben A auf sich selbst hat. Das fällt unter den Fall 1 im Video. Dann hat der Automat also einen Zyklus, in denen er A lesen kann - und das bedeutet, er kann sich nicht merken, wie oft er diesen Zyklus durchlaufen hat, also auch nicht, wie viele As er schon gelesen hat. Wenn er dann im Anschluss Os liest, kann er nicht prüfen, ob es genau so viele Os wie As sind. Man kann leicht einen Automaten bauen, der alle A^nO^n akzeptiert, aber eben keinen Automat, der nur A^nO^n und sonst nichts anderes akzeptiert.

[@SmokingSoni]

@@Gogol-Doering ja okay genau das wird streng genommen also der Automat darf nur A^nB^n Strings erzeugen hm ja ergibt auch Sinn - also darf ich generell nur Automaten bauen die nur Sprachen erzeugen können, die selbst im am schlechtesten gewähltesten Fall/Weg immer noch teil der Sprache A^nB^n erzeugen.. das hab ich glaub ich falsch verstanden warum auch immer alles andere wäre ja viel leichter zu lösen sonst und eigentlich würde der Automat eine andere Sprache erzeugen wenn er mehr erlaubt. Also mein vorgeschlagener Automat würde dann nicht nur A^nB^n lesen können sondern eigentlich a*bb* oder so (als reguläre Sprache ausgedrückt weil beschrieben ist bisschen uneindeutiger nachzuvollziehen) - dankeschön ich meine ich habs kapiert:)!