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

Question

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

G = (N, Epsilon, 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 is from V, а A - от N, а справа от A может быть пустое слово, которое также будет частью V *, поэтому левая сторона будет в порядке.

С правой стороны есть x1 снова, будучи а, тогда мы могли бы сказать, что aaA является частью VV *, причем aa является V, а A - V *, а правая часть - x2, поэтому пустая снова.

Answer 1

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