Решил задачу, хочу сверить ответ:
Дана грамматика языка:
G = ( {a}, {S, N, Q, R}
{ S->QNQ,
QN->QR,
RN->NNR,
RQ->NNQ,
N->a
Q-> epsilon (пустая строка) }, S (аксиома))
Нужно доказать, что с помощью данной грамматики можно получить слова длиной:
а) равной любой степени двойки
б) слова другой длины кроме степени двойки получить нельзя
Примеры получения слов (2^0 и 2^1):
S=>QNQ=>a
S=>QNQ=>QRQ=>QNNQ=>aa
и т.д.