regulären Ausdruck nachweisen |
| 20.11.2007, 09:54 | Auf diesen Beitrag antworten » | ||
| Phoney | regulären Ausdruck nachweisen Hallo L={x aus {a,b}* }: Die Anzahl der a in x ist größer als die Anzahl der b in x} Handelt es sich hierbei um eine reguläre Sprache? Wie kann ich das nachweisen? Ich habe mir gedacht, wenn der dazugehörige Automat endlich ist, ist die Sprache regulär. Jetzt kann ich aber einen Automaten basteln, der unendlich viele a zulässt. Aber auch manche, bei denen es nur ein a mehr gibt als b, der wäre dann ja endlich. Aber ich hab kein Plan wie ich das nachweisen soll. Hoffe auf zahlreiche Tips, Danke 
|
||
|
|
|||
| 20.11.2007, 12:31 | Auf diesen Beitrag antworten » | ||
| Tobias | Ich glaube, man kann den Beweis, dass deine Sprache nicht kontextfrei ist, mit dem Satz von Myhill Nerode oder dem Pumpinglemma für reguläre Sprachen führen. Hattet ihr das schon? |
||
| 20.11.2007, 17:48 | Auf diesen Beitrag antworten » | ||
| Phoney | Das mit dem Pumpinglemma für reguläre Sprachen ist echt ein toller Tip. Das hatten wir, den anderen Satz leider nicht. Kannst du mir denn sagen, wann ich den für L3 und wann den für L2 nehmen muss? Ich hätte nämlich das für L3 genommen. So ganz blick ich da noch nicht durch Gruß Phoney |
||
| 20.11.2007, 18:17 | Auf diesen Beitrag antworten » | ||
| Tobias | Typ-3 (wird wohl dein L3 sein?) Sprachen sind reguläre Sprachen. Man nimmt also das L3 Pumpinglemma, um zu zeigen, dass eine gegebene Sprache nicht regulär ist. Typ-2 (L2) Sprachen sind kontextfeie Sprachen. Entsprechend zeigt man mit dem Pumpinglemma für kontextfreie Sprachen, dass eine gegebene Sprache nicht kontextfrei ist. |
||
| Anzeige | |||
|
|
|||
| 20.11.2007, 21:45 | Auf diesen Beitrag antworten » | ||
| Phoney | Soweit kann ich das nachvollziehen. Aber
Es verwirrt mich, dass du von kontextfrei redest, ich aber regulär nachweisen muss. Kann ich denn nicht das Pumpinglemma vom Typ 3 für regulär benutzen? |
||
| 20.11.2007, 21:58 | Auf diesen Beitrag antworten » | ||
| Tobias | Das verwirrt dich zurecht. Ich habe mich verschrieben. 
Es sollte natürlich "nicht regulär" heißen. |
||
| 21.11.2007, 15:48 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | Reicht es nicht, ein Wort zu finden, dass sich nicht pumpen lässt? ich glaube intuitiv würde ich es mit w = b^n y^n+1, n>0 versuchen ich war im pumpen nie besonders gut, aber wenn ich mich nicht irre, ist w in L, man kann w aber so zerlegen, dass w' = xy^kz nicht in L ist. xy = b^n und z=a^n+1 jetzt muss man ja nur noch ein passendes k wählen, und ist fertig. Ich hoffe, das ist nich all zu falsch, was ich hier versuche 
|
||
| 21.11.2007, 17:01 | Auf diesen Beitrag antworten » | ||
| Phoney |
Das würde ich auch gerne wissen 
Tobias? Reicht das? 
|
||
| 21.11.2007, 17:31 | Auf diesen Beitrag antworten » | ||
| Tobias | Jain.
Das Pumpinglemma besagt, dass es zu jeder regulären Sprache eine natürliche Zahl n gibt, so dass sich alle Wörter, die länger sind als n sind, entsprechend "aufpumpen" lassen. Aufpumpen heißt, dass es einen Substring innerhalb der ersten n Zeichen gibt, den man beliebig oft wiederholen darf, ohne dass das Wort aus der Sprache rausfällt. Wir brauchen die Negation des Lemmas, denn wir wollen ja zeigen, dass die Sprache nicht regulär ist. Die Negation besagt: Wir brauchen für jede beliebige natürliche Zahl n ein Wort x der Länge größer gleich n aus der regulären Sprache, das sich unter keiner Zerlegung uvw aufpumpen lässt. Dein Vorschlag 
Allerdings fehlt mal wieder die nötige Argumentation. Auch was y ist, ist nicht gesagt. |
||
| 21.11.2007, 23:03 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | ach ich hab mich schon wieder vertippt, das sollte b^n a^n+1 sein, jetzt ist w = xyz mit |xy| <= n und z = a^n+1 jetzt kann n beliebig größer 1 sein, und das wort lässt sich nicht pumpen, und damit ist L nict regulär. edit: anders hab ich auch gelernt, dass "regulär" bedeutet "man kann einen DEA machen, der die Sprache bildet". Und das kann ja nicht sein, da man keinen endlichen Automaten konstruieren kann, der diese Sprache bildet, aus folgendem Grund: In der Definition heisst es: "mehr b als a" das würde bedeuten, dass der DEA sich "merken" müsste, wieviele b schon gekommen sind, weil er davon abhängig akzeptiert, oder nicht. Da der Automat aber endlich ist, kann man keinen Automaten konstruieren, der die Sprache bildet, denn dieser müsste unendlich viele Zustände haben, da er sich immer "bewusst" sein müsste, wieviele b schon in der Zeichenkette vorkamen. |
||
| 22.11.2007, 00:13 | Auf diesen Beitrag antworten » | ||
| Tobias | Ganz genau.
Myhill Nerode verallgemeinert und formalisiert deine informelle Begründung übrigens, indem er Wörter in Äquivalenzklassen bezüglich der Nerode-Relation aufteilt. Gibt es unendlich viele Äquivlaenzklassen so ist die Sprache nicht regulär, weil sie nicht durch einen endlichen Automaten darstellbar ist. Das Pumping-Lemma ist eine ähnliche Argumentation: Durchläuft ein Automat mit m Zuständen das Eingabewort mit Länge n > m, muss er nach max. m+1 Zeichen in einem schon besuchten Zustand landen. Das impliziert, dass er eine Schleife gelaufen ist. Die Schleife kann man nun immer wieder in der gleichen Weise durchlaufen, was genau dem "Aufpumpen" des Teilwortes entspricht. |
||
|
|
