13

{0,1}両側から同じように読むことができないアルファベット上のすべての単語の言語が文脈自由言語であるかどうか（つまり、特定の文法に変換できるかどうか）を決定する際に、あなたの助けが本当に欲しいです。ルール）。{ w | w <> wR }

正規言語の反復補題によって文脈自由言語ではないことを証明しようとしましたが、矛盾につながる文字列は見つかりませんでした。

助言がありますか？

4

2 に答える 2

12

私があなたの質問を正しく読んでいるなら、あなたは非回文のセットが文脈自由言語であるかどうかを見ているのです。

これは文脈自由言語です：

S --> 0S0 | 1S1 | R
R --> 0V1 | 1V0
V --> 0V0 | 1V1 | R | 1 | 0 | ε

Sから始めて、文字列を外側から内側に構築するという概念があります。Sを使用すると、一致しないものが存在するRのケースに到達するまで、一致する1または0を必要な数（場合によってはなし）配置できます。そこから、一致または不一致のいずれかを配置できます（この時点で、回文ではないことがすでに保証されているためです）。これは、すべての非回文を説明するのに十分です。外側から内側まで、ゼロまたはゼロで始まります。より多くの一致するペア、次に1つの不一致のペア、次に0個以上のペア（一致するかどうか）。最後に、真ん中にキャラクターがある場合とない場合があります。

PSまだお持ちでない場合は、計算理論に関するSipserの本が間違いなく優れています。実際、それは私が今でも時々読んでいる唯一の大学の本です。

于 2012-04-05T16:51:39.187 に答える
2

この質問は、確かにコンピューター科学者としての私の頭上にあります。しかし、数学者として、私はここで貢献する何かを持っています。

wそれ自体が文脈自由言語である場合、 ：の逆転を解決するためのクロージャが存在します。w

文脈自由言語は、以下の操作で閉じられます。つまり、LとPが文脈自由言語である場合、次の言語も文脈自由言語です。

..。

  • Lの逆転

ここで求められているのはこれだけのようです。これらのリファレンスは、初期および後続の閉じたフォームがどのように導出されるかに関する追加の背景情報を提供します。

（集合論からの追加の、潜在的に役立つ参照）

于 2012-04-04T22:38:41.390 に答える