Какова будет грамматика для данного языка?

Question

[Sneiksus]

Часть с буквами это обычная контекстная грамматика типа S->aSBBBC
цифры же могут генерироваться с помощью безконтекстных правил.
Как это все совместить в одну грамматику?

Comments

[Mercury13]

Что такое 0'1? Или это 0^i? И какой индекс у последней единицы?

[Mercury13]

Касательно грамматики S → aSBBBC. Ну применим ещё раз, будет aaSBBBCBBBC. Как дальше раскрывать?

Answer 1

[Mercury13]

L → EZUU M ZUUUUF
M → ZUU M ZUUUU | S
Для S грамматику вы уже придумали.
Затем — не буду расписывать, они многословны, но просты — UZ → ZU

А чтобы превратить Z в 0 и U в единицу, если i,n ∊ N+…
Сделаем затравку…
EZ → E0
Ua → 1a
cZ → c0
UF → 1F
…Уничтожим технические нетерминалы…
E0 → 0
1F → 1
…И проведём волну!
0Z → 00
U1 → 11

Вроде так.
(Z = zero, U = unit)