9.6. Семантические отображения

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

6.1.2. В нашем понимании семантика относительна: она устанавливает отношение между двумя или более регулярными структурами. Рассмотрим две алгебры изображений

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

Семантическое отображение, — определенное на некотором подмножестве с, будет определено однозначно. В противном случае наше «объяснение» было бы также неоднозначным. Но такой ситуации мы решили избегать (см. подраздел 2.4 настоящей главы). Мы будем говорить, что адекватно для но отношению к

Обратное к отображение не обязательно должно быть однозначным. Заданное первичное изображение может соответствовать множеству (из нескольких элементов)

Иногда лучше начать анализ семантической схемы через это обратное отображение

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

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

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

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

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

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

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

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

продукции имеют вид или Этот язык имеет регулярное выражение

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

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

6.3.2. Читатель может с неудовольствием заметить, что этот пример чересчур упрощенный. Реальная семантика бесконечно сложнее. Но это как раз то, почему мы выбрали такой пример. Как только мы позволим соединения в первичной алгебре бражений, мы должны будем ввести синтаксические ограничения, чтобы сделать семантику адекватной.

Рассмотрим другой пример, тоже совсем простой, с образующими в приведенными в табл. 9.6.1, Произвольное изображение в состоит тогда, скажем, из -образующих к из которых присоединена у-образующая, а также -образующих к из которых присоединены -образующие. На рис. 9.6.1 .

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

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

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

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

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

Таким образом, определяется единственно на оно адекватно для по отношению к Ясно также, что сюръектнвно. Для заданного изображения перечислим его образующие уровня 0, сначала а, потом Каждый раз, встретив а, мы записываем присоединенные к ней образующие у; аналогично поступаем с образующими Следуя этой процедуре, проходим по рис. 9.6.2 и записываем терминальные символы. Если а

отсутствует в мы переходим к 4, записывая у, в противном случае — к 2, записывая а затем к 3, записывая а. Если к а присоединена одна или несколько у, повторно проходим через соответствующее число раз. Если имеется еще одна а, возвращаемся к в противном случае переходим к 4.

Таким образом мы построим правильное предложение По рис. 9.6.1, например, мы получаем предложение

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

6.4.1. В предложении (9.6.4) слова означают, как было описано выше, вхождение «соответствующих» образующих Слова у играют иную роль. Они указывают, какие соединения установлены между отношениями -образующими).

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

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

6.4.3. Последний пример выявляет наиболее важную проблему, возникающую при установлении семантического отображения. Язык конечных состояний, рассматриваемый как регулярная структура, имеет тип соединения «линейный» (см. подраздел 5.4.1). Наша алгебра отношений, с другой стороны, обладает гораздо более гибким типом соединения

Хотя мы по-прежнему будем иметь дело с языками конечных состояний, нельзя не напомнить читателю, что бесконтекстные языки дают более мощную топологию, а именно «древовидный» (см, т. I, разд. 2.6). Еще более мощный тип соединения дают контекстно-зависимые языки, в которых допускаются циклы, как в нашей первичной алгебре изображений. Эти вопросы, по-видимому, следует подробно рассмотреть в наших будущих работах.

6.5.1. Последний пример дает ключ к пониманию семантических отображений в более общем смысле. Вернемся к диаграмме

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

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

6.5.2. Это приводит нас к очень важному для последующего анализа понятию.

Определение 9.6.1. Под семантическим (для конечных состояний) процессором из в мы будем понимать набор множеств при со связками

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

а) Мы начинаем с состояния 1 при

б) Предложение обрабатывается слева направо.

в) При любом переходе обратно к состоянию 1 с снова становится равной 0.

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

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

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

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

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

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

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

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

6.6.1. При заданном семантическом процессоре мы можем расширить отображения конфигураций чтобы опредедить их для фраз и полагая определено», если и не удовлетворяет правилам грамматики, а если — правильно построенная фраза (9.5.4) при то

В силу ассоциативности (9.6.7) и поскольку -детерминированная, цепочка является единственной и, следовательно, также единственно. Пустую цепочку мы ассоциируем с «тождественное» (единица).

6.6.2. При расширенном семантическом отображении отображение конфигураций представляет наше семантическое отображение. После того как -идентификация выполнена в мы

получаем для алгебр изображений:

6.6.3. Семантическое отображение было получено нами путем последовательного развертывания значения заданного предложения. Это можно сопоставить с тем, как Вегнер (Wegner 1968) рассматривает процесс выполнения программы — последовательное преобразование информационных структур. В нашем случае инфор-. мационные структуры — это конфигурации из На каждом шаге старые связи могут замыкаться и добавляться новые образующие. Выходные связи новых образующих могут оставаться свободными или же немедленно замыкаться. В нашем примере имела место последняя ситуация.

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

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

Теорема 9.6.1. Расширенный семантический процессор образует категорию.

Доказательство. Введем объекты (в терминологии категорий) С, - и классы, возможно пустые, морфизмов

Очевидно, что содержит тождественное отображение Из того, как мы расширили исходное семантическое отображение в определении 9.6.1, непосредственно следует, что

где обозначает конкатенацию цепочек и и Таким образом семантический процессор образует категорию, что и требовалось доказать.

6.7.1. Рассмотрим конфигурацию у которой

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

Пусть — произвольная правильно построенная фраза, начинающаяся в состоянии и заканчивающаяся в состоянии Пусть

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

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

6.7.2. Следовательно, потребность в памяти будет зависеть от того, насколько велики таблицы состав Поведение величины установить нетрудно.

Лемма 9.6.1. Для с имеет место

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

Соотношение (9.6.11) влечет за собой

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