Почему эта грамматика не зависит от контекста?

Question

Я получил эту грамматику:

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 в то время как:

А является элементом 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, поэтому снова пусто.

Answer 1

"Правила должны быть построены так: x1 A x2 -> x1 B x2 while:...." да, это правильно. Но существует эквивалентное определение правил (грамматик типа 1): p->q, где p, q является элементом V^+, а length(p)<=length(q) и -naturally- p имеет элемент из N. Ваша грамматика имеет только правила, которые удовлетворяют этой форме => ваша грамматика типа 1