轉換爲喬姆斯基正常形式

我確實需要你的幫助。我有這些作品：轉換爲喬姆斯基正常形式

1) A--> aAb 
2) A--> bAa 
3) A--> ε

，我應該使用喬姆斯基範式（CNF）。

爲了應用上面的規則我應該：

我立刻會被卡住。原因是A是空的符號（ε是它的身體的一部分）

當然，我不能刪除A符號。

任何人都可以幫助我獲得最終解決方案嗎？

2011-06-26 Joachim

正如Wikipedia所指出的，喬姆斯基標準形式有兩種定義，它們在ε生產的處理上有所不同。您必須選擇允許這些語法的語法，否則您將永遠得不到相同的語法：您的語法生成空字符串，而遵循另一個定義的CNF語法不能勝任這一點。

2011-06-26 14:41:59

所以你實際上是在說我的推理完全錯誤？我應該怎麼做？...... – Joachim

@Joachim：我在說你應該仔細閱讀維基百科上的定義，並決定你是否想要一個完全等價的語法。 –

我不明白這個評論。由於ε是語法語言的成員，顯然第一個定義是適用的。 OPs問題可以通過使語法基本上不收縮來解決，然後去除鏈式規則和無用的符號。 – danportin

要開始轉換爲喬姆斯基標準格式（使用維基百科頁面提供的定義（1）），您需要找到一個基本上等價的非收縮語法。文法G與開始符號S基本上noncontracting IFF

1. S is not a recursive variable 
2. G has no ε-rules other than S -> ε if ε ∈ L(G)

與非遞歸開始符號調用你的語法G，等效語法G'是：

G' : S -> A 
    A -> aAb | bAa | ε

顯然，一套可空變量G'是{S,A}，因爲A -> ε是生產G'而S -> A是連鎖規則。我假設你已經有了一個從語法中去除ε-規則的算法。該算法應產生類似於下面的語法：

G'' : S -> A | ε 
     A -> aAb | bAa | ab | ba

語法G''基本上是非收縮的;您現在可以將其餘的算法應用到語法中，以查找Chomsky標準形式的等價語法。

2011-06-26 23:36:58 danportin

非常感謝您的解釋。不幸的是，我仍然遇到解決練習的問題。我是一名學生，因爲幾天後我要參加考試（編程語言和編譯器）......我想知道我是否可以依靠某些知識來填補我的空白......是我的電子郵件地址：[email protected]謝謝 – 2011-06-27 16:39:51

如果您試圖首先解決問題並接受答案，您可能會發現SO的成員知識淵博，樂於助人。 – danportin

回答