Pumping Lemma: Ist es in diesem Fall gültig, „das Produkt der Kräfte zu multiplizieren“?

  • Ich muss zeigen, dass

    $ \ qquad \ displaystyle S = \ {(10 ^ p) ^ m \ mid p \ geq 0, m \ geq 0 \} $

    ist keine reguläre Sprache, die Pumping Lemma verwendet.

    Kann ich das Produkt der Potenzen multiplizieren und drücken Sie Folgendes aus: $ S = \ {1 ^ m 0 ^ {pm} \ mid \ dots \} $ und wenden Sie das Pumping-Lemma an, wo ich 1 pumpe, und dann sagen, dass die Sprache die neue Zeichenfolge nicht akzeptiert?

    15 August 2012
    Raphael
1 answer
  • Sie haben Recht, der Hochsatz bedeutet in diesem Zusammenhang Verkettung.

    Um zu beweisen, dass eine Sprache nicht regelmäßig ist, nutzen Sie die Tatsache, dass jede reguläre Sprache "gepumpt" werden kann. Finden Sie zuerst heraus, was ein Wort "pumpen" bedeutet (ich kann Ihre Hausaufgaben nicht für Sie machen), und zeigen Sie dann, dass Ihre Sprache nicht gepumpt werden kann und daher nicht regelmäßig sein kann. Im Grunde nehmen Sie ein ausreichend langes Wort, das zu Ihrer Sprache gehört, und zeigen, dass es nicht so zerlegt und gepumpt werden kann, dass es dem pumpenden Lemma genügt Die Umkehrung des pumpenden Lemmas ist nicht immer richtig: Wenn also eine Sprache das pumpende Lemma NICHT befriedigt, kann sie dennoch unregelmäßig sein. Aus diesem Grund wird das Pumping-Lemma verwendet, um eine Sprache von einer Gruppe von Sprachen auszuschließen und eine Sprache nicht in eine Reihe von Sprachen (wie z. B. regulär) aufzunehmen. Mit anderen Worten, die Befriedigung des Pumping-Lemmas ist eine notwendige, aber nicht ausreichende Bedingung für eine regelmäßige Sprache.

    15 August 2012
    Brian