0

私はこの文法を持っています：

G = (N、イプシロン、P、S)

と

N = {S, A, B}

Epsilon = {a},

P:    S -> e

      S -> ABA

      AB -> aa

      aA -> aaaA

      A -> a

なぜこれはタイプ 0 のみの文法なのですか?

のせいだと思いますがaA -> aaaA、ルールに抵触する様子がわかりません。

ルールは次のように構築する必要があります。

x1 A x2 -> x1 B x2 その間：

A は N の要素です。

x1、x2 は V* の要素です。

B は VV* の要素です。

ではV = N united Epsilon、ここに問題はありません。

a は V に由来し、A は N に由来しますが、A の右側には空の単語が存在する可能性があり、これは V* の一部でもあるため、左側は問題ありません。

右側にも x1 があり、a であるため、aaA は VV* の一部であり、aa は V で A は V* であると言えますが、右側の部分は x2 であるため、再び空です。

4

1 に答える 1

0

「ルールは次のように構築する必要があります: x1 A x2 -> x1 B x2 while:....」 はい、正しいです。ただし、(タイプ 1 文法の) ルールの同等の定義が存在します: p->q ここで、p,q は V^+ の要素であり、length(p)<=length(q) であり、-当然- p には要素があります。あなたの文法には、このフォームを満たす規則のみがあります => あなたの文法はタイプ 1 です

于 2016-03-04T22:16:33.573 に答える