2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 08:50 
Доброго времени суток.

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

Изображение

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

Благодарю.

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 08:57 
Аватара пользователя
А из какой это книжки скриншот?

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 09:04 
Методичка МГТУ.
https://goo.gl/jWvI7T

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 15:26 
Ну, например, первую серию правил можно превратить во что-то типа $\alpha\xi\to\xi\beta\xi\gamma\xi\alpha,\;\xi\in V$, и дальше, может быть, $\gamma$ можно будет заменить тут на $\beta$, но поначалу эта возможность неочевидна.

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 16:06 
$\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$

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

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

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 16:48 
Кхм, не подскажете, как правильно задать алгоритм для разных символов?
На странице эмулятора я указал алгоритм для схожих символов, который задается как:

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

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

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 17:17 
Т. к. этот пример утраивает только слова из символов $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\}$ работает.

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 17:30 
Да, согласен, далеко не каждый пример можно на данном эмуляторе разобрать.
В любом случае, идея для алгоритма оказалась вполне проста и понятна.
Большое Вам спасибо.

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 20:00 
Я вот тут написал простенький интерпретатор на Ceylon, где алгоритм Маркова задаётся DSL’ом внутри этого языка. Можно менять его в коде, а потом запускать и смотреть, что получается. Состояния строки выводятся попеременно с применявшимися правилами.

 
 
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение11.01.2017, 09:10 
Действительно, возможности для тестирования алгоритмов здесь намного шире.
Еще раз, Большое спасибо.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group