CFG及其反转

Question

假设E^*是'epsilon star'，e是空字符串，ww^r是w，w的反面。

我知道构建一个接受E^*的CFG是一个简单的S -> 0S | 1S | e。

接受{ww^r} such that w in E^*的CGG是一个简单的S –> 0S0 | 1S1 | e。

这是否意味着接受{wxw^r} such that w, x in E^*的CFG是导致S –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e的这两者的一种“组合”？

Answer 1

是的，你的语法是正确的！

CFG to {wxw^r} such that w, x in E^* is S –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e是正确的语法。

但重要的是Language {wxw^r} such that w, x in E^*是Regular Language，所以也可以编写。

此语言的右行等效文法为：

S --> 0B | 1A | ^
B --> 0B | 1B | 0
A --> 0A | 1A | 1

与左线性等效的是：

S --> B0 | A1 | ^
B --> B0 | B1 | 0
A --> A0 | A1 | 1

它的正则表达式是：

一种类似的语言I described here in my answer with DFA。

注意:语言结构是相同的，但符号是不同的，也有^空字符串是不可能的。还有( 0 + 1)上的+这里是*

Its DFA

​

​

此外，我还鼓励您查看0(1 + 0)*0 + 1(1 + 0)*1的DFA。请注意RE中^的一个小变化，但DFA有很大的不同。