Буквы, связи, оболочки, конструкции

Если мы хотим употреблять термин «язык программ», а это нам нужно, чтобы считать программы алгоритмами, мы должны допускать возможность очень сложной структуры предложений языка. Автор думает, что полезность трактов­ки программ для ЭВМ как алгоритмов уже не вызывает у читателя сомнений, и потому не будет второй раз ее обосно­вывать.

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

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

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

Приведенное описание несколько туманно. Сформули­руем его более точно в виде следующих пунктов.

1. Конструктивным элементом является либо отдельная буква, либо конструкция, заключенная в оболочку.

2. Конструкцией называется либо пустое множество, либо несколько конструктивных элементов, связанных несколькими связями так, что «способности» связей к свя­зыванию полностью использованы (связи насыщены), а любые два конструктивных элемента можно соединить це­почкой из конструктивных элементов и связей (конструк­тивные элементы связаны).

Нужно точнее пояснить, что мы понимаем под буквами,

оболочками и связями.

Буквы — это применяемые нами символы, которые в процессе их использования уже нельзя делить на части или как-либо деформировать.

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

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

В слове «мама» присутствуют три вида связей, которые в своей совокупности образуют связи следования букв. В этом слове связи не изображены никакими символами. Они переданы особым расположением букв. Тем не менее они там есть. Если ввести символы для обозначения связей следования букв, обозначив их соответственно через и , то слово «мама» следует представить в виде

Здесь означает «одноместную» связь, называемую начинающей, знак означает «двухместную» связь, называемую продолжающей.

Наконец, знак означает «одноместную» связь, назы­ваемую заканчивающей.

Однобуквенное слово «а» (союз) имеет вид:

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

Мы, говоря о связях, иногда будем их обозначать особыми знаками, иногда будем передавать особым способом расположения конструктивных элементов, но всегда будем иметь в виду их наличие.

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

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

…

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

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

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

Если какой-либо конструктивный элемент является конструкцией, облеченной в оболочку, то связи, которые его связывают «в целом», своими ветвями «подключены» к его оболочке. Мы допустим расширение понятия конст­рукции, если скажем, что после того, как конструкция по­лучена способом, описанным в ее определении выше, можно наложить на нее еще некоторое количество связей, «прони­кающих» сквозь оболочки ее конструктивных элементов на какую угодно глубину. То, что получится, снова будем на­зывать конструкцией и допускать в качестве строительного материала для более сложных конструкций. Заметим только, что если все связуемые элементыкакой-либо связи находятся внутри некоторой оболочки, то считается, что она сама тоже находится внутри этой оболочки. На рис. 16 приведена схема конструкции, образованной из букв с помощью оболочек и связей. На этом рисунке α, β, γ— имена связей, кроме того, показаны связи следования букв, имена которых не обозначены. Замкнутые линии изобража­ют собой оболочки. Одна из оболочек, связанная ветвью жанра 3 связи α, облекает собой пустую конструкцию. Связь β проникает ветвью второго ранга через две оболочки, На практике обыч­но встречаются менее за­мысловатые конструк­ции, чем показанная на рис. 16, например, «деревья» и «кольца», образованные с помо­щью связей следования из букв, матрицы и т. п. Эти виды конструкций пояснены на рис. 17.

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

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

§ 4. Формальные грамматики

Вернемся к описанию языков. Считается, что предложе­ниями языков могут быть любые конструкции, описанные в предыдущем параграфе. Уже одним этим расширяется понятие языка. Как уже сказано, синтаксис языка не дол­жен зависеть от его семантики. Термин «предложение» сохраним и для формальных языков. Мы не накладываем запретов ни на какие формы синтаксиса, но для того чтобы всегда быть уверенными в том, что мы располагаем именно формальным языком, потребуем, чтобы существовала (т. е. могла бы быть построена) формальная грамматика, имею­щая определенную каноническую форму. Американский лингвист А. Хомский предложил следующую форму грам­матики. Для описания синтаксиса языка-объекта задается алфавит букв этого языка, затем алфавит вспомогательных символов, называемых нетерминальными (буквы первого алфавита при этом называют терминальными символами), затем — конечный набор синтаксических правил и, наконец, однобуквенное слово, образованное из нетерминального сим­вола. Условно это передают в виде обозначения (А, С, R, σ), где А — алфавит языка-объекта, С — нетерминальный ал­фавит, R — набор правил, σ — указанная выше нетерми­нальная буква.

Каждое правило в грамматике Хомского имеет вид подстановки Р → Q, в которой Р и Q — слова в алфавите АС (получающемся соединением алфавитов А и С). Под­становки, применяемые А. Хомским, не являются марков­скими подстановками (см. § 3 гл. 4) и вообще не являются однозначными операциями преобразования конструкций. Объектом преобразования для таких подстановок могут быть только слова, но применение подстановки допускает произвол. Если преобразуемое слово имеет несколько вхож­дений слова Р, то подстановка допускает замену любого из этих вхождений правой частью формулы.

Так как, вообще говоря, число вхождений Р в разные слова неограниченно, то можно считать, что каждая под­становка представляет собой бесконечное множество операций замены словом Q: 1) первого вхождения P; 2) второго вхождения Р;...; п) п -го вхождея P и т.д.Выполнение подстановки заключается в выполнении произвольной операции из перечисленных. Однако подстановку можно рассматривать и как конечное множество определенных операций, выполняемых в различных сочетаниях. Дальнейшее изучение подстановок мы производить не станем, поскольку эта проблема для нас особого интереса не представляет. Разъясним только способ порождения формального языка с помощью грамматики Хомского. Предложение языка получим, если применим к однобуквенному слову σ одну из подстановок. Если результат не содержит нетерминальных символов, предложение языка уже получено; если же содержит, то применяем опять одну из подстановок, и т.д. Говорят, что предложение языка выводится из начального слова σ с помощью правил, входящих в состав R, - набора синтаксических правил грамматики Хомского. Аналогично выводится другое предложение и т.д. Грамматики Хомского нас не удовлетворяют по друм причинам. Во-первых, их возможности слишком ограничены, так как с их помощью можно построить только язык, предложениями которого являются слова. Во-вторых, способ порождения языка, избранный Хомским, является слишком искусственным и для нас непривычным. Ни одна знакомая нам грамматика ни одного из естественных языков не имеет вида грамматики Хомского. Обычно предложения языка строят из более простых конструкций и в конце концов все предложения получаются из некоторых элементарных конструкций, называемых морфемами. Остановимся и мы на такой форме порождающих грамматик.

Предположим, что заданы алфавиты букв и связей и знак оболочек, из которых будут построены предложения языка-объекта, т.е. считаем, что известен класс (A, B, Σ) конструкций, с которыми нам придется иметь дело при построении языка. Далее, допустим, что задано конечное число простейших конструкций, множество которых назовем базой языка и обозначим буквой Б. Элементы этого множества называются морфемами. Предположим, что задан алфавит С символов, с помощью которых записываются синтаксические правила. Эти правила у нас всегда будут иметь вид цепочек из символов, т.е. слов. Поэтому специально оговаривать наличие алфавита связей, нужного для записи правил, мы не станем. Алфавит С должен содержать символы четырех видов, попарно различные между собой и не совпадающие с символами, участвующими в конструкциях класса (A, В, Σ). Символы первого вида применяются как индивидуальные имена морфем. Символы второго вида будем применять в качестве групповых имен получаемых конструкций. Символы третьего вида играют роль функциональных знаков и являются именами операций. Наконец, символы четвертого вида играют вспомогатель­ную роль: это скобки, запятые, знаки равенства и знаки «точка с запятой» или заменяющие их символы.

Каждое синтаксическое правило будет иметь либо вид

,

где η— имя морфемы, ξ — групповое имя, либо вид

,

где ξ — групповое имя, ξ₁, ξ₂, …, ξ_r —- групповые имена или имена морфем, f — функциональный знак, r — ранг операции, именем которой является f.

Рангом операции называется число величин, которые участвуют в качестве исходных данных при выполнении операции. Например, среди известных нам операций lg x — операция первого ранга, sin х и — тоже; х + у и х: у — операции второго ранга. Можно считать, что выражение x+y*z задает некоторую операцию третьего ранга.

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

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

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

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

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

Интересно отметить следующую теорему.

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

Доказательство этой теоремы очень просто, а ее резуль­тат имеет большое практическое значение. Приведем это доказательство. Предположим, что нам задано конечное множество предложений естественного языка, например, в виде списка. Пусть это будут Р₁, Р₂, …, P_N. Просматри­вая эти предложения, мы можем отобрать все буквы, при­сутствующие в них; в число букв в общем случае попадут и знаки препинания, и пробелы. Перечень этих букв будет искомым алфавитом А. Связи следования составят алфавит В. Алфавит С образуем из букв «;», «=», «а» и всех симво­лов Р₁, Р₂, …, P_N (считаем, что они отличаются от букв в А, друг от друга и от букв «;», «=», «а»). Теперь напишем N синтаксических правил:

σ = Р₁; σ = Р₂; …; σ = P_N.

Базой считаем совокупность предложений, обозначен­ных символами P_i. Читатель видит, что индуктивная грам­матика построена и, следовательно, конечное множество предложений естественного языка является формальным языком (без учета семантики).

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

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

Мы познакомились с табличной формой задания фор­мального языка. Табличная форма с успехом используется для построения формальных языков, применяемых при описании исходных данных многих задач, решаемых на ЭВМ (в тех случаях, когда эти исходные данные не являются числами).

Нотация Бекуса. Тезаурусы

В 1958 г. на русский язык было переведено описание алгоритмического языка лгол-58, составленное с помощью особых синтаксических правил, получивших название фор­мул Бекуса. Способ описания формального языка с помощью формул Бекуса называется нормальной формой или нота­цией Бекуса.

Рассмотрим частный случай порождающей индуктивной грамматики, в котором применяемыми конструкциями являются слова, а операциями, имена которых присутст­вуют в синтаксических правилах, являются так называемые операции соединения слов. Обозначим эти операции вре­менно символами S₁(P), S₂(P₁, Р₂), S₃(P₁, P₂. P₃), …, S_i(P₁, Р₂, ..., P_i), где Р, P₁, Р₂,..., Р_i — произвольные слова. Сущность этих операций заключается в следующем. Операция S₁(P) является тождественной операцией. Для нее справедливо равенство

.

Например S₁(мама)=мама.

Для операции S₂(P₁, P₂) справедливо условие

.

т. е. ее результатом является новое слово, получаемое путем приписывания елов Р₂ к слову Р₁. Например, S₂ (экстра, алгоритм) = экстраалгоритм.

Вообще, для S_i(P₁, P₂, …, Р_i) справедливо условие

S_i(P₁, P₂, …, P_i)=P₁P₂…P_i.

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

1. Во всех синтаксических правилах знак «=», отде­ляющий левую часть от правой, заменим знаком «:: =», который читается как «по определению есть».

2. Во всех правилах имена морфем заменим самими морфемами. Это можно сделать, так как морфемы являются словами (пустыми, однобуквенными или многобуквенными).

3. Если имеется несколько формул, в левых частях ко­торых стоят одинаковые групповые имена, то заменим эти несколько формул одной, имеющей такую же левую часть, а в правой части содержащей записи всех правых частей указанных формул, разделенные знаками «|». Эти знаки читаются как «или». Данное видоизменение синтаксических формул не обязательно. Новая формула рассматривается как сокращенная запись вошедших в нее старых формул.

4. Пользуясь тем, что результат выполнения операции S_i соединения можно получить из ее записи путем отбрасывания функциональной буквы S_i, скобок и разделяющих аргументы запятых, отбросим в правых частях синтаксических правил знаки S_i, знаки «(», «)», «,».

5. Наконец, условимся об особом выборе символов, яв­ляющихся групповыми именами. В качестве таких символов будем брать фразу на естественном языке, заключенную в угловые скобки. Такая фраза в угловых скобках является одним целым и неизменяемым знаком — метасимволом.

Заметим, что в языке-объекте и в используемом естест­венном языке не должны применяться буквы «:: =», «|». «<«, «>» или сочетания букв, одинаковые с символом:: =,

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

Приведем пример описания формального языка с по­мощью нотации Бекуса. Ставить внутри формул знаки переноса или после них знаки препинания нельзя!

Как известно, десятичная система счисления является формальным языком. Ее алфавит содержит десять букв, обычно называемых арабскими цифрами. Будем считать, что базу языка составляют десять морфем, каждая из кото­рых является однобуквенным словом. Для обозначения груп­пового имени «морфема» используем метасимвол «(цифра)». Итак, приводим формулы Бекуса:

<ненуль>::= 1|2|3|4|5|6|7|8|9

<цифра>::=0 | <ненуль>

<строка цифр>::= <цифра> | <строка цифр> <цифра>

<неотрицательное целое число>::= <цифра> | <ненуль>

<строка цифр>

Эти четыре формулы Бекуса дают полное описание деся­тичной системы счисления. Покажем, как с помощью этих формул можно порождать различные записи чисел. В силу первой и второй формул 1, 2, 7, 0 являются цифра­ми. В силу третьей формулы 001207 является строкой цифр, а в силу второй формулы 5 является ненулем. Наконец, в силу четвертой формулы 5001207 является неотрицатель­ным целым числом.

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

Есть очень простые слова, которые невозможно описать с помощью формул Бекуса. Например, к их числу относятся «спаренные числа»; чтобы написать такое число, нужно сперва написать какое угодно число, а затем к нему припи­сать в точности такое же число. Спаренными числами являют­ся 88, 9191, 235235 и т. п. К сожалению, формула Бекуса

<спаренное число>::= <неотрицательное целое число> <неотрицательное целое число>

не является описанием спаренных чисел, так как наряду со спаренными числами дает и многие другие.

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

<цифра>::=0|1|2|3|4|5|6|7|8|9

<буква> ::=А|В|C|D|E|F|G|Н|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<идентификатор>::= <буква> | <идентификатор> <бук­ва> | <идентификатор> <цифра>

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

В конце предыдущего параграфа мы говорили о том, что конечное множество предложений естественного языка представляет собой, без учета семантики, формальный язык. Такой формальный язык можно описать с помощью формул Бекуса. Еще один вид его описания называют тезаурусом; его мы упоминали в предыдущем параграфе[23]. В простейшем случае тезаурус — это список упомянутых предложений. В более сложном случае тезаурус представ­ляет собой перечень некоторых текстов, каждому из которых придана дополнительная, так называемая грамматическая информация. Эта структура тезауруса применяется в тех случаях, когда список предложений очень велик. Мы пояс­ним его на небольшом списке, чтобы передать только са­мую суть этого способа описания формального языка.

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

Таблица 7

Чтобы получить предложения языка, нужно войти в тезаурус. Если мы остановимся на позиции 1, то про­читаем текст «изделие» и узнаем, что с ним связана пози­ция 10. В позиции 10 прочитаем текст «текстильн» и ин­формацию* 21 —1,2, которая означает, что за «текстильн» следует содержимое позиции 21 и затем текст «изде­лие» (цифра 1 во второй части информации).

В итоге получаем предложение «текстильное изделие».

Знак означает пробел. Знак * означает «данный текст» (в этом примере «текстильн»). Числа означают номера по­зиций. Если два числа разделены запятой, то из них должно быть выбрано то, которое является номером пози­ции, от которой был совершен переход к данной позиции. В графе «смысловые связи» у нас указана лишь подчи­ненность понятий. Запись «2>3» значит, что понятие «производство» старше понятия «работа».

Под номером 5 в тезаурусе стоят 2 термина «текстиль» и «ткань». Эти термины считаются синонимами (что, собст­венно, относится уже к смысловым связям).

Реально применяемые тезаурусы могут быть значитель­но сложнее того, который описан в качестве примера. В тезаурусе, кроме указанных сведений, нередко содержат­ся «отсылки» к массивам информации и программам, позво­ляющим получить «смысловую» информацию, связанную с текстами, включенными в тезаурус.

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

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

Г л а в а 8

ЭЛЕМЕНТЫ АНАЛИТИЧЕСКОЙ ТЕОРИИ

АЛГОРИТМОВ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Операция продвижения влево; обра