Wenn du dich kostenlosregistrierst kannst du neue Themen verfassen, an Umfragen teilnehmen und vieles mehr. Falls Du bei der Registrierung oder Anmeldung Probleme hast, dann kontaktiere uns.
Meine Intuition und das Pumping Lemma sagt mir, dass folgende Sprache regulär ist:
L:={a^n b*|n>=1}
Der reguläre Ausdruck wäre danach a* b*.
Trotzalledem bin ich mir nicht so sicher, ob diese Sprache wirklich regulär ist. Das Problem macht mir dabei das Finden eines DFA's (da ich auf eine unendliche Anzahl von Zuständen komme, um alle Wörter zu akzeptieren). Dabei bereitet mir schon die Sprache L1:={a^n|n>=1} Probleme einen DFA zu finden, da ich jeweils unterschiedliche "Zustandswege" für die unterschiedlichen Wortlängen bekomme, also für a 2 Zustände, für aa 3 Zustände, für aaa 4 Zustände usw. . Wobei mir das Pumping Lemma sagt, dass die Sprache defenitiv regulär ist, da man sich ja nie außerhalb der a's pumpen kann. Ein regulärer Ausdruck wäre dann a*.
Ich hoffe ihr versteht in etwa mein Problem und könnt mir erklären warum ich falsch/richtig liege.
Schonmal vielen Dank im Vorraus für eure Antworten!
Ich vermute, dein Problem liegt im Verständnis der Automaten, ohne dir jetzt natürlich zu nahe treten zu wollen. Zwar weiß ich nicht, auf welchem Alphabet du arbeitest, aber der Automat der Sprache L1 hat max. 3 Zustände.
Startzustand, der nicht Endzustand ist. Von diesem aus kommst du mit einem A in den nächsten Zustand, einen Endzustand. Mit weiteren A's bleibst du in diesem, mit jedem anderen Buchstaben gehst du zum dritten Zustand, kein Endzustand, das Wort wird vom Automaten nicht erkannt.
Beim Automaten zur Sprache L funktioniert es ähnlich, nur musst du hier noch das b dahinter berücksichtigen.
Fragen?
Super! Vielen Dank für deine Antwort! Ja, mein Verständnis der Automaten hapert bei der Unendlichkeit der Zustände (verstehe die Nerode Relation nicht so ganz...). Der Automat für L ist ja regulär und akzeptiert Wörter mit a's und eventuell beliebig vielen b's.
Nur warum ist die Sprache L2:={a^n b^n|n>=1} dann nicht regulär?
Wovon unterscheidet sich denn der Automat für die reguläre Sprache L von der nicht regulären Sprache L2? Wann hat denn ein Automat unedlich viele Zustände?
Nur warum ist die Sprache L2:={a^n b^n|n>=1} dann nicht regulär?
Da du mittels des Pumping-Mechanismus auf a^m b^n kommen kannst.
Zitat:
Zitat von JCDenton
Wovon unterscheidet sich denn der Automat für die reguläre Sprache L von der nicht regulären Sprache L2? Wann hat denn ein Automat unedlich viele Zustände?
L2 mittels eines Automaten zu realisieren ist relativ aufwändig (sozusagen unendlich), da du mitzählen musst, wie oft du schon a gelesen hast. Das beantwortet dann auch gleich die zweite Frage. Ein Automat hat unendlich viele Zustände, wenn du für jedes n einen eigenen Zustand brauchst. Das ist eigentlich auch die Quintessenz aus dem Satz von Myhill und Nerode.
Vielen Dank für deine Antwort! Eine kleine Frage habe ich noch:
Reguläre Sprachen sind ja gegen Durchschnitt abgeschlossen: Aber wie sieht der Schnitt bei den beiden Sprachen L1 UND L2 aus? Wobei L1:={a^n b*|n>=1} und L2:={a* b^n|n>=1}. Der Schnitt wäre dann L={a^n b^n|n>1} ? Nur diese Sprache ist ja nicht regulär! Was mache ich falsch?
Reguläre Sprachen sind ja gegen Durchschnitt abgeschlossen: Aber wie sieht der Schnitt bei den beiden Sprachen L1 UND L2 aus? Wobei L1:={a^n b*|n>=1} und L2:={a* b^n|n>=1}. Der Schnitt wäre dann L={a^n b^n|n>1} ? Nur diese Sprache ist ja nicht regulär! Was mache ich falsch?
Auf die Schnelle würde ich sagen, dass es sich um verschiedene n handeln müsste. Somit wäre L = {a^n1 b^n2 | n1,n2>1} wieder regulär. Falls es genau dasselbe n ist, weiß ich auch nicht, wo der Fehler liegt.
