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.
"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