В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач (1000390), страница 5
Текст из файла (страница 5)
Эти номера не входят в формулы, а нужны для ссылок на формулыпри показе пошагового выполнения НАМ.Пример 1 (вставка и удаление символов)А={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на dddи удалить все вхождения символа c.Например: abbcabbca → adddabbaРешение.Прежде всего отметим, что в НАМ, в отличие от машины Тьюринга, легкореализуются вставки и удаления символов. Вставка новых символов в слово –это замена некоторого подслова на подслово с бóльшим числом символов;например, с помощью формулы bb→ddd два символа будут заменены на трисимвола. При этом не надо заботиться о том, чтобы предварительно освободитьместо для дополнительных символов, в НАМ слово раздвигается автоматически.
Удаление же символов – это замена некоторого подслова на подслово сменьшим числом символов; например, удаление символа c реализуетсяформулой c→ (с пустой правой частью). При этом никаких пустых позицийвнутри слова не появляется, сжатие слова в НАМ происходит автоматически.С учётом сказанного нашу задачу должен, казалось бы, решать такой НАМ:⎧ bb → ddd (1)⎨c →( 2)⎩Однако это не так. Проверим этот НАМ на входном слове abbcabbca (над стрелкамиуказаны номера применённых формул, а в словах слева от стрелок подчёркнуты длянаглядности те части, к которым были применены эти формулы):112abbcabbca → adddcabbca → adddcadddca → adddabbca → …21Как видно, заменив первое вхождение bb на ddd, этот НАМ не перешёл сразу кудалению символов c, а стал заменять и другие вхождения bb.
Почему?Напомним, что на каждом шаге работы НАМ формулы подстановки всегдапросматриваются сверху вниз начиная с первой из них. Поэтому, покаприменима первая формула, она и будет применяться, блокируя доступ костальным формулам. Этот означает, что в НАМ важен порядок перечисленияформул подстановки.Учтём это и переставим наши две формулы:(1)⎧c →⎨ bb → ddd (2)⎩Проверим этот новый алгоритм на том же входном слове:1122abbcabbca → abbabbca → abbabba → adddabba → adddadddaИтак, НАМ сначала удалил все символы c и только затем заменил первое вхождениеbb на ddd. Однако НАМ на этом не остановился и стал заменять остальныевхождения bb. Почему? Дело в том, что, пока применима хотя бы одна формула,НАМ продолжает свою работу. Но нам этого не надо, поэтому мы должныпринудительно остановить НАМ после того, как он заменил первое вхождение bb.Вот для этого и нужны заключительные формулы подстановки, после применениякоторых НАМ останавливается.
Следовательно, в нашем алгоритме обычнуюформулу bb→ddd надо заменить на заключительную формулу bb a ddd:(1)⎧c →⎨ bb a ddd( 2)⎩Вот теперь наш алгоритм будет работать правильно:112abbcabbca → abbabbca → abbabba a adddabbaСлово, которое получилось после применения заключительной формулы (2),является выходным словом, т.е.
результатом применения НАМ к заданномувходному слову.Проверим наш НАМ ещё и на входном слове, в которое не входит bb:11dcacb → dacb → dabК последнему слову (dab) неприменима ни одна формула, поэтому, согласноопределению НАМ, алгоритм останавливается и это слово объявляется выходным.Пример 2 (перестановка символов)А={a,b}. Преобразовать слово Р так, чтобы в его начале оказались все символыa, а в конце – все символы b.Например: babba → aabbbРешение.Казалось бы, для решения этой задачи нужен сложный НАМ. Однако этоне так, задача решается с помощью НАМ, содержащего всего одну формулу:22{ ba → abПока в слове P справа хотя бы от одного символа b есть символ a, эта формулабудет переносить a налево от этого b. Формула перестает работать, когда справаот b нет ни одного a, это и означает, что все a оказались слева от b.
Например:babba → abbba → abbab → ababb → aabbbАлгоритм остановился на последнем слове, т.к. к нему уже неприменима нашаформула.Этот и предыдущий примеры показывают, что в НАМ, в отличие от машиныТьюринга, легко реализуются перестановки, вставки и удаления символов. Однако вНАМ возникает другая проблема: как зафиксировать символ (подслово), которыйдолжен быть обработан? Рассмотрим эту проблему на следующем примере.Пример 3 (использование спецзнака)А={a,b}. Удалить из непустого слова Р его первый символ.
Пустое слово неменять.Решение.Ясно, что удалив первый символ слова, надо тут же остановиться.Поэтому, казалось бы, задачу решает следующий НАМ:(1)⎧aa⎨ba( 2)⎩Однако это неправильный алгоритм, в чём можно убедиться, применив его кслову bbaba:1bbaba a bbbaКак видно, этот НАМ удалил не первый символ слова, а первое вхождениесимвола a, а это разные вещи. Данный алгоритм будет правильно работать,только если входное слово начинается с символа a. Ясно, что перестановкаформул в этом НАМ не поможет, т.к. тогда он будет, напротив, неправильноработать на словах, начинающихся с a.Что делать? Надо как-то зафиксировать, пометить первый символ слова,например, поставив перед ним какой-либо знак, скажем *, отличный отсимволов алфавита слова.
После этого уже можно с помощью формул вида*ξ a заменить этот знак и первый символ ξ слова на пусто и остановиться:bbaba → *bbaba a babaА как поставить * перед первым символом? Это реализуется формулой →*с пустой левой частью, которая, по определению, приписывает свою правуючасть слева к слову.Итого, получаем следующий НАМ:→ * (1)⎧⎪( 2)⎨ *a a⎪⎩ * b a(3)Проверим его на том же входном слове:231111bbaba → *bbaba → **bbaba → ***bbaba → …Как видно, этот алгоритм постоянно приписывает слева звёздочки. Почему?Напомним, что формула постановки с пустой левой частью применима всегда,поэтому наша формула (1) будет работать бесконечно, блокируя доступ к остальным формулам.
Отсюда вытекает очень важное правило: если в НАМ естьформула с пустой левой частью (→β), то её место – только в самом конце НАМ.Учтём это правило и перепишем наш НАМ:(1)⎧ *a a⎪*(ba2)⎨⎪⎩→ * (3)Проверим данный алгоритм:32bbaba → *bbaba a babaКазалось бы, всё в порядке. Однако это не так: наш алгоритм зациклитсяна пустом входном слове, т.к. постоянно будет применяться формула (3), асогласно условию задачи на таком слове НАМ должен остановиться.
В чём причина этой ошибки? Дело в том, что мы ввели знак * для того, чтобы пометитьпервый символ слова, а затем уничтожить * и этот символ. Но в пустом словенет ни одного символа, поэтому формулы (1) и (2) ни разу не сработают и постоянно будет выполняться формула (3). Следовательно, чтобы учесть случайпустого входного слова, надо после формул (1) и (2) записать ещё одну формулу, которая уничтожает «одинокую» звёздочку и останавливает алгоритм:(1)⎧ *a a⎪ *b a( 2)⎨ * a(3)⎪→ * ( 4)⎩Вот теперь мы, наконец-то, составили правильный алгоритм.Прежде чем перейти к следующим задачам, обобщим тот приём созвёздочкой, который мы использовали в примере 3.Пусть в обрабатываемое слово Р входит несколько раз подслово α :P…α…α…α…и нам надо заменить одно из вхождений α на подслово β.
Такая замена делаетсяс помощью формулы α→β. Однако, если мы применим эту формулу к слову Р,то будет заменено первое вхождение α. А что делать, если надо заменить какоедругое вхождение α , скажем второе или последнее? Так вот, чтобы на βзаменялось не первое вхождение α , а какое-то другое, это другое вхождениенадо как-то выделить, пометить, для чего следует рядом с ним (слева илисправа) поставить некоторый символ, скажем *, отличный от всех другихсимволов, входящих в P:P…α…*α…24α…Такой символ будем в дальнейшем называть спецзнаком. Его роль – выделить нужное вхождение α среди других, сделать его уникальным.
Посколькутолько около этого вхождения есть спецзнак, то надо использовать формулу*α→β, чтобы заменить на β именно это вхождение α , а не какое-то другое.Этот приём со спецзнаком следует запомнить, т.к. в НАМ он используетсяочень часто.Правда, остаётся ещё одна проблема: как спецзнак разместить рядом снужным вхождением α ? Следующие примеры показывают, как это делается.Пример 4 (фиксация спецзнаком заменяемого символа)А={0,1,2,3}. Пусть Р – непустое слово.
Трактуя его как запись неотрицательногоцелого числа в четверичной системе счисления, требуется получить запись этого же числа, но в двоичной системе.Например: 0123 → 00011011Решение.Как известно, для перевода числа из четверичной системы в двоичнуюнадо каждую четверичную цифру заменить на пару соответствующих ей двоичных цифр: 0→00, 1→01, 2→10, 3→11. Такая замена, казалось бы, реализуетсяследующим НАМ:⎧ 0 → 00 (1)⎪ 1 → 01 (2)⎨ 2 → 10 (3)⎪⎩ 3 → 11 (4)Но этот алгоритм неправильный, в чём можно убедиться на входном слове 0123:1110123 → 00123 → 000123 → …Ошибка здесь в том, что после замены четверичной цифры на парудвоичных цифр уже никак нельзя отличить двоичные цифры от четверичных,поэтому наш НАМ начинает заменять и двоичные цифры. Значит, надо как-тоотделить ту часть числа, в которой уже была произведена замена, от той части,где замены ещё не было.
Для этого предлагается пометить слева спецзнаком *ту четверичную цифру, которая сейчас должна быть заменена на пару соответствующих двоичных цифр, а после того как такая замена будет выполнена,спецзнак нужно поместить перед следующей четверичной цифрой:0123 → *0123 → 00*123 → 0001*23 → 000110*3 → 00011011*Как видно, слева от спецзнака всегда находится та часть числа, которая уже переведена в двоичный вид, а справа – часть, которую ещё предстоит заменить. Поэтомуникакой путаницы между четверичными и двоичными цифрами уже не будет.Итак, спецзнак * сначала должен быть размещён слева от первой цифрычетверичного числа, а затем он должен «перепрыгивать» через очередную четверичную цифру, оставляя слева от себя соответствующие ей двоичные цифры.В конце же, когда справа от * уже не окажется никакой цифры, спецзнак надо25уничтожить и остановиться.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
