Как из удвоения слова получить утроение? (алгоритм Маркова)

[Pavel_08]

Доброго времени суток.

Изучая нормальные алгоритмы Маркова, возник следующий вопрос:
Имеется пример, в рамках которого мы удваиваем заданное слово:



Здесь \alpha - это курсор, копия каждой буквы помечается \beta .
Как правильно 'модифицировать' алгоритм, чтобы вместо удвоения слова получить утроение?

Благодарю.

[popolznev]

А из какой это книжки скриншот?

[Pavel_08]

Методичка МГТУ.
https://goo.gl/jWvI7T

[arseniiv]

Ну, например, первую серию правил можно превратить во что-то типа $\alpha\xi\to\xi\beta\xi\gamma\xi\alpha,\;\xi\in V$, и дальше, может быть, $\gamma$ можно будет заменить тут на $\beta$, но поначалу эта возможность неочевидна.

[Pavel_08]

$\mathbf{\boldsymbol{}}$То есть в принципе, возможное решение выглядит так, верно?

$\alpha$$\xi$ $\to$ $\xi$$\beta$$\xi$$\gamma$$\xi$$\alpha$, $\xi $\in$ V
$\beta$$\xi$$\eta$ $\to$ $\eta$$\beta$$\xi$,      $\eta$, $\xi$ $\in$ V
$\gamma$$\xi$$\eta$ $\to$ $\eta$$\gamma$$\xi$,      $\eta$, $\xi$ $\in$ V
$\beta$ $\to$
$\gamma$ $\to$
$\alpha$ $\to$ $\cdot$
$\to$ $\alpha$

Или здесь имеется ошибка?

[arseniiv]

Я вот так сразу не скажу, стоит прогнать его на примерах. Возьмите, например, строку из двух разных символов (на одном явно будет непонятно, правильно переставляются символы или нет, а три — это уже сложнее и потом). (Кстати говоря, можно написать интерпретатор алгоритмов Маркова, чтобы сильно не мучиться.)

[Pavel_08]

Кхм, не подскажете, как правильно задать алгоритм для разных символов?
На странице эмулятора я указал алгоритм для схожих символов, который задается как:

*x->xxx*
*=>
->*

Как правильно будет проверить слово вида 'abc'?

[arseniiv]

Т. к. этот пример утраивает только слова из символов $x$, на $abc$ он просто почти сразу завершится: $abc\vdash {*}abc\vdash\mathrel{\cdot} abc$. А ваш алгоритм записывается практически как есть, надо только учесть, что «правила» вида $A\to B, \xi\in V$ — это наборы правил $A\to B$, где $\xi$ заменяется разными символами из $V$. Так что ваш алгоритм там кодируется как

Aa -> aBaCaA
Ab -> bBbCbA
Ac -> cBcCcA
Baa -> aBa
Bba -> aBb
Bca -> aBc
Bab -> bBa
Bbb -> bBb
Bcb -> bBc
Bac -> cBa
Bbc -> cBb
Bcc -> cBc
Caa -> aCa
Cba -> aCb
Cca -> aCc
Cab -> bCa
Cbb -> bCb
Ccb -> bCc
Cac -> cCa
Cbc -> cCb
Ccc -> cCc
B ->
C ->
A =>
-> A

и это не влезает в ограничения эмулятора. (Вообще не понимаю, зачем такие сильные — 20 правил и 500 шагов.) Если выкинуть все правила, содержащие $c$, то для строк в алфавите $\{a,b\}$ работает.

[Pavel_08]

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

[arseniiv]

Я вот тут написал простенький интерпретатор на Ceylon, где алгоритм Маркова задаётся DSL’ом внутри этого языка. Можно менять его в коде, а потом запускать и смотреть, что получается. Состояния строки выводятся попеременно с применявшимися правилами.

[Pavel_08]

Действительно, возможности для тестирования алгоритмов здесь намного шире.
Еще раз, Большое спасибо.