問題タブ [chomsky-hierarchy]

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

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

と

なぜこれはタイプ 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 であるため、再び空です。

さまざまなレベルのチョムスキー階層を理解しようとしています。

私はいくつかの例をチェックしましたが、ここに私が本当に理解していないものがあります。これが文脈依存言語ではない理由を誰かが知っているかもしれません:

再帰的に列挙可能な文法には制限がないため、LHS に 1 つ以上の終端がある (つまり、非終端がない) プロダクションを作成することは可能ですか?