我在接近以下問題時遇到問題。找到更復雜的語言的上下文無關語法的方法
給了以下語言的上下文無關文法：
{x#y | x,y in {0,1}* and |x| != |y|}
什麼是解決這個問題的最佳方式是什麼？目前我只是用直覺來解決像這樣的問題，但是有沒有有用的技巧？也就是說，你能想出這種語言的PDA會是什麼樣子，然後從中得到語法嗎？有沒有使用語法A和B來查找語法G = A和B的方法？
我很努力地看到如何解決這個問題，所以任何幫助將不勝感激。
謝謝。
使用直覺是一種有價值的技術。當你解決更多這樣的問題時，你的直覺變得更加敏銳，所以變得更容易。
沒有將語言描述轉換爲CFG的正式技術（除非描述是映射到CFG上的，當然，就像一組生產規則）。通常，語言是否是上下文無關的（雖然CFG必須符合很多約束條件，因此通常可以證明語言不是 CFG，甚至半機械地使用計數參數。 ）兩種上下文無關語言的交集並不一定是上下文無關的，所以沒有可以採用兩種上下文無關語言併爲它們的連接生成一個CFG的過程。
但是，兩種上下文無關語言的聯合是上下文無關的，並且可以從兩種語言的CFG機械地生成CFG。所以有可能將問題分解成碎片。
在這個特定問題的情況下，我建議一個簡單的啓發式，它通常適用於你在正式語言類中得到的問題：嘗試將問題基於你知道答案的簡單問題。
如上所述，兩個CFL的結合是上下文無關的。級聯如下定義：
L ＆centerdot; L = {xy | X ∈ 大號 ∧ ý ∈ 大號 }
這裏的兩種方法，兩者都基於能夠其中以構建類似語言| x | = | 和 |。任何字符串，其中| x | ≠ | 和 |必須在右側或左側有更多的字符。根據您的傾向，您可以在中間（分隔符的一側或另一側）或其中一端添加這些額外的字符。這兩種方法都涉及使用工會;其中一個是串聯，另一個是嵌入。
祝你好運。