給出了下面的語言語法

Question

給語法爲下列語言{0^n w 1^n | n>=0 w is in {0,1}* and |w|=n}

嘗試在解決方案：

S--> 0S1|R 

R--> 0R|1R|empty 

不知道如何保證R的長度是一樣的0的數量或1。

Answer 1

這裏什麼都不做。

每個單詞應該看起來像這樣：0^n w 1^n。所以如果我們有規則S - > 0S1，我們就達到了一個狀態，我們可以從中產生的每個句子形式都看起來像0^n S 0^n。

那麼...這不是我們想要的。不是嗎？我們更進一步，我們需要一些涉及規則V的變量V（編輯：這將是我們的「目標」，但事情可能會出錯，所以我們不使用這兩個規則），這使我們有可能使用S - > 0SV1代替S-> 0S1。有什麼變化？

現在我們得到像這樣的句子形式：0^n S（V1）^ n。所以，例如000SV1V1V1就是這樣的句子形式。現在我們確實需要的一個小增加是規則S - >空

儘管如此，我們仍然還沒有完成，畢竟我們希望它看起來更像0^nV^n1^n。因此，我們添加一個交換V和1的規則。因此，我們將1V - > V1添加到規則集合中。現在有什麼可能性？鑑於像000SV1V1V1這樣的句子形式，我們現在可以將所有的V移動到左邊，並且所有的1移動到右邊。

現在我們成爲真正的語法納粹。我們不希望發生任何問題，所以我們做一些小改動。我們做一些swippidy swappidy。我們把S到現在爲止的每一次出現的都換成了T.於是S - > 0SV1變成了0TV1等等。此外，我們添加規則S - >空| T，並刪除規則T - >空。我們從這得到什麼？那麼......一見鍾情。但是，現在我們可以建立一個機制，確保當我們將V變成1和0時，什麼都不會出錯。

我們只需添加規則TV - > C和CV - > CC。哦耶穌基督，所有這些規則。

現在，給定一個句子形式，我們可以慢慢地將它轉換爲0^n C^n 1^n。什麼用途？ 如果我們不把所有的V都推到左邊，沒有什麼可能會出錯的。 所以：像0000CCC1V111這樣的句子形式對我們的事業不會造成任何傷害，因爲我們不能對V做任何事情，除非它緊挨着C，並且我們也不可能推C，因爲沒有這樣的規則。此外，由於我們將添加規則C - > 0 | 1，如果我們過早地將它們更改爲1和0，如果仍有V浮動，我們就無法完成單詞。

這可能根本就不是必需的，我不確定這一點，但它是我們證明的一部分，我們可以創建的所有單詞都在我們想要用這個語法指定的單詞集合中。 規則是：

S -> empty | T 
T -> 0TV1 
1V -> V1 
TV -> C 
CV -> CC 
C -> 0|1 

編輯： 這是一個Type-0格拉默，雖然。 有了一些變化，這可以成爲一個等效CSG，雖然：

S -> empty | T 
T -> 0TV1 | 0C1 
1V -> V1 
CV -> CC 
C -> 0 | 1 

的主要區別是，我們在某些時候可以決定停止添加0TV1的句型，而是與0C1完成了，得到一個形式如0^n C1（V1）^（n-1）。再次，如果我們過早地將所有的C變成0和1，我們就失去了刪除所有V的可能性。所以這也應該產生我們正在尋找的集合。

這也是我對stackoverflow的第一個答案，因爲我有點喜歡計算機科學理論，所以我希望我的解釋沒有錯。如果是這樣，告訴我。