11

したがって、これはポンピングの補題とそれがどのように機能するかについてではなく、前提条件についてです。

ネットのどこでも読むことができますが、その正規言語は正規言語の反復補題を通過する必要がありますが、今では誰もが実際には正規言語の一部である有限言語について話します。

したがって、次の言語は通常の言語であると同時に有限の言語であることに同意するかもしれませんが、それは間違いなく正規言語の反復補題を通過しません。

L = {'abc', 'defghi'}

誰もそれについて書いていないのか、なぜ私たちが間違っているのか、あるいはそうでないのかを教えてください。

4

4 に答える 4

16

有限言語がポンピング補題で機能する理由は、言語で最も長い単語よりもポンピング長を長くできるためです。ウィキペディアに記載されているポンピング補題は次のとおりです (計算理論の本は手元にありません)。

Lを正規言語とする。次に、 Lのみに依存する整数p ≥ 1 が存在し、長さが少なくともp ( pは「ポンピング長」と呼ばれます) のL内のすべての文字列wは、 w = xyzと記述できます(つまり、wは 3 つに分割できます)。部分文字列)、次の条件を満たします。

  1. | | y | 1以上
  2. | | xy | ≤ p
  3. すべてのi ≥ 0 に対して、xy i z ∈ L

ここで、ある有限言語Lを考えて、k = max w ∈ L |とする。w | Lの最長の単語の長さになります。次に、 Lの最小ポンピング長はp = k +1 であると主張します。Lには少なくともk +1 の長さの単語がないため、そのようなすべての単語が 3 つの条件 (または、実際には、指定したい他の条件) を満たすことが (漠然と) 真です。

もちろん、任意の有限言語が正則であることはわかります (正則言語は有限結合の下で閉じており、1 つの単語のすべての言語は正則です)。ただし、この引数はこれを示していないことに注意してください。通常の言語はすべてポンピングできますが、ポンピングできるが正規ではない言語が存在することを覚えておくことが重要です。

于 2012-08-06T17:14:12.257 に答える
5

「正規言語のポンピング補題の文脈で」

はい、同意します。すべての有限言語は正規言語であり、有限オートマトンと任意の有限言語の正規表現を使用できることを意味します。
一方a infinite language may be regular or not。ベン図を以下に示します。したがって、通常の無限言語 L のみをチェックする必要があります。

FA について考えてみましょう。

  • 任意automata(操作a finite language can not contains loop!もregular expressions for finite language will be without * and +)。

  • automataのための任意a infinite language(regular) will contain the loop。We can't construct an automata for infinite language without loop; ここで、ループは他の状態を介した自己ループである可能性があります。{自己ループの場合、単一のシンボルが任意の回数繰り返されます。他の状態を介してシンボルのシーケンスがループに入った場合、任意の回数繰り返すことができます}.

ポンピングとは繰り返すという意味です。ポンピング補題では、x、y、zwの 3 つの部分に分けることができます。「y」は、ループ内で発生する部分です (つまり、 y>=1 )。したがって、補題のポンピングは、ループ部分を見つけて、このループ部分を何度でも繰り返すことではありません。 ループを何度でも繰り返して、新しい文字列を言語のまま生成するかどうかを確認できます。 wy
ここに画像の説明を入力w'

注:Regular Expressions for infinite language can't be without * and +操作!

[回答]有限言語のオートマトンにはループがないため、言語で新しい文字列をポンピング (繰り返し生成) することはできません。また、ポンピング補題は有限言語には適用できません。

一部の作家は有限言語のポンピング補題も説明していますがi、 xy i z は有限に繰り返すことができます (たとえば、 k ≤ i ≤ m )

ここに画像の説明を入力

ベン図では、すべての有限集合は正則です。無限集合は規則的であるかもしれないし、そうでないかもしれない。 Regular-Languages ⊆ Non-Regular Languages

于 2012-11-24T09:08:52.627 に答える
0

ある言語が無限であることを示す最も簡単な方法があります。L が正規表現 E、L(E) の言語であると仮定します。

L(E) が と等しいと仮定し{ab^nc | n ≥ 0}ます。

E が の形式ab*cであることはわかっており、この言語はおそらく正則であることもわかっています (何かが正則であることを証明することはできません)。なぜなら、ポンピング補題から、この結論はk = 0、別の言い方をすれば、xz = acであり、すべての正規表現には同等のオートマトンがあるからです.

結論は簡単です。DFA がそれ自体への遷移を伴う状態を持っている場合、言語は無限です。

     a   b   c

 q0  q1    
 q1     q1  q2
*q2

q1 は自身への遷移を持っているため、L(E) は無限大です。

于 2015-04-21T15:39:33.027 に答える
-1

有限言語は定義上、正規言語です。すべての単語の結合を表現するだけでそれを満たす正規表現を構築でき (たとえば(abc)|(defghi)、言語を満たす正規表現です)、その結果、それを満たす決定論的有限オートマトンを作成できるからです。

ポンピング補題を通過できないからといって、言語が規則的ではないということにはなりません。実際、ポンピング補題を使用するには、言語の定義にある種のクロージャが必要です。あなたの言語がただの単語の集合であるなら、その中に「ポンピング」するものは何もありません。

于 2012-08-06T17:03:42.153 に答える