構建語法需要幫助嗎？

L = ((a^n)(b^n+m)(a^m)) | n, m = 0, 1, 2...)

我是新來的上下文自由語法，知道基礎知識，但我一直在爲此掙扎了一段時間。構建語法需要幫助嗎？

對於初學者來說，我不知道是什麼的這部分代碼的意思是：

| n, m = 0, 1, 2...)

其次，怎麼可能有不同的指數相同的變量？我覺得我沒有得到完整的概念。

編輯：我也需要能夠構造規則來構造這個語法。

編輯：添加標籤

來源

2011-09-14 tehman

是整個問題描述/是這個作業嗎？ –

是的，我只是添加了標籤。問題是要求構造一個生成以下語言的語法。我還添加了一些我不明白的Michael幫助過的東西。 – tehman

首先，用文字描述語言。這種語言有一個特別簡潔的描述：它是以a開始的所有字符串的語言，其次是b，其次是a，其中b的數量等於a的總數（在兩側）。

接下來，我們將嘗試提出一條規則，在語言中使用字符串並生成新字符串。給定一個字符串，你可以通過在前面添加一個a，在中間添加一個b，或者在後面添加一個a，在中間添加一個b，來獲得下一個最長的字符串。空字符串也是用這種語言（n = m = 0），所以這可以作爲歸納的基礎。如果我們仔細觀察一下，我們可以得到一個更好的規則：我們可以將任何一個字符串分割成兩個字符串（a^n b^n）（a^m b^m）。由於級聯很容易處理語法，並且對於語法很容易，所以就是這樣。

我得到的規則...

S := LR 
    L := empty | aLb 
    R := empty | bRa

要獲得如aabbba，...

S := LR := aLbR := aaLbbR := aabbR := aabbbRa := aabbba

如果這是家庭作業，將它標記爲好。如果這是自學，希望你能拿走以下技巧：用英語描述語言;嘗試識別簡單的基本案例;嘗試從已經在語言中的字符串中識別出形成更復雜的字符串（即更長的字符串）的規則;重新制定你的規則和/或注意技巧，以便你可以在語法上容易的事情陳述規則;編寫語法並在幾個字符串上檢查它。

在語法中容易做什麼？語言聯合，語言連接，甚至符號對（例如a^k b^k），迴文等的匹配。

來源

2011-09-14 03:51:08 Patrick87

男人，這是驚人的。現在用語法，如果不管用什麼順序出現在某個點上的答案，它是正確的嗎？即使您多次重複使用該規則？ – tehman

只要您正在構建的字符串作爲子字符串存在於生產/規則左側，您可以應用任何規則;儘可能多次使用任何規則。語法類僅在生產限制方面有所不同：LHS和RHS的特徵以及兩者之間的關係。 – Patrick87

這只是n和m值限制的數學表示法。這意味着對於由(a^n)*(b^n+m)*a^m形式組成的字符串，「n」和「m」是兩個單獨的值（儘管它們可能相等），並且0,1,2 ...僅表示它們是大於或等於零。

來源

2011-09-14 03:29:37 Michael

你能解釋一下如何去構建語法規則嗎？ – tehman

對不起，沒有。我無法弄清楚你的語言規範是什麼意思，因爲我習慣了不同的格式。 – Michael

無論如何，您的回答確實讓我前進！ – tehman

構建語法需要幫助嗎？

回答

相關問題