問題タブ [pumping-lemma]

ポンピング補題を使用してコンテキストフリーではないことを証明しようとしてL={y#x|(y is a substring of x) ∧x,y∈{a,b}^* }いますが、それができないようです。もしも

次に、とのvxy両方、または のみまたは のみのいずれかです。abba

それを示すためにどのようにポンピングできますか？

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

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

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

L = {'abc', 'defghi'}

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

質問の補題の違いを学んでいます。私が見つけることができるすべての参照は、例を使用しています:

両者の違いを示します。通常のレンマを使用してそれを「反証」する例を見つけることができます。

w = uvxyz, st |vy| を選択します。> 0、|vxy| <= p。w に同数の b、c、d が含まれているとします。

私が選んだのは：

y をポンピングすると、a の数が増えるだけで、|b|=|c|=|d| の場合 最初は、今でもそうです。

( w に a がない場合の同様の議論。その後、必要なものを何でもポンピングします。)

私の質問は、Ogden の補題がこの戦略をどのように変えるかということです。「マーキング」は何をしますか？

ありがとう！

^{Bを言語と}します{ 0n1 ⁿ | n> = 0}つまり、0と1は同じ長さである必要があります

Bのsを文字列0p1pと^します^。

Bが規則的であると仮定すると、sはs = xyzに割り切れる必要があります。ここで、xy ⁱ z i> = 0はまだBにあります（ポンピング補題の3つの条件の条件1）。

xyizの場合を考えてみましょう。ここでⁱ =2 so xyyz：すべて0のポンプy
xyyzには0と1が多いため、Bに含めることはできません。したがって、Bは規則的ではありません。

yがxyyzですべて0の場合、＃of 0s>＃of1sであることを理解するのに苦労しています。

なぜ|xyy|できないのか = | z | それでは、0と1の数は同じになりますか？

ポンピング補題の問題について助けが必要です。

これは私がこれまでに得たものです：

y = abbc^n とし、n はポンピング補題からの長さです。a:s の数が b:s の数よりも少なく、b:s の数が c:s の数よりも少ないため、y は L にあります。

u = a、v = bb、w = c^n とします。|紫外線| < y、ポンピング補題で述べたとおり。「ポンプ」(bb)^2 すると、次のようになります。

これは正しいですか ？私は「正しい道」を進んでいますか？

ありがとう

Context-Free Languages の特定のポンピング レンマの問題について質問があります。

次の言語があるとします。

言語が文脈自由ではないことを証明するための私の試みは次のとおりです。

L は文脈自由であると仮定します。補題から定数 n>0 を取ります。

レンマによれば、Z は Z = uvwxy と書くことができ、次のプロパティが保持されます。

vwxには6つの異なる可能性があります

ここまででいいですか？私が確信していないことは、vwx のさまざまなケースが正しいかどうかです。

前もって感謝します

反復補題を使用すると、その言語が正規言語L1 = {WcW^R|W ∈ {a,b}*}ではないことを簡単に証明できます。（アルファベットは{a、b、c}です。W^ Rは逆文字列Wを表します）

ただし、文字cを"x"(x ∈ {a,b}+)たとえば、に置き換えるとL2 = {WxW^R| x, W ∈ {a,b}^+}、L2は正規言語になります。

アイデアをいただけますか？

ご存知のように、反復補題を使用すると、言語L = {WW |W∈{a、b}*}が正規言語ではないことを簡単に証明できます。

ただし、言語、L1 = {W1W2 | | W1 | = |W2|}は正規言語です。以下のようにDFAを取得できるため、

私の質問は、L = {WW |W∈{a、b} *}も文字列の長さが偶数であり（| w | = | w |、間違いなく）、Lは上記のようなdfaを持つことができます。なぜそれは正規言語ではないのですか？

ありがとう。

ポンピング補題を使用して、指定された言語が正規であるかどうかを確認する際に少し混乱しています。

次のことを確認する必要があるとします。

L.0通常の 偶数の 's を受け入れる言語かどうか?

L の DFA を構築できるので、これが正則であることはわかっています。しかし、ポンピング補題でこれを証明したいと思います。

ここで、 String を取るとしますw= "0000"。

x = 0これで、文字列が、y = 0、およびに分割されますz = 00。にポンピング補題を適用するi = 2と、文字列 が得られますが"00000"、これは私の言語には存在しないため、レンマをポンピングすることで、言語が規則的ではないことが証明されます。しかし、それは DFA によって受け入れられますか?

どんな助けでも大歓迎
ですありがとう

次の言語が正則でないことを Pumping Lemma で証明しようとしています。しかし、私がそれを正しく行ったかどうかは本当にわかりません。

{L = a ^{2 n} | n>= 0}

これまでに行ったことは次のとおりです。

s = a ^{2 p}

x = a ^{2 i}

y = a ^{2 j}

z = a ^{2 p-ij}

したがって、xy ² z = a ^{2 p+j}

これは、 a ^{2 p+j} > a ^{2 p} であることを意味し、言語は規則的ではなくなります

私はそれを正しくやっていますか？それとも私が間違っていることがありますか？