上下文無關語法 - 計算理論

我正在爲我的決賽進行學習&我在讀維基百科的上下文無關語法文章，並遇到以下示例。上下文無關語法 - 計算理論

S → SS- (1st production rule) 

S → (S) - (2nd production rule) 

S →() - (3rd production rule)

我很清楚左派和右派。當我試圖解決這個問題，我先開始符號

S-> SS -> (S)S->()S->()(S) ->()()

，但是當我看到了答案，它是這樣

S → SS → SSS → (S)SS → ((S))SS → ((SS))S(S) 
→ ((()S))S(S) → ((()()))S(S) → ((()()))()(S) 
→ ((()()))()(())

我不知道哪裏出了問題我的回答？是否有必要使用第一條生產規則兩次？有誰能幫我解決這個問題嗎？

2010-12-11 cool

在上面的問題S是非終端和（，）是終端符號。我知道我們正在使用遞歸，但它是如何工作的？ – cool 2010-12-11 22:23:43

當我試圖解決這個問題，我先開始符號

什麼問題？維基百科文章不會造成任何問題。它只是顯示描述匹配良好的圓括號的語言的文法，並給出了該語言中的單詞以及如何派生它的例子。

S-> SS -> (S)S->()S->()(S) ->()()

這是一個完全有效的推導。

，但是當我看到了答案，它是這樣

這不是的答案（沒有問題）。這只是一個例子。

我不確定我的答案出了什麼問題？

你的派生沒有任何問題。 ()()和((()()))()(())都是該語言中的有效單詞。

是否需要兩次使用第一條生產規則？

您可以根據需要隨時應用生產規則（假設當前需要更換的非終端），並且可以按照您希望的任何順序應用。這一切都取決於你想要派生出哪個單詞。

2010-12-11 22:24:32 sepp2k

因此，我們可以多次應用規則，因爲我們希望在末尾實現終端符號？ – cool 2010-12-11 22:28:43

@cool：是的，沒錯。 – sepp2k 2010-12-11 22:32:32

@cool：是的，但通常（在考試中，或者在編寫解析器時），你會以另一種方式 - 使用規則來顯示特定序列（例如'（（（）（））'）是有效的。 – SimonJ 2010-12-11 22:33:13

您的方法沒有什麼「錯誤」 - 您剛剛爲維基百科文章推出了不同的符號序列。

至關重要的一點是，它可能導出匹配的任何序列，使用嵌套語法括號，但不能像(()或)()(序列。

2010-12-11 22:25:57 SimonJ

好吧。謝謝。 – cool 2010-12-11 22:31:06

該文章只是給出一個可能的字符串，可以使用該語法來表示...您正在給另一個可能的字符串。您可以使用派生來證明這些字符串根據語法是有效的（即沿相反方向）。

編輯：打到衝：P

2010-12-11 22:26:56

回答