Ich versuche gerade mir das Pumping-Lemma zu verinnerlichen.
Ich bin dabe auf folgende Aufgabe gestossen:
a^n b^m —->>> ist meines verständnisses nach eine Reguläre Sprache
doch mithilfe des Pumpinglemmas komme ich dabei auf einen widerspruch.
In der aufgabe gibt es zwei "Schleifen". Mithilfe des uvw-Theorems kann ich nur eine "Schleife" darstellen und zwar mithilfe von v^i.
Kann mir da jemand weiterhelfen ?
Wenn ich mich recht erinnere, wurde das Lemma auf a^n b^n angewandt; diese Sprache ist nicht regulär.
Gib mal den Link zu der Aufgabe.
ich hatte die aufgabe a^n b^n gefunden. Diese Sprache ist nicht regulär.
Dann habe ich mich gefragt ob die o.g. Sprache regulär ist.
Meine Frage war nicht ganz richtig formuliert, denn exakt diese Aufgabe wurde nicht gestellt.
doch mithilfe des Pumpinglemmas komme ich dabei auf einen widerspruch.
Wie sieht deiner Meinung nach dieser Widerspruch denn aus???
[latex]\{a^nb^m\mid n,m\in \mathbb{N} \} = \{a\}^*\{b\}^*[/latex]
ist sicherlich regulär, also wird es da garantiert keinen Widerspruch zum uvw-Theorem geben!
Ich sehe den Widerspruch darin, dass ich mit v^i nur ein Wort pumpen kann. Also z.b. aaaaaaa oder abababab. Wenn ich aber einen Automaten konstruiere der beliebig viele a's und danach b's akzeptiert, dann bräuchte ich doch eine Schleife von a nach a, einen Übergang nach b und dort ebenfalls eine Schleife. Ich verstehe nicht wie ich das in uv^iw zerlegen kann, obwohl ich doch nur v aufpumpen kann.
Es reicht doch, dass du mit v zB nur a's pumpst.
Also zB das Wort a^nb^m . pumpste jetzt a's hoch oder runter, sagen wir k a's, dann entsteht ein Wort a^(n+i*k)b^m was auch in der Sprache ist.
Es gibt also für jedes Wort, schonmal eine Zerlegung nach dem Pumping Lemma. Denn du kannst bei jeder Zerlegung v=a wählen und dann beliebig a's hoch oder runterpumpen, und das Wort ist wieder in der Sprache!