Nochmal Pumping-Lemma

vip*r

L={0^m1ⁿ | m+n≥2}

Sei n aus N und n ≥ 1 die Konstante aus dem PL.
Betrachte: z=0ⁿ1ⁿ. Offenbar gilt: z aus L und |z|≥n.

Zerlegung: z=0^k10^k20^k30ⁿ1ⁿ
u=k1, v=k2 und w=k3...

Betrachte i=2, dann ist uvⁱw nicht in L und somit nicht regulär: Wie gehts da jetzt weiter?

Stimmt das soweit?

Ich versteh die Sprache so, dass der Automat der evtl. dahinter stecken würde, beliebig viele 0en und beliebig viele 1en akzept. Die Wortlänge zusammen muss aber in jedem Fall größer oder gleich 2 sein. Stimmt das so?

CStoll

Deine Beschreibung der Sprache sieht in Ordnung aus - aber die Einsetzung im Pumping-Lemma stimmt nicht so ganz.

(Anmerkung: Du hast mal wieder eine reguläre Sprache erwischt und versuchst jetzt zu beweisen, daß sie es nicht ist ;))

vip*r

Ok... Ich hab mir jetzt bei näherem hinsehen schon gedacht, dass sie regulär ist.

Gehen wir mal von oben durch:

Das erste Betrachte ist schon nicht richtig, oder?

Wenn ja, warum nicht?

vip*r

Wenn die Sprache regulär ist, dann könnte ich ja quasi zum Beweis einen Automaten zeichnen und gut is.

Kann man das nun auch noch mit dem PL. beweisen? Können wir das durchmachen?

CStoll

Der Ansatz ist schon falsch - wir haben dir schon mehrfach erklärt, daß diese Anwendung des Pumping-Lemmas nur brauchbar ist um zu beweisen, daß eine Sprache nicht regulär ist. Zum Beweis, daß die Sprache regulär ist, gibt es andere Methoden (z.B. die Formulierung als regulärer Ausdruck oder mit Myhill-Nerode).

vip*r

Hm, ok...

Ich muss mir also anscheinend echt aufschreiben, dass man das PL nur zum Beweis der "unregularität" (gibts das Wort überhaupt?) benutzen kann. Hier ein anderes Beispiel welches nicht regulär sein sollte:

L={0^j1^k0^l | k=j+l; j,k,l aus N}

Annahme: L ist nicht reg.
Wir beweisen dies mit Hilfe des PL mit der Kontraposition.
Sie n aus N und n≥1 die Konstante des PL.

Betrachte: z=

Und ab hier bin ich schon leicht aufgeschmissen. Kurz zur Sprache: Ich versteh die so, dass die Anzahl der 1en so groß sein muss, wie die Anzahl der ersten 0en und die Anzahl der letzten 0en. Soweit richtig oder?

Was mir auch noch immer irgendwie schleierhaft, ist, was das n sein soll. Wir bezeichnen es immer als Konstante des PL. Aber wieso, warum, weshalb?

CStoll

vip@r schrieb:

Und ab hier bin ich schon leicht aufgeschmissen. Kurz zur Sprache: Ich versteh die so, dass die Anzahl der 1en so groß sein muss, wie die Anzahl der ersten 0en und die Anzahl der letzten 0en. Soweit richtig oder?

Kommt hin. Und wenn ich mich recht erinnere, hatten wir diese Sprache schonmal durchgekaut.

Was mir auch noch immer irgendwie schleierhaft, ist, was das n sein soll. Wir bezeichnen es immer als Konstante des PL. Aber wieso, warum, weshalb?

Das Pumping-Lemma basiert ja auf dem Beweis per Widerspruch.
Das heißt, wir tun so, als wäre die Sprache regulär. Dann gibt es einen DEA mit n Zuständen (wobei dieses n unbekannt, aber fest ist), der die Sprache akzeptiert. Bei jedem Wort mit mehr als n Buchstaben muß zum Akzeptieren ein Zustand X doppelt vorkommen - und damit eine Schleife. Jetzt zerschneiden wir das Wort in die Teile u (der Teil, der bis zum ersten Erreichen von X gelesen wurde), v (die Schleife) und w (der Teil von der Schleife bis zum akzeptierenden Endzustand) und könnten durch "Pumpen" (wiederholtes durchlaufen der Schleife) weitere Wörter der Sprache finden.
Bei einer vorgegebenen Sprache kennen wir den DEA nicht, deshalb prüfen wir alle möglichen Aufteilungen und stellen dann idR fest, daß das Pumpen nicht funktioniert - gibt es vermutlich keinen Automaten, d.h. die Sprache ist nicht regulär.

vip*r

Ich hab hier nochmal eine Sprache:

L={(01)ⁿ 0^k | n>k ∧ k≥0}

Antwort: L ist nicht reg.
Ich beweise das mit dem PL.
Sei n₀ und n₀≥1 die Konstante des PL.

Betrachte: z=(01)²ⁿ⁰ = 0²ⁿ⁰ 1²ⁿ⁰ 0ⁿ⁰

Zerlegung: z=0^k1 0^k2 0^k3 1²ⁿ⁰ 0ⁿ⁰
mit k1+k2+k3=2n0

Betrachte i=0, dann ist uvⁱw nicht in L, da gilt:

0^k1 (0^k2)ⁱ 0^k3 1²ⁿ⁰ 0ⁿ⁰ = ... = 0^k1+k3 1²ⁿ⁰ 0ⁿ⁰

=> L ist nicht regulär, da k1+k3<2n0 ist.

Stimmt das so?

CStoll

An der Stelle ist schonmal die Zerlegung des Wortes falsch - (01)ⁿ0^k ist 0101010101...01 00000000..0 (im ersten Block n mal abwechselnd 0 und 1, im zweiten Block k Nullen). Wenn du das dann zerlegst, sollten zwei mögliche Fälle herauskommen, wie die Zerlegung aussehen kann.

PS: Sind bei euch in der Klasse alle so begriffsstutzig? Oder warum hängt ihr immer noch bei den regulären Sprachen fest?

vip*r

Wie lautet dann die zerlegung richtig?

vip*r

aber ich kann doch:

(01)ⁿ 1^k = 0ⁿ 1ⁿ 1^k

schreiben, oder? Das sind doch nur Potenzgesetze... Somit ergibt sich doch dann bei der Betrachtung mit n0 das hier: 0²ⁿ⁰ 1²ⁿ⁰ 0ⁿ⁰

Da is doch noch nix falsch, oder?

CStoll

Dazu müssen wir erstmal ein brauchbares Wort aus der Sprache auswählen: Ich entscheide mich mal für z=(01)ⁿ⁺¹0ⁿ (warum? scharfes Hinsehen).
Bei der Zerlegung fällt schonmal auf, daß wegen |uv|<n v komplett im (01)-Teil von z liegen muß. Also können wir zwei Fälle unterscheiden (eigentlich 4, aber die lassen sich paarweise zusammenfassen):

v in (01)*0 (d.h. es beginnt und endet mit 0)
-> u endet mit 1, w beginnt mit 1
-> uv⁰w enthält zwei aufeinanderfolgende 1 und liegt deshalb nicht in L
v in (10)*1 (beginnt und endet mit 1) funktioniert analog
v = (01)^m oder v = (10)^m (m≥1)
-> uv⁰w = (01)^n+1-m0ⁿ liegt nicht mehr in L (weil n+1-m≤n)
(jetzt siehst du, warum ich z genau so ausgewählt habe ;))

PS: Und dieses Ausklammern per "Potenzgesetze" funktioniert nicht so wie du das vorhast, weil die Verkettung von Zeichen nicht kommutativ ist. In natürlichen Zahlen gilt (5*7)³ = 5³*6³, aber bei Wörtern/Sprachen gibt es einen Unterschied zwischen (01)^2[/c] (=0101) und 0[h]2¹2^ (=0011).