我正试图把头绕在 CGS 上。让E^*'epsilon star'e成为空字符串，并ww^r在 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^*是这两种结果的一种“组合” S –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e？
是的，你的语法是正确的！
CFG to {wxw^r} such that w, x in E^*isS –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e是正确的语法。
但重要的是 Language {wxw^r} such that w, x in E^*is Regular Language所以也可以写Left-Linear 和 Right-Linear Grammars。
该语言的Right-Liner 等效语法是：
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
此外，我还鼓励您查看0(1 + 0)*0 + 1(1 + 0)*1. 请注意 RE 的微小变化，^但 DFA 完全不同。