Pumping-Lemma

Question

Hallo,

ich habe Problem mit der Aufgabe Au-3-4(opt. Übung 3, Aufgabe 2)

1) Ich verstehe nicht warum L1 nicht regulär nicht und L2 regulär ist( wenn man V02:S.59-S.63 schaut):

L1= {a^mb^nc^n |m; n ≥ 1} (nicht-regulär) 

L2 ={b^mc^n |m; n ≥ 1} (regulär) 

2) ich verstehe auch nicht ganz warum L1 erfüllt die Eigenschaft des Pumping Lemma ( wenn man die Lösung von Übung 1: Aufgabe 7: AU-1-3 schaut)

ich freue mich auf die Erklärung

Answer 1

Hallo uqyws,

zu 1) eine Sprache ist regulär, wenn man alle Wörter durch Vereinigung, Produkt und Iteration über die Basismenge schreiben kann. Das Produkt ist (soweit ich weiß) nur für zwei Elemente bzw. Sprachen definiert, also m^n geht zum Beispiel nicht, daher gibt es nicht die Möglichkeit bei L1 gleich viele b's und c's zu garantieren. L2 wird einfach als b^*c^* definiert, m und n sind unabhängig (m,n>=0 nach Definition, wäre es >=1 müsste man bb^*cc^* schreiben, damit garantiert man mindestens ein b und ein c) und ist damit regulär.

Zu 2.) Die Schleife ist direkt am Anfang und ist nur ein Zeichen lang, dann wird entweder ein a gepumpt und das Wort gehört immer noch zu L1 (die a's sind unabhängig von den b's und c's) oder es wird ein b oder c gepumpt (d.h. es ist kein a darin, das wäre am Anfang), dann gehört das Wort zu L2. Das heißt, die Bedingungen vom PPL werden erfüllt, das war die Aufgabe.
Bei AU-1-3 ist bei L6 zum Beispiel die Anzahl der 1en abhängig von der Anzahl der 0en (doppelt so viele), daher funktioniert das dort nicht. Hier ist entweder die Anzahl der a's egal (wenn ein a vorhanden ist L1) oder das Wort gehört zu L2 und dann ist die Anzahl der b's oder c's egal.

Falls noch etwas unklar ist, frage einfach noch einmal.

Viele Grüße

Anne (Tutorin)

Comments

Vielen Dank für die Antwort.
1. das heißt regulär Sprache muss gelten:  das Produkt ist für zwei Elemente definiert:
deswegen w=(a^n)(b^n)(c^n) ist nicht regulär, aber w=(a^n)(b^n) schon?
2 oder muss noch gelten: (a^m)(b^n): m ungleich n?
Gegenbeispiel:
w1=(a^n)(b^n) : zweite n ist abhängig von erste n.
w2 = (a^n)(b^2n)(aus Übung1: erfüllt PumpingLemma nicht): zweite n ist abhängig von erste n
3. erfüllt w1 Pumping- Lemma auch nicht oder?

---

Genau, es ist wie in 2. w=a^nb^n ist nicht regulär, aber a^nb^m ist regulär, da n und m unterschiedlich sein können.
3. Nein, w1 erfüllt das PPL auch nicht