Теория автоматов, определить грамматику

[logonoff]

Есть такая задача: определить грамматику, дающую язык в котором слова - последовательности единиц, и их длины - простые числа.
Полистал учебники и пришел к выводу, что это контекстно-зависимый язык, и в наборе правил необходимо каким-то образом реализовать рекуррентный алгоритм нахождения простых чисел. А вот что дальше делать я не совсем понимаю, буду очень благодарен если натолкнете на ход решения.

[Профессор Снэйп]

logonoff в сообщении #412941 писал(а):

это контекстно-зависимый язык

Совершенно верно!

Думаю, проще всего запрограммировать машину, перечисляющую простые числа, а затем представить команды этой машины в виде правил грамматики.