Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Ввиду неоднозначности символов может возникнуть, например, следующий вопрос: почему дистрибутивность умножения относительно сложения записывается в виде
(а + Ь) (с + d) = ас + ad + be + bd,
а если мы имеем некоторую операцию о, дистрибутивную относительно некоторой другой операции *, то соответствующее выражение необходимо записывать более точно, т. е. сохраняя скобки:
(а о Ь) * (с о d) = (а ° с) * (а ° d) * (b ° с) к (b ° d)?
Подобные вопросы возникают в области обычной математики, но ответы на них следует искать в области метаматематики.
Вообще, человек, изучающий математику или пользующийся ею, нередко не проводит четкого различия между математическим понятием и математическим методом построения определения этого понятия и введения обозначений для его описания. Так, сплошь и рядом функцию смешивают с описывающей ее формулой. Впрочем, довольно часто сознательное неразличение формы и содержания, т. е. трактовка семантики как синтаксиса, позволяет 14
Часть /. Предварительные сведения из логики и алгебры
обнаруживать ошибки и восстанавливать смысл ошибочных или неоднозначных выражений.
Ясно, что машина не обладает тем запасом общих знаний и навыков, которые позволяют человеку выбирать правильную интерпретацию того или иного формального выражения. Поэтому, чтобы ввести в машину некоторое сообщение, мы должны пользоваться языком, в котором все определено совершенно строгим образом, вплоть до мельчайших деталей.
Для этого нам придется пойти на выучку к логикам, которые — к счастью для нас! — не дожидаясь появления "электронных машин, начали изучать метаматематику чисто математическими методами.
Обращение к логике избавит нас от необходимости затрачивать значительные усилия на повторное открытие хорошо известных вещей.
В качестве первого шага мы приступим к рассмотрению «письма», начав с его самых простых аспектов — с употребления символов, которые можно располагать один за другим и образовывать из них слова, выражающие, быть может, тот или иной смысл.
Это и будет содержанием первой главы.
1.1.1. Базовые элементы
Пусть имеется непустое множество 91, которое мы назовем базой, а его элементы— базовыми элементами. Чтобы как-то обозначить эти элементы, мы поставим в соответствие каждому из них графический символ, который и будет «письменным» именем этого элемента; а чтобы иметь возможность говорить о базовых элементах, мы сопоставим каждому из них «устное» имя. Само собой разумеется, что двум разным базовым элементам мы дадим разные имена.
Пример 1. Множество 91 содержит один-единственный элемент, изображаемый символом | и обозначаемый словом «палочка».
Пример 2. Множество 91 содержит два элемента, изображаемые символами bhdh обозначаемые словами «черный» и «белый».
Символ, которым мы обозначаем базу (в нашем случае — символ 91), не должен, естественно, использоваться для обозначения какого-либо элемента этого множества.
1.1.2. Конечные последовательности (цепочки)
Теперь мы рассмотрим некоторые образования, которые обычно называют размещениями элементов из 91 с повторениями. Речь идет о конечных последовательностях, или цепочках, элементы которых суть вхождения элементов из 91. Чтобы изобразить по- Гл. I. Слова (цепочки). Полугруппы. Языки
15
добную цепочку графически, можно расположить на строчке (на бумажной или магнитной ленте и т. п.) вхождения символов, сопоставленных элементам її. Обычно в книгах последовательности символов всегда считаются ориентированными слева направо, если только в явной форме не оговорено противное.
Пример. Если база її содержит три элемента, обозначенные соответственно через a, b и с, то запись
bacaba
изображает цепочку, образованную шестью элементами; первый элемент последовательности есть вхождение элемента b множества її и т. д.
Удобно ввести в рассмотрение также пустую цепочку, не содержащую никаких вхождений.
Мы будем обозначать цепочки специальными символами, а сами цепочки заключать в одинарные кавычки (следя при этом, чтобы эти символы не использовались в качестве обозначений для каких-либо базовых элементов). Например, в предыдущем примере можно писать
А = 'bacaba', В = 'acccab'.
Целесообразно выбрать один символ, например Ey чтобы обозначать пустую цепочку.
Введенные здесь соглашения о способах записи цепочек позволяют получить предварительное представление об использовании метаязыка для описания некоторого языка; к этому вопросу мы вскоре еще вернемся.
Определим длину цепочки как целое число, равное числу вхождений элементов, образующих цепочку. Пустая цепочка будет иметь длину нуль. Длина цепочки обозначается с помощью вертикальных черточек:
I bacaba | = 6, |Л| = 6.
Аналогично определяется длина цепочки относительно одного или нескольких символов: 'bacaba' имеет длину 3 относительно а (иначе — по а), длину 1 по с и т. п.
1.1.3. Конкатенация цепочек
Итак, пусть имеется множество її. Рассмотрим множество її* цепочек, образованных вхождениями элементов из її. Если даны цепочки А и В (в указанном порядке), то мы можем поставить в соответствие упорядоченной паре {А, В) цепочку С, полученную следующим образом: выпишем сначала подряд все вхождения из 16
