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 に答える