如何在將CFG轉換爲CNF時做最後一步？

考慮：如何在將CFG轉換爲CNF時做最後一步？

S->AcA|BcB 
    A->ccBc|ABA|cc 
    B->c 

step1 

    S0->S 
    S->AcA|BcB 
    A->ccBc|ABA|cc 
    B->c 


step2    // change symbol to terminals? 

    S0->S 
    S->ABA|BBB 
    A->BBBB|ABA|BB 
    B->c 

step3    // split? 

    S0->S 
    S->ABA 
    S->BBB 
    A->BBBB 
    A->ABA 
    A->BB 
    B->c 

step4    // what to do when A->AXA? 

    S0->S 
    S->ABA 
    S->BBB 
    A->BBBB //?? 
    A->ABA //?? 
    A->BB  //?? 
    B->c

我不知道如何繼續。

來源

2015-03-13 qqq

I F ixed在代碼格式中似乎是一個疏忽。我還修復了錯誤的標籤; 'cnf'的含義與Chomsky Normal Form有所不同，正如您從懸停在標籤或鍵入時所示的摘錄中可以看出的那樣。最後，我重寫了標題至少要清晰一些，但仍需要更具體一些。你完全無法理解什麼部分？ – 2015-03-13 23:01:21

@NathanTuggy他在代碼註釋「在A - > AXA時做什麼？」。一旦我重新瞭解了我對CNF的知識，就很清楚他需要什麼。 – 2015-03-13 23:08:39

@MillieSmith：恩，我對CNF的瞭解僅限於正式語法規範的名稱和模糊概念，所以我盡我所能。如果您可以重新改寫標題以使其具體，那將對未來的參考很有幫助。 – 2015-03-13 23:10:39

沒有第二步給你。 Step 2 is removing epsilon rules，你沒有epsilon規則。

您也沒有第3步，因爲B-> c在其右側有一個終端 - 不是非終端。有形式的任何單位規則：

Terminal -> Terminal.

這給我們留下您的第1步後：

S0 -> S 
S -> AcA|BcB 
A -> ccBc|ABA|cc 
B -> c

你需要讓你的規則，其餘的形式：

X -> YZ //where X,Y,Z are all nonterminals

要將非終結符和終端的字符串轉換爲上述形式，需要從前面獲取第一個非終結符或終端，然後將其餘字符串轉換爲新規則，並在末尾使用該規則。我沒有很好地解釋，所以我們來看一個例子。

//To convert 
S -> AcA 
//we split it into A and cA, and define a new rule C -> cA, giving: 
S -> AC 
C -> cA 
//Then, C -> cA needs to be converted to the same form, so just replace c with B 
S -> AC 
C -> BA

然而，拋出了上面，因爲首先我將只是改變所有c s到B，因爲這將仍會發生：

S0 -> S 
S -> ABA|BBB 
A -> BBBB|ABA|BB 
B -> c

現在，我看看你的問題再次，這是你在哪裏。你已經走了一步到：

S0 -> S 
S -> ABA 
S -> BBB 
A -> BBBB 
A -> ABA 
A -> BB 
B -> c

如果我們採取的第一個S，並使用上述方法，我們得到：

S -> ABA 
//goes to 
S -> AC 
C -> BA

做的其餘規則，我們得到：

//second S 
S -> BD 
D -> BB 

//first A 
A -> DD 

//second A: 
A -> AC

結合這一切，我們得到：

S0 -> S 
S -> AC 
S -> BD 
A -> DD 
A -> AC 
A -> BB 
B -> c 
C -> BA 
D -> BB

來源

2015-03-13 22:54:31

如何在將CFG轉換爲CNF時做最後一步？

回答

相關問題