私は言語を持っています: L = {0^i 1^i | 私 >= 0}
それを記述する文法は、それが文脈自由言語であることを証明しています: S -> 0S1 | e
言語が文脈自由であれば、ポンピング補題が成り立つはずです。ただし、「ポンプ」に何を選択しても、0101などの0と1が混在して動作しません。
それが本当に文脈自由言語であるというのは正しいですか？もしそうなら、Pumping Lemma の使用例を教えてください。
1 に答える
0
文脈自由文法で言語を記述できる場合、その言語は文脈自由です。ポンピングできる文字列を見つけたとしても、ポンピングできない文字列が存在する可能性があるため、ポンピング補題を使用して言語が文脈自由であることを証明することは困難です。
通常、ポンピング補題を使用して、言語が文脈自由でないことを証明します。必要なのは、ポンピングできない文字列の 1 つの例だけだからです。
L = {0^i 1^i | の文字列の例を次に示します。i >= 0} とそれをポンピングする方法。
文字列 w=01 は、次のように分割できます。
u = empty
v = 0
x = empty
y = 1
z = empty
uv^ixy^iz は、すべての i >= 0 に対して L にあります
于 2013-11-18T06:12:41.503 に答える