找到相同數量的「a」和「b」語法的等價LR語法？

Question

我似乎無法找到等價的LR語法：

S→aSbS | bSaS | ε

其中我認爲識別字符串與'b'相同的數字比'b'。

這將是一個解決方法？是否有可能找到和LR語法呢？

在此先感謝！

編輯：

我發現什麼，我認爲是等效的語法，但我一直沒能證明這一點。

我想我需要證明原語法生成上面的語言，然後證明語言是爲以下等價語法生成的。但我不知道該怎麼做。我應該怎麼做？

S→aBS | bAS | ε

B→b | aBB

A→a | BAA

在此先感謝...

PS：我已經證明，這種新的語法是LL（1），SLR（1），LR（1）和LALR（1）。

Answer 1

除非語法，直接關係到另一個語法 - 通過標準的轉換，如標準化，零生產消除，等等 - 例如證實兩個文法derivee同樣的語言是非常困難不知道什麼語言是。通常更容易證明（獨立地）每個語法都來自語言。

第一語法您提供：

S → aSbS | bSaS | ε 

確實在事實上獲得的所有字符串的語言在字母表{a, b}*其中一個的個數爲相同的b S上的號碼。我們可以分兩部分來證明：首先，語法所識別的每個句子都具有該屬性，其次，具有該屬性的每個句子都可以由該語法派生。兩種證明都是通過歸納進行的。

對於前向證明，我們通過對派生數進行歸納。假設我們有一些推導S → α → β → … → ω，其中所有的希臘字母代表非終端和終端的序列。

如果微分的長度正好是零，使得它開始與S結尾，則有在任何派生句子沒有端子，以便其清楚，每一個導出的句子具有相同數量的一個 S和b s。 （基礎步驟）

現在爲感應步驟。假設每個長度爲i的派生已知以衍生句子結束，該衍生句子具有相同數量的a s和b s。我們想從這個前提證明，每個長度爲i+1的派生結尾的句子的句號與a s和b s相同。但是，這也很清楚：三種可能的生產步驟中的每一種都保持了平價。

現在，讓我們來看看相反的方向：與相同數量的一個 S和b S能夠從該語法派生的每一句話。我們將通過字符串長度的歸納來完成此操作。我們歸納前提將是，如果它是一個爲每個j ≤ i，與正好j一個 S和jb小號的每一句話都有從S推導，然後用準確i+1一個 S和i+1每一句話的情況下b s。 （這裏我們只考慮只包含終端的句子。）

考慮這樣一個句子。它可以從a或b開始。假設它與一個開始：然後至少有一個b在句子中，使得與該b結束前綴具有相同數目的每個終端。 （把這個字符串想象成一個方形網格：每個a向上向右移動一個單位，並且每個對角向下向右移動，因爲端點的高度與起點完全相同，並且有沒有蟲洞在圖中，一旦我們提升我們必須遲早下降回到起始高度，這是結束b的前綴。）這樣的前綴的內部（以外的所有一個在開始和最後的b）是平衡的，正如字符串的其餘部分一樣。這兩者都較短，所以通過歸納假設，它們可以從S得出。使這些替代，我們得到一個小號b小號，這可以從S導出。相同的參數適用於以b開頭的字符串。再次，基礎步驟是微不足道的。

所以這基本上是你需要適應你的語法的證明程序。

祝你好運。

---

順便說一句，這類問題也可以在cs.stackexchange.com或math.stackexchange.com構成，其中MathJax可用。 MathJax使得寫出數學證明更加乏味，所以你可能會發現你會在那裏得到更多可讀的答案。