CFG和它的反向

Question

我試圖把我的頭圍繞CGS的。令E^*爲'epsilon star'，e爲空字符串，並且ww^r與w的反向相鄰。

我知道，建立一個CFG接受E^*是一個簡單的S -> 0S | 1S | e。接受{ww^r} such that w in E^*

甲CGG是一個簡單的S –> 0S0 | 1S1 | e。

這是否意味着一個CFG接受{wxw^r} such that w, x in E^*是一種「組成」這兩個導致S –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e？

Answer 1

是的，你的語法是正確的！

CFG到{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^*是Regular Language所以它也可以寫Left-Linear and 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 +^

類似的語言，我described here in my answer with DFA。

說明：語言結構相同但符號不同，也有^空字符串是不可能的。也有+上(0 + 1)這裏是*

其DFA

此外，我還建議你查看DFA爲0(1 + 0)*0 + 1(1 + 0)*1。注意RE中的一個小變化^，但是DFA很不相同。