設計上下文免費語法的[HW]

我一直在爲此做了大約5個小時的作業，我希望你們中的一些人能夠提供幫助，因爲CFG是CS的重要組成部分。設計上下文免費語法的[HW]

我的真正的麻煩是與部分C.

設計一個CFG每個下列語言：

A. {（A^I）（B^j）的（C^k）的} WHERE （！I = j）的與I，J，K> = 0）

我想出了：

Start-> aAB | AbB 
A-> epsilon | aA 
B-> epsilon | C | bB 
C-> epsilon | cC

這似乎爲BCCC，ABBCC，aabbb，CC工作，所以我覺得我好這裏。

B. {（A^I）（B^j）的（C^k）的}，其中（i！= k）和I，J，K> = 0）

Start-> aABC | ABcC 
A-> epsilon | aA 
B-> epsilon | bB 
C-> epsilon | cC

這適用於bc，bbcc，ab，abb，aac，所以當我i = 1時，看起來很好。！= k）和I，J，K> = 0）

Start-> aABC | AbB | ABcC 
A-> epsilon | aA 
B-> epsilon | bB | C 
C-> epsilon | cC

我不認爲C部分是正確的，但我相信，A和B是正確的。任何人都可以告訴我，如果我對/錯或幫助嗎？我相信自從最後一種情況，我只是在做一個OR，並且因爲我的A，B，C變量幾乎是相同的，所以我可以通過組合來避免。它看起來像BC工作，acc工作和許多其他工作，但我覺得我不應該簡單地結合起始狀態。

任何人都知道我是否正確或接近或有任何提示？

來源

2011-03-07 user591162

請記住，當您測試語法時，一定要測試應該被拒絕的字符串（請參閱@ Paulo的答案，當前有些失敗的答案）。要解決前兩個問題，寫一個代表A^i B^j的語法，其中i != j;在第1部分的末尾添加一個任意數量爲c的語法，並將該語法添加到第2部分的中間。對於第3部分，請記住兩個語法的聯合可以很容易地寫爲語法。

來源

2011-03-07 01:13:39

我仍在處理事情，我認爲這個問題可能並不瞭解如何正確設置i = j或i！= j。我擁有的書是神祕的，沒有真正的例子。我相信i = j或i！= j的決定因素取決於開始狀態。所以爲了解決問題，我有（開始 - > aAB | AbX; A-> epsilon | aA; B-> epsilon | bbB; X-> epsilon | cC。我一直在玩東西，我認爲這是最好的解決方案。這確實是對的？我基本上支持a和b是否是偶數，所以ab現在將被拒絕，abb將被接受。我的理解是否正確？ – user591162 2011-03-07 01:32:15

@ user591162：不要將語法看作解析器，而應該將其視爲生成字符串的機器。作爲第一件嘗試的事情，寫一個生成'A^i B^j'的語法，其中'i == j';這很可能在你的教科書中。然後想想它是如何工作的以及如何適應'i！= j'。順便說一句，考慮偶數與奇數會使你寫錯這個語法的方向。 – 2011-03-07 01:35:19

您的第一個語法匹配abc（按開始 - > AbB - > abB - > abC - > abc），所以它不是正確的語法。

因此，您需要確保a s和b s是以相同的數量創建的（對於其中的一個來說更多）。

同樣的abc也符合你的第二條規則，也不應該被允許。

來源

2011-03-07 00:35:29

這對A是否正確？（起始→aAB | AbD; A→ε| aA; B->ε| b | C | bbB; D->ε| bB | C;>ε| cC）。我相信這更有意義。我一直在爲此工作40米，這是我最好的解決方案，基本上在每種條件下分支以確保沒有我等於j的。 – user591162 2011-03-07 01:16:56

@ user591162：你知道如何爲'A^i B^j'編寫語法，其中'i == j'？ – 2011-03-07 01:24:43

設計上下文免費語法的[HW]

回答

相關問題