Reputation: 21
Given {a^(n+m) | n>= 2m}
, state whether it is regular, context free, or not context free and prove it using DFA, CFG, ...
My answer: it's not context free because there is no way to represent n>=2m. The greater than sign is too ambiguous.
I'm wondering if my answer is correct.
Upvotes: 1
Views: 309
Reputation: 3592
Your answer is *in*correct, since a^(n+m) == a^([2m+k]+m) == a^(3m+k) where m, k >= 0. CFG representing such language is as follows:
S->LR;
R->Ra|a;
L->LL|aaa;
Upvotes: 1