從給定的語言構造無上下文語法

Question

我需要幫助爲給定的語言構建CFG。

L = { x ∈ {a, b}* | x != x reversed }，換句話說，L是L中所有迴文的補充。

我更關心如何解決這些問題，而不是具體的解決方案。

Answer 1

好了，我沒身材常見圖案爲了解決這些問題，但我想我知道如何解決這個問題：

首先考慮CFG G(L)爲迴文語言L（讓我們考慮二元字母表） ：

S -> "" 
S -> "0" S "0" 
S -> "1" S "1" 
S -> "1" // odd length case 
S -> "0" // odd length case 

在構建G(L)的想法是，以確保最後的符號等於在S中的第一符號，因此，對於每個位置i從開始i個符號等於i個符號從那個語法產生的單詞結尾。

一個字w未迴文我們要確保有這樣一個位置i，從一開始的i個符號是不等於從年底i個符號。所以，讓我們終止字只生產後，我們把不同的字母在開始和生產結束：

S -> "0" S "0" 
S -> "1" S "1" 
S -> "0" T "1" 
S -> "1" T "0" 
T -> "" 
T -> "0" T "0" 
T -> "1" T "1" 
T -> "0" T "1" // we are allowed to put different symbols more than once 
T -> "1" T "0" // we are allowed to put different symbols more than once 
T -> "0" 
T -> "1" 

你可以給S狀態的意義«我們還沒有把不同的字母又»，和T「我們把不同的字母」的含義。注意：我已經刪除了這個CFG中的S -> ""規則，所以我們只會從T完成，所以我們一定會在生成單詞時放置不同的字母。