9.7. Примеры семантических отображений

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

Продемонстрируем, как это делается, на примере алгебры изображений из подраздела 6.3.2. Пусть состоит из символов II. Другими словами, мы пользуемся элементами а также двумя разделительными символами I и II.

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

вхождениями II отсутствуют другие символы. Символ I не используется после исчерпания связей образующей.

Например, конфигурация на рис. 9.6.1 будет отображена в цепочку

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

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

Рис. 9.7.1

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

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

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

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

Рис. 9.7.2

7.2.1. Вместо того чтобы стремиться к схемам типа (9.7.1), было бы интереснее начать с другого конца: при заданном семантическом отображении рассмотреть., потребности в памяти и сопоставить это с Будут введены семантические отображения со специальной структурой, см. Примечания А.

Определение 9.7.1. Семантическое отображение называется обратно направленным, если любое соединение присоединяет все новые выходные связи (при наличии таковых) вводимых им образующих к образующим, которые уже находятся в

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

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

Лемма 9.7.1. Если семантическое отображение обратно направленное, то для любой правильно построенной фразы, начинающейся в состоянии 1, справедливо

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

7.2.3. Любая правильно построенная фраза V означает теперь регулярную конфигурацию — важный факт, который значительно упростит обучение семантике. По заданному предложению мы можем рассмотреть каждую исходную фразу начиная с малых значений и пытаясь уяснить значение каждой новой ветви на диаграмме автомата. Это справедливо только в том случае, если, как это здесь имеет место, каждая обладает смыслом в а не только в где конфигурации не всегда обладают смыслом с точки зрения наблюдателя.

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

пор мы познакомились лишь с несколькими простыми примерами того, как это делается.

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

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

7.3.2. При «множество показателей связей» (для введем множество

и множество Ф функций определенных на подмножествах Обозначим через область определения такой связывающей функции

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

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

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

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

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

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

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

7.4.1. Чтобы пояснить сказанное выше, рассмотрим алгебру изображений из подраздела 4.2 настоящей главы, ограничиваясь образующими уровней 0 и 1. Выберем язык у которого а соответствующая диаграмма представлена на рис. 9.7.3.

Для того чтобы построить семантическое отображение, воспользуемся связывающими функциями, приведенными в табл. 9.7.2, и будем интерпретировать продукции грамматики в соответствии с табл. 9.7.1.

Графа «определение во второй колонке табл. 9.7.2 относится к полному действию всех связывающих функций, указанных в данной строке. Роль индивидуальных связывающих функций дана лишь неявно. Например, означает, что нужно добавить и присоединить к последней к, в то время как означает — присоединить (текущей -образующей) к следующей последней к.

Рассмотрим предложение

Рис. 9.7.3 (см. скан)

и его разложение

Это предложение правильно построено.

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

(см. скан)

Последний переход не изменяет изображения. Теперь рассмотрим более сложный пример:

Соответствующее разложение имеет вид

Применяя ту же «разворачивающую» процедуру, мы убеждаемся, что показано на рис. 9.7.4.

Рис. 9.7.4

Замечание 1. Связки, применявшиеся в этом примере, обладают свойствами, которые встретятся нам при более общих условиях. Каждая связывающая функция присоединяет выходные связи (если таковые имеются) новых образующих к входным связям старых

Таблица 9.7.1 (см. скан)

Таблица 9.7.2 (см. скан)

образующих. Получающаяся в результате семантика является обратно направленной.

Замечание 2. Каждая связывающая функция определена в табл. 9.7.2 через 1-ю, 2-ю, ... из последних входных связей с заданным показателем. Возможно, на первый взгляд это не очевидно, поскольку в табл. 9.7.2, кажется, указаны определенные образующие, а не их связи. Взглянув, однако, на табл. 9.4.1, последние две строки, мы видим, что в данном случае это одно и то же. В других, более общих случаях об этом различии следует помнить. Такие связывающие функции, зависящие только от порядка, в котором

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

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

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

В (9.7.8) минимум берется по всем фразам, начиная в 1 и кончая в .

Для нашего примера мы имеем:

в чем можно убедиться, вернувшись к табл. 9.4.1 и рассмотрев четвертую колонку.

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

7.4.3. Другое множество интересующих нас величин составляют задержки для связывающей функции использующей упорядоченные ссылки.

Для нашего примера имеем:

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

7.5. Оставив теперь пример, рассмотрим соединения, построенные выше. Приходим ли мы к семантической категории, как в теореме 9.6.1? Ответ на этот вопрос дает

Теорема 9.7.1. Рассмотрим обратно направленную стратегию и предположим, что для любой ветви на диаграмме любая

ассоциированная с ней связывающая функция с показателем связи удовлетворяет неравенству

Тогда по построению мы приходим к целому семантическому отображению.

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

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

Это условие выполнено; в данном случае мы можем даже утверждать, что все последовательно развертываемые конфигурации регулярны. Что касается глобальной регулярности, то она следует из того, что было сказано в доказательстве леммы 9.7.1.)

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

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

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

Потребуются также аналоги величин в (9.7.8). Введем

Для того чтобы наше построение привело к семантической категории, нужно, чтобы были выполнены два условия:

Заметим, что мы уже не можем утверждать, что справедливо лишь