4.4. Натуральные алгоритмы. Порождение первичных алгоритмов

В § 2.5 дано общее определение операции. Однако из всех операций нам пока известны только натуральные, которые являются операциями только над словами и квазисловами. Язык L₂ построен нами из конечного числа морфем при помощи последовательно выполняемых операций сцепления слов.

Введем обозначения еще двух натуральных операций: "*" - нахождение начала и "→" - продвижение вправо.

Теперь нетрудно определить формальный язык, предложениями которого будут всевозможные слова и квазислова в алфавите А₁. Чтобы не говорить только об одном конкретном алфавите, считаем метасимвол <буква> заданным. Формальная грамматика нового языка в этом случае имеет вид.

Правая часть первой метаформулы опущена. Скобки в правой части четвертой метаформулы служат для указания границ аргументов. Наличие среди синтаксических правил четвертой метаформулы не позволяет считать формальную грамматику заданной с помощью нотации Бекуса. Пользуясь операциями линеаризации и делинеаризации, можно было бы задать еще более сложные языки.

Вернемся к изучению первичных алгоритмов. Семейство первичных алгоритмов, в котором используются только операции из числа натуральных, принадлежит подклассу первичных алгоритмов, называемых натуральными алгоритмами.

Построим теперь конкретный алгоритмический язык, для чего доопределим грамматику языка первичных алгоритмов, приведенного в предыдущем параграфе. Будем считать, что алфавит А₂ этого языка содержит все буквы в А₁ и, кроме того, в него включены дополнительные буквы, которые читатель легко найдет, если просмотрит нижеприведенные метаформулы. Произвольную букву в А₁ будем обозначать метасимволом <α>.

Между знаками операций и самими операциями установим следующее соответствие (табл. 4.1.).

Таблица 4.1. Соответствие между знаками операций и операциями

В качестве упражнения построим алгоритм нахождения конца слова в определенном нами семействе натуральных алгоритмов. Его запись может иметь вид:

1. Δ ? 2 / 1 ;
2. *, 3 ;
3. k ? стоп / 4 ;
4. →, 3 ;

В этой записи (исключительно для наглядности) мы расположили приказы в виде столбца. Можно было бы их написать в виде одной строки и это не уменьшило бы понятности алгоритма для того, кто знает правило выполнения (см. с. 63). Первый приказ гласит: если преобразуемое слово непусто, то перейти к приказу 2, а иначе снова к приказу 1. Значит, если слово пусто, то сдвинуться с приказа 1 невозможно. Это значит, что к пустому слову наш алгоритм неприменим. Это естественно, так как пустое слово не имеет конца.

Приказ 2 предписывает найти начало преобразуемого слова (т. е. превратить его в квазислово) и перейти к приказу 3; приказ 3 - проверить, является ли выделенная буква концом, и если да, прекратить процесс. Если же выделенная буква еще не конец, то по приказу 4 нужно продвинуться вправо и снова вернуться к приказу 3 и т. д. В конце концов необходимое преобразование будет выполнено.

Составив такой алгоритм, мы можем выполняемое им преобразование объявить операцией. Обозначим ее "**".

Составим еще натуральный алгоритм, который проверял бы, является ли рассматриваемое слово однобуквенным? Его запись может иметь вид

1. Δ ? 2 / нет ;
2. *, 3 ;
3. k ? 4 / 5 ;
4. ×, да ;
5. ×, нет ;

Этот алгоритм я умышленно записал в виде одного слова. Он кончает свою работу по-разному в зависимости от того, является ли слово однобуквенным или нет. Если слово однобуквенное, то процесс окончится выполнением приказа, имеющего отсылку "да", а если не однобуквенное - выполнением приказа, имеющего отсылку "нет". Получив его, мы можем объявить новую логическую операцию: проверку однобуквенности. Обозначим ее, например, "б".

Алгоритм, который бы проверял, является операнд словом или квазисловом, можно составить, только используя операции линеаризации и делинеаризации. В этом случае необходимы дополнительные буквы для обозначения связей, их ветвей и нумерации. Они не должны входить в алфавитех языка исходных данных, но должны использоваться операциями d и l и входить в алфавит, над которым определены остальные натуральные операции. Предположим, что для обозначения связей нами избраны буквы Н, П, К, В (соответственно для начинающей, продолжающей, заканчивающей и выделяющей связей), для пометки их ветвей - Г и Д (соответственно первого и второго жанра) и буква I для нумерации связей и ветвей. Это заставило бы нас изменить самую первую метаформулу:

Искомый натуральный алгоритм может иметь запись:

1. l, 2 ;
2. Δ / 3 / да ;
3. *, 4 ;
4. = B ? 5 / 7 ;
5. ×, 6 ;
6. d, нет ;
7. k ? 9 / 8 ;
8. →, 4 ;
9. ×, 10 ;
10. d, да ;

Приказ 1 применим к любой конструкции языка исходных данных Он предписывает линеаризацию операнда. Приказ 2 проверяет непустоту результата линеаризации. Если он пуст, то исходное данное было пустой конструкцией, т. е. словом, так как квазислова пустыми не бывают. Этому случаю отвечает отсылка "да". Если он непуст, нужна дальнейшая проверка. Приказ 3 выделяет начало результата линеаризации. Приказ 4 проверяет, содержится ли в результате линеаризации буква A, являющаяся именем выделяющей связи. Приказы 7 и 8 обеспечивают просмотр результата линеаризации, так как буква В может стоять и не в начале операнда. Если оказывается, что буквы и вообще нет (значит, исходное данное было словом), то приказы 9 и 10 производят делинеаризацию (т. е. придают операнду вид исходного данного Белова) и завершаются отсылкой "да"). Если В будет найдена, то приказы 5 и 6 производят делинеаризацию, чтобы вернуть операнду его исходный вид (вид квазислова) и завершаются отсылкой "нет". Читатель сам понял, почему пустой результат линеаризации не нужно было делинеаризировать - потому что делинеаризация его не изменяет (см. приказ 2).

Последний алгоритм позволяет объявить еще одну логическую операцию, что мы и сделаем. Обозначим ее s.

Расширив набор операций, мы можем построить новое семейство первичных алгоритмов, добавив к грамматике алгоритмического языка метафор-мулы:

При этом нужно изменить и правило выполнения так, чтобы оно обеспечивало выполнение новых операций. У нас это правило сформулировано в общем виде и потому его изменение будет неявным.

Новые алгоритмы уже не будут натуральными (так как используют три новые операции, не являющиеся натуральными).