Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Regulär oder nicht?
Autor
Universität/Hochschule J Regulär oder nicht?
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Themenstart: 2021-05-21

Hi, ich soll zeigen, oder widerlegen, dass folgende Sprachen regulär sind. https://matheplanet.com/matheplanet/nuke/html/uploads/b/53673_pump.png Leider komme ich hier nicht weiter. Das Problem ist, dass ich nicht einmal weiß, ob das Pumpinglemma hier jeweils stark genug ist. Über die Abgeschlossenheit wüsste ich ebenfalls nicht, wie ich hier argumentieren könnte. Zu L1: i = 1 funktioniert nicht. Dann hatte ich an i = n-1, j = 1 gedacht, sodass ich das b abpumpe und somit j >= 1 verletze, aber auch hier kann die Zerlegung ja wieder so gewählt werde, dass es nicht der Fall ist. Die Voraussetzungen für beide Sprachen sind ja auch identisch und deshalb ist meine Vermutung hier, dass falls es sich per Pumpinglemma widerlegen lässt, die Lösung jenseits der a^ib^j liegt, da sonst beide Aufgaben auf gleiche Art lösbar wären. Wenn die Sprachen regulär sind, müsste es ja auch einen Automaten geben, der die Sprache repräsentiert. Aber auch hier bin ich unsicher, da ich nicht weiß, in welche Richtung meine Überlegung eigentlich gehen sollte, sprich Widerspruch oder Beweis der Regularität. Über Tipps und Anregungen würde ich mich freuen. Viele Grüße


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.1, eingetragen 2021-05-21

(b) ist sicherlich regulär. Saloppe Begründung: Der Automat muss nur bis schlimmstenfalls 30 zählen. Konstruktiv: Zeige, dass es für ein bestimmtes k einen Automaten gibt und vereinige dann die Automaten für alle 30 Restklassenkombinationen. Die Regularität von (a) sollte man mittels Pumpinglemma widerlegen können. In beiden Fällen hilft es, das reguläre Präfix zu ignorieren und sich auf den relevanten hinteren Teil zu konzentrieren. (man sollte ggf. begründen, warum man das darf)


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-21

Danke erstmal für die Antwort. zu (b): ich glaube hier kann ich nun dank deinem Denkanstoß auch gut mit der Abgeschlossenheit, hier bezüglich der Verkettung, arbeiten. Für (a) hilft mir das leider nicht. Ich wüsste hier auch nicht, wie ich das reguläre Präfix ignorieren soll, bzw. begründen kann, dass ich es ignorieren darf, wenn ich das Pumpinglemma anwende. Vielleicht kannst du das noch etwas genauer ausführen.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.3, eingetragen 2021-05-21

Edit: Ups, das geht nicht. Blödsinn geschrieben. :(


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.4, vom Themenstarter, eingetragen 2021-05-21

Also für den nicht regulären Teil war meine Idee: \ z = c^2n b^10n c^5n dann käme ich auf \ v = c^m mit 1<= m <= n u v^2 w = c^2n+m b^10n c^5n hier würde ja dann das Verhältnis nicht mehr passen, wobei ich auch nicht weiß, wie ich das Formal ausdrücken sollte (uns wurde gesagt wir sollen dann später in der Klausur bloß nicht sowas schreiben) Würde das denn zumindest passen, oder habe ich da bereits einen Denkfehler drin? Aber selbst wenn ich gezeigt habe, dass der hintere Teil nicht regulär ist, falls das so überhaupt mit meiner Wahl korrekt ist, weiß ich nach wie vor nicht, wie ich es dann zeigen soll mit dem entsprechenden Präfix. Wie du selbst schon bemerkt hast, geht das ja scheinbar nicht.


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-21

Wenn meine Idee im letzten Post für die Zerlegung des hinteren Teilwortes korrekt ist, hätte ich nun folgende Idee. a^i b^j lässt sich offensichtlich als EA darstellen. Gilt das Pumpinglemma für den hinteren Teil der Sprache, dann existiert ein EA, der die Sprache beschreibt. Insgesamt könnte man die beiden EAs dann zu einem zusammenfügen und hätte einen EA der L1 beschreibt. Wenn ich nun widerlegen kann, dass die hintere Teilsprache regulär ist, dann gibt es ja auch folglich keinen EA dafür und somit insgesamt keinen EA der die Sprache beschreibt. Es gibt jedoch für jede reguläre Sprache einen EA der diese beschreibt, also kann L1 nicht regulär sein. Macht das Sinn?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.6, eingetragen 2021-05-21

Nein, das geht eben so einfach nicht. Das war genau mein (mir nicht zum ersten Mal unterlaufener) Denkfehler. Nimm als Gegenbeispiel die Sprache $\{a^*a^n, n \in \mathbb{P}\}$. Die Sprache ist offensichtlich regulär, obwohl der hintere Teil das Pumpinglemma verletzt.


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.7, vom Themenstarter, eingetragen 2021-05-24

Okay, das ist blöd. Ich hab leider überhaupt keinen anderen Ansatz hierzu. Abgesehen von dem Pumpinglemma und der Abgeschlossenheit kenne ich keine Methode. Auf dem Aufgabenblatt gibt es in einer anderen Aufgabe ein Beispiel für die Substitution. Da muss ich allerdings gestehen, dass ich da auch noch nicht ganz verstanden habe, wie man dabei vorgeht (wurde in der Vorlesung nicht thematisiert). Wäre das hier die Möglichkeit der Wahl, oder hat vielleicht noch jemand eine andere Anregung bzw. Tipps, wie man alternativ vorgehen kann?


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 919
Wohnort: Kiel, Deutschland
  Beitrag No.8, eingetragen 2021-05-24

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo Schutze, du kannst es mittels der Nerode-Relation versuchen. Mit dem PL müsste es aber auch gehen. Wenn \(n\) die Pumping-Konstante für \(L_1\) ist, dann wäre mein erster Versuch vermutlich \[z := a^{60\,n}\,b^{60\,n}\,c^{4\,n}\,b^{20\,n}\,a^{10\,n}\in L_1\] und die Länge davon ist erheblich größer als \(n\). mfg thureduehrsen\(\endgroup\)


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.9, vom Themenstarter, eingetragen 2021-05-24

@thureduehrsen Danke erstmal für deine Antwort. Den Beweis mit dem Satz von Myhill-Nerode würde ich nach Möglichkeit vermeiden wollen, da das Verfahren nicht in der Vorlesung behandelt wurde (vermutlich würde ich auch zu lange dafür brauchen, das nachzuvollziehen, um eine Aufgabe zu lösen). Meine Wortwahl für das Pumpinglemma war ähnlich zu deiner, nur das ich wie folgt gewählt habe: i = n j = n k = 30n Wenn ich mir dein Wort z anschaue, komme ich leider auch nicht darauf, wie ich das zum Widerspruch führen soll. Um das einmal auszuführen. v = a^m mit 1<= m <= n |uv| <= n Hier gilt doch für jede Zerlegung uv*w, dass das Wort in L1 liegt. j>= 2 lässt sich so nicht verletzen. Wähle ich i = n ebenfalls nicht. Dann finde ich lediglich wenige Zerlegungen, für die das Pl nicht erfüllt ist. Aber es geht ja darum, dass es keine Zerlegung gibt, die alle 3 Eigenschaften des Pl erfüllt. Stehe ich hier so auf dem Schlauch, oder ist dir ebenfall ein Denkfehler unterlaufen? Viele Grüße


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.10, eingetragen 2021-05-25

Das Pumpinglemma funktioniert. Du musst allerdings für das Präfix mMn. zwingend das minimale $a^2b$ wählen, da sich jedes längere Präfix selbst pumpen lässt.


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.11, vom Themenstarter, eingetragen 2021-05-25

@DerEinfaeltige Diese Zerlegung hatte ich ganz zu Beginn bereits betrachtet und dann wieder verworfen, weil ich mit dem massiven Brett vor meinem Kopf keine ordentliche Fallunterscheidung gemacht habe, sondern es nur einmal gedanklich durchexerziert habe und zu dem Schluss kam, dass es so nicht geht. Hab mich nun nochmal dran gesetzt und bin zu einem befriedigenden Ergebnis gekommen. Danke für deine Hilfe. Sehr beruhigend, dass ich phasenweise nicht der einzige mit Brett vorm Kopf war 😁 Viele Grüße


   Profil
Schutze hat die Antworten auf ihre/seine Frage gesehen.
Schutze hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]