Дифференциальная, неконтекстная и регулярная грамматика дифференциации

Question

Учитывая {a^(n+m) | n>= 2m}, указать, является ли он регулярным, контекстно-свободным или не контекстно-свободным, и доказать это с помощью DFA, CFG, ...

Мой ответ: он не является контекстно-свободным, потому что нет способа представить n> = 2m. Знак больше чем слишком двусмысленный.

Мне интересно, правильный ли мой ответ.

Answer 1

Ваш ответ * в * правильный, поскольку a ^ (n + m) == a ^ ([2m + k] + m) == a ^ (3m + k), где m, k> = 0. CFG, представляющий такой язык, выглядит следующим образом:

 S->LR;
 R->Ra|a;
 L->LL|aaa;