単語の各端末が偶数に発生するように多項式サイズCFG（大きなアルファベット）

Question

すべての単語の言語Lのコンテキストフリーの文法（CFG）を見つけ、単語の各端末がおそらく大きなアルファベットσで偶数に発生するようにする

私の長いaproachは（唯一の非末端はsです）：

s⟶ε| ss

x∈σ：s⟶xsx

x、y∈σ：s⟶xxsyy | yysxx | xysxy | xysyx | yxsyx | yxsyx

これは正しいです？作品は正しい単語を生成しますが、すべての単語を生成しますか？

編集：大規模なアルファベット上のCFGは、各端末が偶数に表示される言語を説明できますか？

edit_2：ソリューションが存在する場合、|σ|でchomsky垂直形式が多項式である可能性がありますか？ ？

Answer 1

これを達成するための定期的な文法さえあります。すべての通常の文法は定義上コンテキストフリーであるため、答えは「はい」です。有限のオートマトンを構築することも可能ですが、文法を求めたので...

方法は次のとおりです。通常の文法では、フォームa - > b cまたはa-> bまたはa-> epsilonのルールが許可されていることを思い出してください。ここで、aとcは非末端であり、bは端子です。これは本質的に、すべての非ターミナルが端子と、文字列の残りの部分を生成する別の非末端を生成することを意味します。すべての非末端は、生成する文字列について特定のプロパティをエンコードすると言えます。

アルファベットシグマのすべてのサブセットを考慮してください。 Sigmaは有限であると思われるため、サブセットのセット（Powerset）もそうです。非ターミナルのセットをシグマのパワーセットにします。

ルールから始めます：{} - > a {a}すべての端末a。すべての非末端xに対して、aがxにある場合、ルールx - > a x- {a}を追加します。またはx-> a x + {a} aがxにない場合（私は +をゆっくり書いている +と - ここでの組合と違いのために）。

最後に、{} - > epsilon（空の単語）を追加します。

文法は、非ターミナルで、奇数で登場したため、再び「キャンセル」する必要がある端子のセットを正確にエンコードします。