如何在将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时做最后一步？

回答

相关问题