Нормальные алгорифмы Маркова

Советский ученый А. А. Марков избрал другой путь уточнения понятия алгоритма. Им разработана строгая теория класса алгоритмов, которые он назвал нормальными алгорифмами.

Нормальные алгорифмы в качестве исходных данных и искомых ре­зультатов имеют, подобно машинам Тьюринга, строки букв – слова. Предположим, что заранее выделен некоторый алфавит. Обозначим его А. Букву, одинаковую с одной из букв, входящих в алфавит А, называ­ют буквой в А. Слово, состоящее из букв в А, называют словом в А. При этом для удобства рассуждений допускают и пустые слова (не имеющие в своем составе ни одной буквы).

Если А и В – два алфавита, причем каждая буква алфавита А является буквой в В, а хотя бы одна из букв алфавита В не является буквой в Л, то 5 называется расширением алфавита А. Например, если А - {а, б, в, г), В={1, а, б, в, г, д}, то В являегся расшире­нием А, так как содержит две буквы («1» и «д»), не являющиеся буквами в А, тогда как все буквы алфавита А являются буквами в В. Рассмотрим какое-либо конкретное слово для определенности в алфа­вите русских букв, например слово «самолет». Мы видим, что из него можно вырезать подслова, например «сам», «амол» или «олет», или «лет», или, наконец, однобуквеиное слово «т». Про такие подслова говорят, что они входят в рассматриваемое слово или являются вхождениями в него. Заметим, что в наше слово входит и пустое слово, причем — несколько раз (оно входит перед первой буквой, между каждыми двумя буквами и, нако­нец, после последней буквы, т. е., в данном случае, 8 раз).

Подслово - часть слова, буквы которого расположены рядом. Подсло­вом может быть и само слово.

Условимся обозначать слова заглавными латинскими буквами (если эти буквы не являются буквами в применяемом алфавите). Если задано не­которое слово и нами выбрана буква, являющаяся его обозначением (именем), то будем ставить между ними знак = (равенства). Возвращаясь к на­шему примеру, мы можем написать: для слова Я=самолет слово Р=амол является вхождением.

Заметим, что не только пустое слово может многократно входить в другое слово. Например, в слово Я=тарарам слово Р=ара входит два раза. Особый интерес для нас будет представлять так называемое первое вхож­дение.

Марковской подстановкой называется операция над словами, зада­ваемая с помощью пары слов (Р, Q), заключающаяся в следующем.

Если задано исходное слово R, то в нем находят первое вхождение сло­ва Р (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово является ре­зультатом применения марковской подстановки (Р, Q) к слову R. Если же нет первого вхождения Р в слово R (при этом нет вообще ни одного вхож­дения Р в R), то считается, что марковской подстановке слово R не подда­ется.

Частными случаями марковских подстановок являются (,Q), (Р,) и (,). В первом из приведенных примеров Р, во втором Q, а в третьем и Р, и Q являются пустыми.

Действие Марковской подстановки заключается в том, что в искомом слове ищется подслово слева направо, и как только находится, оно меня­ется на другое подслово. Если вхождений несколько, то при любой под­становке меняется только первое слева вхождение. Будем рассматривать слова в некотором алфавите А. Предположим, что символы «—»» и «.» не являются буквами в А. Запись Р-> Q и Р —. будем называть записями марковской подстановки (Р, Q), причем пер­вую из них будем называть подстановкой, а вторую - заключительной подстановкой.

Подстановки и заключительные подстановки будем называть форму­лами, различая в них левую часть Р и правую часть Q.

Марковская подстановка выполняется один раз, и если есть несколько вариантов, то выполняется подстановка, которая находится левее (ближе к началу слова). Марковская подстановка может быть успешной, неуспеш­ной и конечной. Успешной - если подстановка выполнена, неуспешной, если подстановку выполнить нельзя и конечной, если в начале слова-замены стоит ". " Ее назначение - прекращение дальнейшего процесса Марковских подстановок.

Записью нормального алгоритма в алфавите А называют столбец формул, левые и правые части которых являются словами в А. Выполне­ние нормального алгоритма применительно к исходному данному R, яв­ляющемуся словом в А, заключается в следующем: 1. Двигаясь по столбцу формул, ищут первую формулу, левая часть ко­
торой входит в преобразуемое слово. 2.Если такой формулы не найдется, процесс окончен. 3. Если же она найдется, то выполняют марковскую подстановку, соответствующую данной формуле, изменяя преобразуемое слово. 4. Затем смотрят, является ли выполненная подстановка заключительной. 5. Если она является заключительной, то процесс окончен. 6. В противном случае весь процесс повторяют с самого начала (то есть с пункта 1).

Этапы решения задач с помощью алгорифмов Маркова Для составления алгорифма Маркова необходимо задать: 1. алфавит для записи слов и, возможно, расширенный алфавит для
записи марковских преобразований (полученный путем добавления
дополнительных технических букв); 2.определение предложений и слов языка, на котором будут записы­
ваться данные и результаты.

Порядок действия алгорифма Маркова:

1) записывается последовательность марковских подстановок и зада­
ется слово, на которое должен действовать этот алгорифм.

2) проверяется возможность марковской подстановки (1). Если она
успешна, процесс повторяется, начиная с первой подстановки, если
неуспешна, то происходит переход к следующей подстановке. Если
подстановка конечна, то прекращаем работу алгорифма.

3) если в результате использования алгоритма будет произведена ко­
нечная подстановка или ни одна из подстановок не будет успеш­
ной, то алгорифм прекращает свою работу.

Результатом действия алгорифма Маркова может быть:

1) все подстановки неуспешны, мы получаем результат действия алго­рифма.

2) в процессе работы выполнена конечная подстановка, результат ра­боты есть.

3) алгорифм выполняется бесконечно.

Таким образом, результата действия алгорифма нет только при беско­нечном выполнении алгорифма, а если алгорифм совсем не меняет слово, то считается, что результат есть.

Говорят, что алгорифм применим к данному слову, если он дает ре­зультат для слова, и не применим к слову, если результата нет. Таким образом, у любого алгорифма существует множество слов, для которых он применим (область применимости) и множество слов, для которых он не применим (область неприменимости).

Замечание: поскольку алгорифм используется для построения словар­ных функций, то кроме применимости можно определить и правильность действия. Алгорифм правильно действует на слово, если он применим к этому слову и его результат совпадает с результатом словарной функции, которую он определяет.

Дата добавления: 2015-07-11