 regulären Ausdruck nachweisen |
Phoney
Jungspund
Dabei seit: 13.12.2006
Beiträge: 20
 |
|
| 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 09:54 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
|
|
20.11.2007 12:31 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
20.11.2007 18:17 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Das verwirrt dich zurecht. Ich habe mich verschrieben. 
Es sollte natürlich "nicht regulär" heißen.
|
|
|
20.11.2007 21:58 |
|
|
|
|
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 
__________________
I'm 71% Megatron!
|
|
|
21.11.2007 15:48 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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 ![[latex]b^n y^{n+1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?b^n y^{n+1}) ist schon nah dran. 
Allerdings fehlt mal wieder die nötige Argumentation. Auch was y ist, ist nicht gesagt.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 21.11.2007 17:33.
|
|
|
21.11.2007 17:31 |
|
|
|
|
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.
__________________
I'm 71% Megatron!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von JROppenheimer: 21.11.2007 23:51.
|
|
|
21.11.2007 23:03 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
22.11.2007 00:13 |
|
|
|
