我想設計一個上下文無關文法下列語言：上下文無關文法平衡parethesis
L = {寬E {（，）} * | w爲平衡}
我提出以下語法：
的S - >（S）S | Ë
而在演講中提出的解決方案是：
的S - >（S）| SS | E
我無法弄清楚，我的解決方案有什麼問題。 我跑無論對於各種情況，如語法：
（（）（）），（）（）（），和（（））（）
並且兩個CFG接受這些字符串。
有人可以請幫忙，我的CFG不會涵蓋什麼情況。或者它們都是等價的。或者達到最終狀態所需的轉換次數是不同的。
這兩種語法都生成相同的語言，所以都不正確。
我更喜歡你的，因爲它是明確的，但這不是要求的一部分。許多人似乎發現其他答案更容易理解，但這也不是要求的一部分，它是一個非常主觀的標準。
rici是正確的。爲了顯示語法是相同的（它們生成相同的語言），可以顯示出一個能夠複製另一個，從而生成相同的字符串。
例如，所提出的語法可以產生(S)S和E如下：
`S => SS => (S)S` and `S => E`.
你的語法可以複製其他語法如下：
`S => (S)S => (S)`
`S => E`
對於S => SS，你不能真正複製那個，或者講課中的語法可以的任何其他S^n。沒關係，因爲你不需要覆蓋所有這些，只要覆蓋一串串終端即可。對於這一個，注意S^n最終必須所有的S變成(S)（其它規則），然後從左邊工作：
`S => (S)S => (S)(S)S => ... => (S)^n S => (S)^n`
現在你做。你可以通過以下方式來證明它：（a）你的語法生成的每個字符串都在L; （b）如果一個字符串在L那麼你的語法生成它。您可以通過歸納法（例如，括號對的數量）來完成此操作。
基本情況：對於n = 0，字符串是E，這在L。 n = 0唯一的字符串是E，它是由我們的語法生成的。
歸納假設：所有的字符串與直到幷包括k雙通過我們的語法生成的括號是L，並在L所有字符串與直到幷包括k對括號通過我們的語法生成。
歸納步：我們顯示出與k+1對我們的語法產生括號的所有字符串都在L，並且在L與k+1對括號的所有字符串由我們的語法生成。
假設串w與通過使用規則S => (S)S我們的語法生成k+1對括號。然後w =（X）Y where X andare words inÝ大號with fewer than K + 1pairs of parentheses. But then they are balanced by the induction hypothesis.瓦特is therefore balanced since X is balanced, thus（X）is balanced and（X）Y = w`過。
假設字符串w與k+1括號對在L。然後，通過L的定義，w是平衡的。平衡括號的字符串必須具有相同數量的左右括號，並且在任何前綴中必須至少具有與右括號相同數量的左括號（因此它們在任何後綴中必須至少具有與左括號一樣多的右括號）。選擇第一個左括號和第一個右括號，以便前綴包含相等數目的左右括號;這是w的子串(x)。在子字符串之後，還必須具有與右括號相同數量的左括號，並且在任何前綴中必須至少有與右括號一樣多的左括號（這是爲了滿足w平衡的條件）。因此，之後會發生什麼 - 我們稱之爲y - 也必須是一個平衡的括號字符串。作爲（正確的）子字符串，x和y必須短於w（包含更少的括號對），它們必須均衡，因此兩者都在L中。但它們都是由語法生成的，而且由於語法包含生產S => (S)S，因此語法生成(x)y。
QED
你的答案好感謝。 – yogeshagr