Формальная семантика формального языка

В свое время, получая понятие формального языка, мы пришли к выводу, что семантика и синтаксис языка долж­ны рассматриваться раздельно.

Во всех предыдущих параграфах, говоря о формальных языках, мы все время следили за их синтаксисом. Лишь один раз, в § 4 настоящей главы, мы имели дело с формаль­ным языком, наделенным семантикой. Теперь можно кое-что сказать о способах наделения языков семантикой. К со­жалению, при этом мы не можем сказать, чем же вообще яв­ляется семантика, а можем разъяснить лишь некоторые част­ные случаи.

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

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

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

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

Второй способ наделения формального языка семанти­кой заключается в следующем. Предположим, что, кроме нашего формального языка L, имеется еще один язык L¹, причем этот второй язык уже наделен семантикой (безраз­лично как). Обозначим произвольное предложение языка L буквой 7, а правильное предложение языка L¹—буквой s. Допустим, что нам задан алгоритм Т, который каждое 1 перерабатывает в одно-единственное соответствующее ему предложение 5. Такой алгоритм называют алгоритмом пе­ревода, а в теории программирования — алгоритмом транс­ляции. Алгоритм перевода переносит смысл предложения s на то предложение I, из которого получается это s.

Описанный способ (назовем его способом трансляции) имеет очень широкое применение. Семантика языка эспе­ранто, о котором мы говорили в §2 гл.7, была задана именно таким способом.

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

В § 5 гл. 6 мы говорили о входных языках программиро­вания и о трансляторах, которые позволяют делать перевод на язык программ. Как только для входного языка програм­мирования задан транслятор,— он наделен семантикой, так как язык программ имеет семантику.

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

Этот способ отличается от предыдущих тем, что, кроме формального языка, наделяемого семантикой, требует прив­лечения второго языка — операндного. Если t — алго­ритм, as — исходное данное, то нужен алгоритм W, опи­сывающий применение t к £. Меняя s', но не меняя t, мы мо­жем для каждого t (при желании) получить соответствующий результат р*. Значит, t есть описание некоторой функции вида t (s). Если задан алгоритм, то задана и эта функция.

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

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

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

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

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

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

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

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

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

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

Глава 9