0

鉴于：

    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

我不确定如何继续。

4

1 回答 1

0

没有适合您的第 2 步。第 2 步是删除 epsilon 规则，而您没有 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
于 2015-03-13T22:54:31.810 回答