Why is this Grammar not context sensitive?

124 Views Asked by At

I have got this grammar:

G = (N, Epsilon, P, S)

with

N = {S, A, B}

Epsilon = {a},

P:    S -> e

      S -> ABA

      AB -> aa

      aA -> aaaA

      A -> a

Why is this a grammar of only type 0?

I think it is because of aA -> aaaA, but I don't see how it is in conflict with the rules.

The rules have to be built like this:

x1 A x2 -> x1 B x2 while:

A is element of N;

x1,x2 are elements of V*;

and B is element of VV*;

With V = N united Epsilon, I don't see the problem here.

a is from V, and A is from N, while right of A there could be the empty word, which would also be part of V*, so the left side would be okay.

On the right side, there is x1 again, being a, then we could say aaA is part of VV*, with aa being V and A being V*, while the right part is x2, so empty again.

1

There are 1 best solutions below

0
On

"The rules have to be built like this: x1 A x2 -> x1 B x2 while:...." yes, it's correct. But, exists an equivalent definition of the rules (of type-1 grammars): p->q where p,q is element of V^+ and length(p)<=length(q) and -naturally- p has an element of N. Your grammar has only rules, that satisfy this form => your grammar is type-1