すべての単語の言語Lの文脈自由文法（CFG）を見つけて、単語の各終端が、おそらく大きなアルファベットで偶数回出現するようにしますΣ
私の長いアプローチは（唯一の非終端記号はSです）：
S⟶ε| SS
x∈Σ：S⟶xSx
x、y∈Σ：S⟶xxSyy| yySxx | xySxy | xySyx | yxSyx | yxSyx
これは正しいです？プロダクションは正しい単語を生成しますが、すべての単語を生成しますか？
編集：大きなアルファベットのCFGは、各端末が偶数回表示される言語を記述できますか？
EDIT_2：解が存在する場合、チョムスキー標準形が|Σ|で多項式になる可能性はありますか？？
これを達成するための正規文法さえあります。すべての正規文法は定義上文脈自由であるため、答えは「はい」です。有限オートマトンを構築することも可能ですが、文法を要求したので...
方法は次のとおりです。正規文法では、A-> bCまたはA->bまたはA->イプシロンの形式のルールが許可されていることを思い出してください。ここで、AとCは非終端記号であり、bは終端記号です。これは基本的に、すべての非終端記号が終端記号を生成し、残りの文字列を生成する別の非終端記号を生成することを意味します。すべての非終端記号は、それが生成する文字列に関する特定のプロパティをエンコードしていると言えます。
ここで、アルファベットSigmaのすべてのサブセットについて考えてみます。シグマは有限であると想定されているため、サブセットのセット（べき集合）も有限です。非終端記号のセットをSigmaのべき集合とします。
ルールから始めます：すべての端末aに対して{}->a{a}。すべての非終端記号Xに対して、aがXにある場合は、ルールX->X-{a}を追加します。または、aがXにない場合は、X-> X + {a}（ここでは、集合の和集合と差のために+と-をだらしなく書いています）。
最後に、{}->イプシロン（空の単語）を追加します。
文法は、その非終端記号に、奇数で表示されたために再度「キャンセル」する必要のある終端記号のセットを正確にエンコードします。