将 CFG 转换为 CNF 时，最后一步如何执行？

Question

鉴于：

    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

我不确定如何继续。

Answer 1

没有适合您的第 2 步。 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

但是，抛开上面的内容，因为首先我要将所有 cs 更改为 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

将 CFG 转换为 CNF 时，最后一步如何执行？

How do you do the last step when converting a CFG to a CNF?

context-free-grammar

chomsky-normal-form