問題タブ [pumping-lemma]

正規言語の反復補題に関する教科書の例の1つに従っています。

条件3が、「yは0のみで構成されている必要があるため、xyyzはCではない」という結論に至るまでの理解に苦労しています。

私はそれが規則的でないことを知って{a^i b^j | i = j }おり、ポンピング補題で証明できます。同様に、ポンピング補題を使用して、これも正則でないことを証明できます。しかし、そのような言語が実際には規則的であるという同様の問題があると思います。そして、補題のポンピングに関する知識に自信がないので、この悪い質問をしています。ごめん。

これが私がそれを証明する方法です: w を としましょうa^p b^(19k+p)、明らかにこれは言語にあります。次に、a をポンピングすると、 になりますa^(p+1) b^(19k+p)。失敗します。したがって、定期的ではありません。

私の証明は正しいですか？

ポンピング補題について読み始めたばかりで、主に矛盾によって、いくつかの証明を実行する方法を知っています。私が答えを見つけられないように見えるのは、この特定の質問だけです。どうやって始めたらいいのかわからない。ポンピング長が必要であり、LPのすべての要素に対して. そしてもちろん、ポンピング補題の 3 つの通常条件と同じように w を書くことができます。wLENGTH(w) >= Pxyz

次の言語が非規則的であることを証明する必要があります。

この種の質問を証明するプロセスを本当にマスターしたいのですが、誰かがこれについて私を助けてくれますか?

編集：申し訳ありませんが、アルファベットは文字列のバイナリ値を意味すること
を忘れていました。と のように。{0,1,+,=}##(00101) = 5#(110) = 6

^{a n} b ⁿ :n>=0のポンピング補題の解き方は知っていますが、この例の解き方がわかりません : a ⁿ b ²ⁿ⁺¹ :n>=0

私はそれを解決しようとしましたが、正しく解決したかどうかわかりませんか?誰かが私を助けてくれませんか?

どのように解決したかを示すことができます。しかし、真剣に、それが正しいかどうかはわかりません。間違っていたら正しいものを教えてください。

問題 : a ⁿ b ²ⁿ⁺¹ :n>=0 が正則でないことを証明してください。

これが私の答えです。

L が正則であると仮定します。このとき、ポンピング補題が成り立たなければなりません。Pumping lemma で m を整数とします。

L においてもw=a ^m b ^2m+1とし、|w|>=m とする。

|xy|<=m および |y|>=1 のポンピング補題 w=xyz によって

ポンピング補題 w _i =xy ⁱ z によると、 i=0,1,2,... の場合も L である

ｉ＝２とし、ｗ_２＝ｘｙｙｚとする。

y=a ^kここで 1<=k<=m および x=a ^qここで 0<=q< m とすると、z=a ^m-qk b ^2m+1

w ₂ =xyyz = a ^q a ^k a ^k a ^m-qk b ^2m+1

= a ^m+k b ^2m+1

しかし、これは 1<=k<=m の任意の値の L にはありません

したがって、ポンピング補題と矛盾します。したがって、L が正則であるという仮定は間違っています。したがって、L は正則ではありません。

これは正しいです？？？

ありがとうございました。

ポンピング補題を使用して、次の言語が規則的でないことを証明しようとしています

L = {a ⁱ b ^j | i = 2j for some j ≥ 0}

このようにs = a ^2p b ^pを選択することにしました |s| ≥ p で、それを 3 つの部分 xyz に分割できます。ここで、i ≥ 0 ごとに xy ⁱ z ∈ Lです。

証明を続けるためのヒントはありますか?

ありがとう！

私は言語を持っています: L = {0^i 1^i | 私 >= 0}

それを記述する文法は、それが文脈自由言語であることを証明しています: S -> 0S1 | e

言語が文脈自由であれば、ポンピング補題が成り立つはずです。ただし、「ポンプ」に何を選択しても、0101などの0と1が混在して動作しません。

それが本当に文脈自由言語であるというのは正しいですか？もしそうなら、Pumping Lemma の使用例を教えてください。

エクササイズに問題があります:

L = {a ⁿ b ^m c ^p | 1 <= n <= m <= p}

その演習用の文法を書くことは可能ですか?

私はそれを解決する方法を理解していません:(私を助けてください