如何使一個上下文無關的語法用於特定情況下

Question

問題是這樣

創建CFG生成{一個^ I B^Y：2I < J + 2 < 3i的}。 我的問題是，這裏有很多情況。例如，這對j = 1,2,4不起作用。對於j = 5,6,7,8,9，我們需要i = 3,3,4,4,4。所以我如何處理這樣的事情，是否有任何技巧來做這樣的事情，或者我會讓它看起來更難。

Answer 1

你讓它比現在更難。

使用語法是一種經典的遞歸分析技術。對於遞歸，您總是需要提出兩個問題：如何才能進入下一步？我如何知道我什麼時候完成？

第二個問題很簡單：您已經發現基本案例是aabbb（即i=2, j=3）。沒有更短的單詞可以成爲語法的一部分。

現在，假設我們有一個更長的單詞，這意味着i必須大於2.我們如何進入下一步？換句話說，我們如何找到一個更短的有效單詞？我們可以刪除a（遞減i），但我們還需要修復j。從不平等角度來看，很顯然j可以減少兩三個（可能兩個都有效，但其中一個必須有效）。

這將導致模糊的語法，但問題並不是說語法需要明確。然而，如果兩個答案都是可能的，那麼基於總是在同一方向上解決決定（兩個或三個）的策略，很容易提出一個明確的語法。