Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика

Ясно, что удалив первый символ слова, надо тут же остановиться. Поэтому, казалось бы, задачу решает следующий НАМ:

Однако это неправильный алгоритм, в чем можно убедиться, применив его к слову bbaba:

Как видно, этот НАМ удалил не первый символ слова, а первое вхождение символа a, а это разные вещи. Данный алгоритм будет правильно работать, только если входное слово начинается с символа a. Ясно, что перестановка формул в этом НАМ не поможет, т.к. тогда он будет, напротив, неправильно работать на словах, начинающихся с a.

Что делать? Надо как-то зафиксировать, пометить первый символ слова, например, поставив перед ним какой-либо знак, скажем *, отличный от символов алфавита слова. После этого уже можно с помощью формул вида *ξ a заменить этот знак и первый символ ξ слова на пусто и остановиться: bbaba → *bbaba → baba

А как поставить * перед первым символом? Это реализуется формулой →* с пустой левой частью, которая, по определению, приписывает свою правую часть слева к слову.

Итого, получаем следующий НАМ:

Проверим его на том же входном слове:

Как видно, этот алгоритм постоянно приписывает слева звездочки. Почему? Напомним, что формула постановки с пустой левой частью применима всегда, поэтому наша формула (1) будет работать бесконечно, блокируя доступ к ос­тальным формулам. Отсюда вытекает очень важное правило: если в НАМ есть формула с пустой левой частью ( →β), то ее место - только в самом конце НАМ. Учтем это правило перепишем наш НАМ:

Вот теперь мы, наконец-то, составили правильный алгоритм.

Прежде чем перейти к следующим задачам, обобщим тот прием со звездочкой, который мы использовали в примере 3.

Пусть в обрабатываемое слово Р входит несколько раз подслово α:

и нам надо заменить одно из вхождений α на подслово β. Такая замена делается с помощью формулы α →β. Однако, если мы применим эту формулу к слову Р, то будет заменено первое вхождение α. А что делать, если надо заменить какое-другое вхождение α, скажем второе или последнее? Так вот, чтобы на β заменялось не первое вхождение α, а какое-то другое, это другое вхождение надо как-то выделить, пометить, для чего следует рядом с ним (слева или справа) поставить некоторый символ, скажем *, отличный от всех других символов, входящих в P:

Такой символ будем в дальнейшем называть спецзнаком. Его роль - вы­делить нужное вхождение α среди других, сделать его уникальным. Поскольку только около этого вхождения есть спецзнак, то надо использовать формулу *α →β, чтобы заменить на β именно это вхождение α, а не какое-то другое.

Этот прием со спецзнаком следует запомнить, т.к. в НАМ он используется очень часто.

Правда, остается еще одна проблема: как спецзнак разместить рядом с нужным вхождением α. Следующие примеры показывают, как это делается.