將語言規範轉換爲生產規則（不知道它是CFG還是CSG）

Question

我必須編寫一個函數來檢查輸入字符串是否對給定語言規範有效。我認爲這將是一個標準的CFG - >喬姆斯基規範形式，然後是CYK解析，但是語言中的規則之一是防止這種情況發生。

一些規則是簡單的，如果我們定義端子{a,b,c,d,e,f,P,Q,R,S}，然後有效字符串是

1）任何在隔離小寫端子
2）如果「X」是一個有效的字符串，則所以是SX

但第三個原則是

3）如果X和Y是有效的輸入字符串，那麼這樣的PXY，QXY，RXY

其中{P,Q,R}是剩餘的大寫終端，X和Y是非終結符。

這個樣子的生產規則是什麼樣的？我認爲它會像

XY -> PXY (and QXY, RXY) 

但這有兩個問題。首先，這不是一個CFG規則 - 這是否意味着這種語言定義了一個CSG呢？

而第二個是，這是不行的，因爲

XY - > PXY - > PPXY

不會是一個有效的在所有情況下的消息。

Answer 1

我認爲這個語法是上下文無關的，除非我誤解你的意思。

首先，讓我們讓一個是擴大了使用前兩個規則做只是一些有效的字符串非終結，我們得到

A -> a | b | c | d | e | f 

現在，你的第二條規則說，如果你可以建立串ω那麼你可以建立S ω。我們可以編碼爲

A -> SA 

最後，你說，如果你有兩個字符串X和Y，那麼你可以將它們組合爲

PXY 
QXY 
RXY 

一種方式來思考，這將是生成字符串P，後面跟隨任意兩個有效的字符串（對於Q或R相同）。因此，你可以添加規則

A -> PAA | QAA | RAA 

這給出最終語法

A -> a | b | c | d | e | f 
A -> SA 
A -> PAA | QAA | RAA 

希望這有助於！