regular-language - 正規言語 L には無限の単語がありますか?

Question

これは奇妙ですが、レンマをポンピングすることで、

L正規言語にしましょう。nsuch that のすべての文字列に対してw、Lthatにもある suchに|w| >= n割り込むことができるような定数が存在します。wxyzxy*zL

この補題は、すべての正規言語を主張するため、強力です。しかし、通常の言語の場合はどうなるL = aでしょうか? その中には 1 つの単語 ( a) しかありません。この場合、ポンピング補題はどのように機能しますか?

Answer 1

もしそうなら、任意の inがポンピング補題の結論を満たすn = 2ことは空虚に真です。反例として役立つほど長い単語はありません。より一般的には、が任意の有限言語である場合、ポンピング レンマを満たします。wL|w| >= nLLLnL