上下文無關文法和逆轉

Question

我設計一個上下文無關文法生成這個語言：

{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* } 

我定義兩個字符串爲：

U -> aU | bU | _ 
V -> aV | bV | _ 

然後再結合這些：

S -> UV 

但是，我如何表達作爲上下文無關文法的逆轉？

Answer 1

您需要使用語法的上下文岬（什麼你這麼遠呈現只是一個普通的語法）的：

U-> aUa | bUb | a | b | _ 

會匹配「貝巴」的東西，「 aabaa「，但不是」aabba「。

我會讓你改變這個以滿足你的需求 - 但請記住，你指定的語言有可能是u是空字符串，因此它會生成{a,b}*中的所有字符串。