Warum ist L" regulär?

Question

Hallo,

mich irritiert gerade, dass in der Aufgabe steht, dass die Sprache L'' regulär ist. Kann ich da nicht beweisen, dass zum Bsp für das Wort \( a^n b^n \) das Pumping Lemma für reguläre Sprachen nicht gilt?

 

Answer 1

Hallo!

Es stimmt, dass die Sprache \(a^n b^n \) nicht regulär ist und dass du dies auch mit dem Pumping Lemma widerlegen kannst.

Allerdings lautet die Sprache L'' ja \(b^m c^n \) lediglich mit der Einschränkung    \(m,n \geq 0\), dh. m und n müssen nicht gleich sein! Genau das ist nämlich das Problem, warum \( a^n b^n\) nicht von einem endlichen Automaten erkannt werden kann: Ein EA kann nicht überprüfen, ob nach der Eingabe von n mal "a"' dann auch genau n mal "b" eingegeben wurde. Diese Einschränkung hat die Sprache L'' aber nicht: hier dürfen auf m mal "b" einfach n mal "c" folgen und die tatsächliche Anzahl der b's und c's ist im Grunde genommen egal ( dh. es ist keine Beziehung zwischen m und n gegeben, die erfüllt sein muss, um ein gültiges Wort der Sprache L'' zu erzeugen).

Natürlich liegt das Wort \( b^n c^n \) auch in der Sprache L'' drin. Wenn du damit nun aber das Pumpinglemma durchführst, dann erhälst du am Ende nach dem Pumpen bspw. den Ausdruck \( b^n+2 c^n \) und dieses Wort liegt ja auch wieder in der Sprache L'' drin, weil wie oben erläutert kein Zusammanhang zwischen der Anzahl der b's und der c's gefordert ist (dh. die Exponenten von b und c müssen insbesondere nicht gleich sein!) Damit liefert das Pumpinglemma für diese Sprache keinen Widerspruch!

Denk aber daran: nur weil das PPL gilt, ist das noch kein Beweis, dass die Sprache regulär ist! Wir können lediglich aus der Nicht-Gültigkeit des PPL schließen, dass dann die Sprache nicht-regulär ist!

In Bezug auf die Aufgabe bedeutet das, dass du der Angabe, dass die Sprache L'' regulär ist, einfach trauen kannst / musst ;)

Ich hoffe, ich konnte dir weiterhelfen!

Gruß, Janine (Tutorin)

 

Comments

Hallo,

mich verwirrt schon der Anfangssatz...

Meine Sprache a^nb^n kann doch von keinem EA erfüllt werden oder ? Meiner Meinung nach habe ich am Ende für das reguläre PPL die Form a^n+k b^n c^n dastehen, was ja nicht mehr aus L ist...

Wieso ist denn die Sprache L´mit a^m b^n c^n nicht regulär ?

Was ich im Grunde nicht verstehe, wieso die KOMBINATION der beiden Sprachen nun das PPL für EA erfüllt, aber nicht regulär ist?

Meine Sprach L" ist ja regulär, das leuchtet mir ein.. aber meine Sprache L´, mit dieser weiß ich nichts anzufangen.. Wieso ist sie denn nicht regulär ?
Für diese brauche ich ja das PPL für kontextfreie Sprachen oder nicht ?

Gruß