Здравствуйте, mefrill, Вы писали:

M>Понятно, что напрямую писать 600 символов -- это надо иметь 600 переходов и соответствующие состояния. Для минимизации количества состояний и переходов можно использовать тот факт, что число 600 -- составное и равно 2*2*2*5*5*3. Соответственно, надо сначала записать два символа a, затем два раза помножить эту запись на два, затем два раза помножить результат на 5, и затем помножить результат на три. Лучше конечно делать это в порядке возрастания множителей, т.е. сначала 2, потом 3, а уже потом 5. Левую звездочку можно использовать как начала записи влево количества на что умножаем.

Да, кстати! Блестящая идея.
Её можно развить — не факторизовывать число (а если бы оно было простым?), а разложить в двоичной системе счисления.
600 = 1001011000b
Нам нужны 9 групп правил, удваивающих строку, и 4 правила, дописывающих одиночную букву в хвост.

Про блеск поговорили, теперь про нищету.
Вопрос: сколько времени потратит что твоя, что моя машина? Вынужденная мотаться вдоль однеричной записи, удваивая, а то и упятеряя её?

И сравни с машиной, которую я предложил здесь

Автор: Кодт
Дата: 15.05.08

.