Typ 2 Sprache die Pumping Lemma erfüllt?
Das Pumping Lemma ist hier erfüllt. Es soll sich hier um eine kontrexfreie Sprache vom Typ 2 handeln. Woran erkenn ich dies?
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik, Mathematiker
Das Pumping Lemma ist hier erfüllt.
Ist es nicht.
Angenommen p sei die Pumping konstante.
Betrachte w = ca^pb^p (w ist in L)
Wir wollen nun eine Zerlegung w = xyz, mit |xy| <= p und |y| > 0
Es gibt somit zwei fälle:
1. y = a^k für ein k>0
2. y = c
(y = ca^k können wir ausschließen)
Bei Fall 1 ist xy^2z nicht in L
Bei Fall 2 ist xy^0z nicht in L.
Die Sprache ist also nicht regulär.
Um zu zeigen, dass die Sprache den Typ 2 hat, kann man einfach eine kontextfreie Grammatik definieren, die L erzeugt
Woher ich das weiß:Studium / Ausbildung – Mache derzeit meinen Mathematik Master