§ 1. Что такое операция?

В предыдущей главе, при определении понятия формаль­ной грамматики, было использовано понятие операции, а в параграфе, посвященном нотации Бекуса, применялись конкретные операции: операции соединения слов.

Понятие операции тесно связано с понятием алгоритма, и поэтому следует считать, что в гл. 7 мы «забежали» впе­ред. В этом нет беды. Можно считать, что мы пока условно определили понятие формальной грамматики (а значит, и порождаемого ею языка). После точного разъяснения смысла слова «операция» станет точным и строгим это «ус­ловное» определение.

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

и слова «алгоритм».

Итак, что же такое операция? Исходным данным для операции может быть либо отдельная конструкция (при этом говорят, что операция имеет первый ранг), либо на­бор, образованный из конструкций (в этом случае говорят, что операция имеет ранг г). Принято считать, что каждая операция имеет постоянный, всегда один и тот же ранг. Кроме того, положим, что операция однозначна. Каждому исходному данному она ставит в соответствие единственный

определенный результат.

Мы будем допускать два вида операций: простейшие, основные операции, определение которых не входит в ком­петенцию теории алгоритмов, и более сложные, «производ­ные» операции, получаемые методами теории алгоритмов. Простейшие операции назовем натуральными. Каждая из них должна быть тщательно разъяснена. Понятие про­изводной операции свяжем с расширенным понятием алго­ритма.

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

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

Объявление новой операции является абстрактным ана­логом следующей конкретной ситуации. В реальной жизни очень часто, имея некоторую машину, разрабатывают для нее определенную программу. При эксплуатации этой программы убеждаются, что ее приходится очень часто применять. Тогда разрабатывают новую ЭВМ, в которой ранее полученная для старой ЭВМ программа реализована уже аппаратурно и новой машиной выполняется за один такт. Еще один убедительный пример объявления новой операции в реальной практической области приведем поз­же, когда познакомимся с математическим обеспечением ЭВМ.

§ 2. Натуральные операции

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

К первой группе отнесем натуральные операции, исход­ными данными для которых являются слова или наборы слов, а результатами — отдельные слова. Группу этих операций назовем группой слово-слово.

В эту группу войдут четыре следующие операции.

1. Аннигиляция. Сущность аннигиляции состоит в том, что если ее применить к однобуквенному слову, то в качестве результата будет получено пустое слово. К мно­гобуквенным словам эту операцию применить нельзя. Для таких исходных данных она не определена и никакого ре­зультата не дает. Для обозначения аннигиляции введем знак .

2. Генерация противоположна аннигиляции. Эта операция применима к пустому слову и в качестве резуль­тата дает однобуквенное слово. Но различных однобуквенных слов столько же, сколько различных букв. Поэтому операций такого вида много. Если α некоторая буква, то ей отвечает так называемая α-генерация. Для такой операции введем обозначение hα. К непустым словам α-генерация неприменима и для них никакого результата не дает.

3. Одноместная операция соединения слов (описана в § 5 гл. 7). Будучи применена к произ­вольному слову, эта операция в качестве результата дает то же слово. Эту операцию будем обозначать S₁(P), где P — слово.

4. Двухместная операция соединения слов (описана в § 5 гл. 7). Эта операция, будучи приме­нена к упорядоченному набору из двух слов, в качестве результата дает слово, которое получится, если к первому слову (после его конца) приписать второе слово. Эту опе­рацию обозначим S₂(P₁, Р₂), где P₁ и Р₂ — слова.

Ко второй группе натуральных операций, называемой группой слово-квазислово, отнесем операции, для которых исходными данными являются слова, а результатами — ква­зислова (см. ниже), и операции, для которых исходными данными являются квазислова, а результатами — слова.

Квазисловом будем называть конструкцию, отличаю­щуюся от слова тем, что одна из ее букв связана дополни тельной связью первого ранга, которая отличается как от начинающей, так и от заканчивающей связи следования и называется выделяющей связью. Поясним понятие квази­слова примерами. Слово «мама» имеет структуру

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

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

В группу слово-квазислово входят следующие две операции.

5. Нахождение начала слова. Обозначим чту операцию символом * (звездочка). Она применима к любому непустому слову и преобразует его в квазислово, в котором выделена начальная буква. К пустому слову эта операция неприменима и для него не дает никакого резуль­тата. Если применить операцию нахождения начала к слову

то результатом будет квазислово

6. Отключение — операция, противоположная предыдущей. Она применима к любому квазислову и в ка­честве результата дает соответствующее ему слово. Иными словами, эта операция уничтожает в квазислове выделяю­щую связь и тем самым превращает его в обычное слово. Обозначим эту операцию знаком X. Эту операцию мы про­изводим, когда в рассматриваемом слове перестаем особо рассматривать одну из его букв.

Третья группа операций называется квазислово-квазислово. В нее входит пять натуральных операций.

7. Операция продвижения вправо. Обозначим ее символом →. Заключается она в том, что от заданного квазислова она ведет к квазислову, в котором выделена буква, непосредственно следующая за той, кото­рая была выделена в исходном данном. Например, приме­няя продвижение вправо к квазислову

получим квазислово

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

8. Операция продвижения влево; обратна предыдущей. Будучи примененной к некоторому ква­зислову, она преобразует его в другое квазислово, отличаю­щееся от данного тем, что в нем выделена буква, которая в исходном данном непосредственно предшествовала вы­деленной букве. Например, если к квазислову

применить продвижение плево, получится квазислово

К квазисловам, в которых выделена начальная (первая, самая левая) буква, эта операция неприменима. Обозначим эту операцию ←.

9. Замена буквы. Фактически таких операций столько, сколько букв в алфавите. Поэтому если а — неко­торая буква, то ей соответствует операция, называемая заменой буквы на а. Выполнение этой операции заключается в том, что в исходном квазислове выделенная буква заме­няется буквой а, которая становится при этом выделенной.

Например, если исходным данным является квазислово

то с помощью замены буквы на «ш» мы получим квазислово

Описанную операцию обозначим !a.

10. Отсечение. Обозначим эту операцию значком ↓. Заключается она в том, что в исходном квазислове все буквы, следующие за выделенной, отбрасываются. Вы­деленной оказывается последняя (концевая) буква резуль­тата. Например, применяя операцию отсечения к квази­слову

мы получим квазислово

Отсечение применимо к любому квазислову.

11. Приписывание буквы справа. Так как приписать в принципе можно любую букву, то таких опе­раций столько, сколько букв в алфавите. Поэтому конкрет­ная операция при заданной букве а называется (коротко) а-приписыванием. Эта операция применима только к ква­зисловам, в которых выделена последняя буква. К осталь­ным квазисловам она неприменима. Ее результат отличает­ся от исходного данного тем, что в квазислове после (справа от) выделенной появляется буква а. Выделенной останется прежняя буква. Например, применяя а-приписывание к квазислову

получим квазислово

Описанную операцию обозначим

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

12. Линеаризация применима к любой конструкции. Если эта конструкция принадлежит классу (A, В, Σ), то линеаризация преобразует его в слово в алфавите Е=BACD, который получается объединением в одно слово четырех алфавитов (напоминаем, что алфавит — это слово, буквы которого попарно неодинаковы). При этом, кроме алфавитов A и B, в этот новый алфавит входят еще два алфавита, не пересекающиеся ни о алфавитами А и В, ни между собой.

К алфавиту С предъявляется, кроме вышесказанного, лишь одно требование. Число его букв должно равняться наибольшему жанру связей, указанных в алфавите В.

Алфавит D должен состоять из трех букв. Пусть для определенности это будут «|» (палочка), «(« (открывающая скобка) и »)» (закрывающая скобка). Выбрав так алфавит D, мы не уменьшим общности наших рассуждений потому, что если бы выбранные символы уже оказались занятыми в других алфавитах, мы взяли бы вместо них другие сим­волы.

Слово, получаемое в результате линеаризации конструкции, называется образом этой конструкции в алфавите E (точнее, относится к числу таких образов; об этом будет речь в следующем параграфе).

13. Делинеаризацией называется операция, которая слова в E=BACD, если они удовлетворяют условиям в силу которых являются образами конструкций класса (А, B, Σ), преобразует в определенные конструкции указанного класса. К остальным словам делинеаризация неприменима, Остальные натуральные операции являются операция­ми проверки различных условий. Их всего четыре. Будем считать, что все они входят в одну группу, именно в группу натуральных предикатов. Термин «предикат» является ма­тематическим синонимом слова «условие». В результате применения предиката к какой-нибудь конструкции она никак не изменяется, но ей в соответствие ставится логиче­ское значение, которое можно передать одним из слов «да» или «нет». Логические значения в принципе можно пере­давать и с помощью других символов и конструкций. Логическое значение не является составной частью кон­струкции, которая получилась после применения к ней предиката, а является определенным изменением состояния исполнителя операции²⁴. Мы уже встречались с преди­катами, когда изучали машины Тьюринга, но только не выделяли их в самостоятельные операции. Для машин Тьюринга было еще характерно применение многозначных предикатов (допускающих одно значение из многих), тогда как мы сейчас будем допускать только двузначные преди­каты (дающие одно из двух логических значений). В маши­нах Тьюринга логическими значениями были возможные состояния логического блока.

Опишем натуральные предикаты (их четыре).

1. Условие непустоты. Можно считать, что оно гласит: «рассматриваемое слово непусто». Обозначим эту операцию знаком Δ (дельта). Условие непустоты приме­нимо к любому слову и дает ответ «да», если слово непу­сто, и ответ «нет», если оно пусто.

2. Условие начала; оно гласит: «в рассматри­ваемом квазислове выделена начальная буква». Это условие к словам неприменимо. Обозначим его буквой н.

3. Условие конца. Обозначим его буквой k. Оно гласит: «в рассматриваемом квазислове выделена по­следняя буква». К словам эта операция неприменима.

4. Условие тождественности выделенной буквы заданной букве. Фактически таких условий столько, сколько букв в алфавите. Поэтому, если α — заданная бук­ва, то говорят об условии α-тождественности. Условие α-тождественности гласит: «выделенная буква квазислова одинакова (тождественна) с буквой α». Обозначим это ус­ловие знаком .

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

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

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

1. Исходную конструкцию заключают в оболочку. Про­извольным образом нумеруют все оболочки. Если в конст­рукции имеются связи, то производят их подготовку ниже­описанным способом» после чего переходят к п. 2. Если связей нет, сразу переходят к п. 2. Подготовка связей осуществляется так.

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

Окончив нумерацию связей, помечают у всех связей ветви первого жанра — первой буквой алфавита С, ветви второго жанра — второй буквой алфавита С и т. д.

Наконец, для каждой связи ветви, имеющие одинаковый жанр, произвольным образом нумеруют, опять используя в качестве номеров строки палочек. Теперь именем каждой ветви связи β, ранга, помеченного буквой γ, считают строку букв β ||. . .| γ ||…|, в которой первая группа палочек — номер связи вида β, а вторая группа палочек — номер ветви среди ветвей, имеющих жанр, соответствующий букве γ.

Наш способ построения имен ветвей позволяет устано­вить старшинство между этими именами (они все различ­ны). Предположим, что мы имеем два имени ветвей

β₁||…| γ₁||…| и β₂||…| γ₂||…|.

Если β₁ в алфавите В предшествует β₂, то первое имя младше второго. Если β₁ и β₂ означают один и тот же символ, но число палочек между β₁ и γ₁ меньше числа палочек между β₂ и γ₂, то снова первое имя младше. Если и эти числа палочек равны, то рассматриваем буквы γ₁ и γ₂. Если γ₁ в С предшествует γ₂, то снова первое из имен младше. Если окажется, что и последнее не решает вопроса (γ₁ и γ₂ означают одну и ту же букву в С), то вопрос решают палочки, стоящие после γ₁ и и после γ₂. Если число палочек после γ₁ меньше числа палочек после γ₂ тo опять первое имя младше второго. Так как одинаковых имен нет, то случай, в котором первое имя не младше второго, является случаем, в котором второе младше первого.

2. Просматривая оболочки в порядке присвоенных им в п. 1 номеров, находят первую, внутри которой больше нет оболочек. Рассматривают заключенную в ней конструк­цию. Переходят к п. 3.

3. Если рассматриваемая конструкция является пустой, то считают, что ей соответствует пустое слово, и переходят к п. 6. Иначе переходят к п. 4.

4. Если рассматриваемая конструкция состоит из един­ственной буквы, то считают, что ей соответствует однобуквенное слово, и переходят к п. 6. Иначе переходят к п. 5.

5. В произвольном порядке выписывают столбцом все буквы в Л, присутствующие в рассматриваемой конструк­ции, а перед каждой из них в порядке возрастания стар­шинства пишут имена ветвей связей, которые в составе конструкции их связывают. Теми же правами, что и буква в А, может пользоваться слово в Е, заключенное в скобки. Такое слово может появиться при повторных выполнениях данного пункта (см. п. 6).

Получают столбец строк, каждая из которых содержит несколько имен связей и заканчивается буквой в А. Такие строки будем называть фрагментами. Фрагменты в поряд­ке номеров строк, которые их содержат, объединяют в слово. Это слово содержит в себе последствия большого числа актов произвола. Эти последствия нужно устранить. Для этого произведем полную факториализацию получен­ного слова. Теперь мы будем иметь длинный столбец слов, каждое из которых соответствует некоторому сочетанию возможных способов нумерации связей и их ветвей.

После факториализации в некоторых фрагментах не­которых слов нарушится порядок старшинства имен ветвей. Мы каждое из наших слов поправим, добиваясь того, чтобы в каждом фрагменте каждого слова имена ветвей были расположены по возрастанию их старшинства. Затем пере­расположим в каждом слове фрагменты в порядке возраста­ния их алфавитного старшинства (а это старшинство опре­деляется первым из.,имен ветвей, стоящим во фрагменте). Теперь остается совершить последний шаг: из веех имеющихся слов выбрать такое, которое в смысле алфавит­ного порядка (задаваемого алфавитом Е) не старше всех остальных слов. Мы говорим «не старше» вместо «младше», потому что среди построенных слов могут быть одинаковые и может оказаться, что «младших» слов несколько. Итак, получив единственное слово, переходим к п. 6.

6. Полученное слово заключают в скобки и вставляют в преобразуемую конструкцию вместо соответствующей ему оболочки и ее содержимого. Если конструкция не ис­черпалась при этом, то переходят к п. 2. Если же конструк­ция исчерпалась, то отбрасывают только что примененные скобки. Получившееся слово и есть результат линеаризации. Как видит читатель, описанная операция очень сложна. Но она является универсальной и может быть применена к любой конструкции.

На практике для частных видов конструкций обычно пользуются более простыми способами линеаризации. Та­кие способы могут быть получены из универсального с по­мощью общего определения операции (см. § 1).

Две конструкции класса (А, В, Σ), которые при каких-либо алфавитах С и D дают один и тот же результат после линеаризации, называются одинаковыми конструкциями. Теперь опишем делинеаризацию. Эта операция некоторые слова в алфавите E=BACD преобразует в кон­струкции класса (А, В, Σ). Здесь D состоит из трех букв, играющих роль палочки, и двух сортов скобок (открываю­щей и закрывающей), а С имеет число букв, равное наиболь­шему жанру связей из В.

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

Операция делинеаризации является обратной для ли­неаризации в следующем смысле. Если какую-либо конст­рукцию линеаризовать, а потом получившееся слово де линеаризовать, то новая конструкция окажется одинаковой с исходной. Это позволяет обе конструкции считать экземп­лярами одной и той же конструкции.

Нетрудно сообразить, какова должна быть структура исходного слова для того, чтобы оно могло быть исходным для линеаризации. Это слово должно расчленяться на фраг­менты, состоящие из нескольких имен ветвей и замыкающей их буквы в А или слова, взятого в круглые скобки. В круг­лых скобках опять должны стоять слова, разложимые на фрагменты. И так далее. Но этого еще мало. Нужно также, чтобы имен ветвей каждой связи было столько, сколько вет­вей имеет эта связь, и чтобы между именами ветвей и вет­вями было необходимое соответствие. Кроме того, распо­ложение имен ветвей должно обеспечивать получение после делинеаризации одной, а не нескольких конструкций. По­дробнее останавливаться на операциях линеаризации и делинеаризации мы не будем.