0

鉴于此 CFG

 S->A|t|pCq
 S->B|r|^
 A->C|q|BA
 C->S|p|^
 B->m

我尝试转换为 CNF

首先删除 Null 产品，即 S->^ 和 C->^

所以删除后

S->A|t|pCq
S->B|r
A->C|q|BA
C->S|p
B->m

现在删除单位产品，即 S->B、A->C、S->A 和 C->S

 S->B gives S->m using B->m

 A->C gives A->p using C->p

 S->A gives S->q|BA using  A->q|BA 

 C->S gives C->t|pCq|r using S->t|pCq

所以添加这些产品

S->t|pCq|q|BA

S->r|m

A->q|BA|p

C->p|t|pCq|r

其中 K->q,U->p

CNF 中所需的 CNG 是

S->t|UCK|q|BA

S->r|m

A->K|BA|U

C->U|t|UCK|r

R->UC

S->t|RK|q|BA

S->r|m

A->K|BA|U

C->U|t|RK|r

R->UC 

K->q

U->p

这是正确的吗？

4

1 回答 1

0

  1. 删除 Null 产品。一些定义允许 S 有一个空产品，你错误地删除了 C 产品。您应该通过将 C 替换为 null 来为 RHS 中具有 C 的每个产品创建另一个产品。

    S->A|t|pCq|pq
S->B|r
A->^|q|BA
C->S|p
B->m

    注意：在处理 C->^ 之后，当您移动到 ​​S->^ 时，您不会添加另一个 C->^ 产生式，因为它已经被处理过。但是必须添加 A->^ (A->C & C->^)。

  2. 删除 A -> ^ 产生式

    S->A|t|pCq|pq
S->B|r
A->B|q|BA
C->S|p
B->m

  3. 删除 A->B 和 S->B

    A->m|q|BA
S->A|m|t|r|pCq|pq

  4. 删除 C->S

    C->A|p|m|t|r|pCq|pq

    请注意，由于 S->A 尚未处理，因此 A 也是如何添加的（首先更容易处理它，我只是在演示一个观点）

  5. 删除 C->A

    C->q|p|m|t|r|pCq|pq|BA

  6. 删除 S->A

    S->q|m|t|r|pCq|pq|BA

  7. 最终 S->m|r|q|t|pCq|pq|BA A->m|q|BA C->m|p|q|t|r|pCq|pq|BA B->m

  8. 转换为 CNF

    P->p
Q->q
X->CQ
S->m|r|q|t|PX|PQ|BA
A->m|q|BA
C->m|p|q|t|r|PX|PQ|BA
B->m

可选的：

S->^

编辑：哎呀。我犯了一个错误。忘记添加 C->r。对不起^^'

于 2014-12-05T13:08:04.947 回答