Lexy Yang
Lexy Yang

Reputation: 21

Context-free, not-context-free, and regular grammars differentiation

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

Answers (1)

iehrlich
iehrlich

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

Related Questions