2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



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


09/01/17
7
Доброго времени суток.

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

Изображение

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

Благодарю.

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


14/10/13
339
А из какой это книжки скриншот?

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 09:04 


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

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 15:26 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 16:06 


09/01/17
7
$\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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 16:48 


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

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

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

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 17:17 
Заслуженный участник


27/04/09
28128
Т. к. этот пример утраивает только слова из символов $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 


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

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение10.01.2017, 20:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Как из удвоения слова получить утроение? (алгоритм Маркова)
Сообщение11.01.2017, 09:10 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group