私は頭をCGSに巻き込もうとしています。を 'イプシロンE^*スター'、e空の文字列、ww^rw を w の逆の隣の w とする。
受け入れる CFG を構築するのE^*は簡単S -> 0S | 1S | eです。
受け入れる CGG{ww^r} such that w in E^*は単純なS –> 0S0 | 1S1 | e.
それは、受け入れるCFG{wxw^r} such that w, x in E^*がこれら2つの一種の「構成」であることを意味しS –> 0S0 | 1S1 | e | B where B –> 0B | 1B | eますか？
はい、あなたの文法は正しいです！
CFG to{wxw^r} such that w, x in E^*はS –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e正しい文法です。
しかし重要なことは、言語{wxw^r} such that w, x in E^*は正規言語であるため、 Left-Linear および Right-Linear Grammarsを書くこともできるということです。
この言語の右ライナー同等の文法は次のとおりです。
S --> 0B | 1A | ^
B --> 0B | 1B | 0
A --> 0A | 1A | 1
左ライナーに相当するものは次のとおりです。
S --> B0 | A1 | ^
B --> B0 | B1 | 0
A --> A0 | A1 | 1
その正規表現は次のとおりです。
0(0 + 1)*0 + 1(0 + 1)*1 + ^
ここで説明した類似の言語は、DFA の回答で説明されています。
注:言語構造は同じですが、記号はありません。また、^空文字列は使用できません。また、あり+ます( 0 + 1)ここにあります*
そのDFA
また、 の DFA を表示することもお勧めします0(1 + 0)*0 + 1(1 + 0)*1。REの小さな変化に注目してください^。ただし、DFA はまったく異なります。