Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
9.6. Семантические отображения6.1.1. Теперь мы попытаемся формализовать в алгебраической форме семантические концепции разд. 9.2. Мы проделаем это в достаточно общем виде, пытаясь четко выявить главные проблемы, возникающие по ходу решения нашей задачи. Постепенно мы будем сужать рассмотрения, накладывая ограничения на семантические отображения, а в разд. 9.7 детально проанализируем структуру некоторых семантических схем. 6.1.2. В нашем понимании семантика относительна: она устанавливает отношение между двумя или более регулярными структурами. Рассмотрим две алгебры изображений
Нам нужно «объяснить» в терминах пользуясь отношением изображений из к изображениям из Чтобы различать эти две алгебры, будем называть первичной алгеброй изображений и Семантическое отображение, Обратное к
Иногда лучше начать анализ семантической схемы через это обратное отображение
Когда вторичная алгебра изображений представляет собой язык, Ниже мы будем пользоваться следущей терминологией. Если 6.2.1. В настоящем разделе мы всюду будем считать первичную алгебру изображений алгеброй отношений — об этом мы уже говорили в разд. 9.3. Вторичная алгебра изображений будет состоять из языка конечных состояний который рассматривается как регулярная структура — см. подраздел 5.4 настоящей главы. Поскольку мы имеем 6.2.2. К сожалению, семантическое отображение, даже если оно адекватно и биективно, не представляет большого интереса, если не имеет дополнительной структуры. Если оно задано лишь как список пар Чтобы обеспечить эту дополнительную структуру, мы воспользуемся комбинаторной регулярностью двух алгебр изображений. 6.3. Начнем с тривиального примера. Пусть Для описания таких первичных изображений достаточно ввести язык конечных состояний, у которого продукции имеют вид Если Таблица 9.6.1 (см. скан) 6.3.2. Читатель может с неудовольствием заметить, что этот пример чересчур упрощенный. Реальная семантика бесконечно сложнее. Но это как раз то, почему мы выбрали такой пример. Как только мы позволим соединения в первичной алгебре Рассмотрим другой пример, тоже совсем простой, с образующими в Построить язык, подходящий для описания таких изображений, нетрудно. Он представлен в виде диаграммы конечного автомата на рис. 9.6.2. Снабдим этот язык семантическим отображением. Для заданного правильно построенного предложения каждый раз, когда мы проходим ветвь 2-3, будем добавлять образующую а к диаграмме конфигурации. Каждый раз при прохождении ветви каждом прохождении через Рис. 9.6.1 (см. скан) Рис. 9.6.2 (см. скан) Таким образом, отсутствует в Таким образом мы построим правильное предложение
Данное семантическое отображение является совершенным. Однако, как мы вскоре убедимся, рассмотренный пример может ввести в заблуждение. 6.4.1. В предложении (9.6.4) слова Можно считать 6.4.2. Следует предупредить читателя, что данный пример не моделирует естественного языка, где невозможно провести такого четкого различия между именами и связками. Наш подход — совершенно абстрактный в противоположность эмпирическому. 6.4.3. Последний пример выявляет наиболее важную проблему, возникающую при установлении семантического отображения. Язык конечных состояний, рассматриваемый как регулярная структура, имеет тип соединения Хотя мы по-прежнему будем иметь дело с языками конечных состояний, нельзя не напомнить читателю, что бесконтекстные языки дают более мощную топологию, а именно 6.5.1. Последний пример дает ключ к пониманию семантических отображений в более общем смысле. Вернемся к диаграмме на рис. 9.6.2. Для заданного правильного предложения Отображение конфигураций в 6.5.2. Это приводит нас к очень важному для последующего анализа понятию. Определение 9.6.1. Под семантическим (для конечных состояний) процессором из в мы будем понимать набор множеств обозначает связку, которая может содержать или не содержать новые образующие). а) Мы начинаем с состояния 1 при б) Предложение в) При любом переходе обратно к состоянию 1 с снова становится равной 0. Замечание. Пункт в) означает, что мы начинаем строить новую подконфигурацию, имея в качестве исходной пустую. Новая подконфигурация не будет присоединяться к уже построенной или построенным. Пункт в) менее важен по сравнению с а) и б) и его можно опустить. Хотя мы здесь ограничимся изучением языков конечных состояний, определение было сформулировано в таком виде, что его можно адаптировать и для более мощных языков. 6.5.3. Чтобы получить некоторое представление о роли сделанного выше определения, вернемся к примеру из подраздела 6.3 настоящей главы. Введем подмножества
В этом примере все Соответствующие отображения конфигураций, представленные через
Замечание 1. Поскольку мы интерпретируем переход назад к состоянию 1 как «начать новую (несоединенную) компоненту конфигурации», мы могли бы, например, позволить ветви Замечание 2. По мере того как эволюционируют наши конфигурации, нам, возможно, потребуется указывать на образующие и связи через координаты конфигураций. Замечание 3. Процессор, которым мы пользуемся, связан с понятием древовидных автоматов. 6.6.1. При заданном семантическом процессоре
В силу ассоциативности (9.6.7) и поскольку 6.6.2. При расширенном семантическом отображении отображение конфигураций получаем для алгебр изображений:
6.6.3. Семантическое отображение было получено нами путем последовательного развертывания значения заданного предложения. Это можно сопоставить с тем, как Вегнер (Wegner 1968) рассматривает процесс выполнения программы — последовательное преобразование информационных структур. В нашем случае инфор-. мационные структуры — это конфигурации из На каждом шаге старые связи могут замыкаться и добавляться новые образующие. Выходные связи новых образующих могут оставаться свободными или же немедленно замыкаться. В нашем примере имела место последняя ситуация. Пока семантический процессор содержит в себе операции слишком общего характера. В следующем разделе мы еще больше сузим выбор. 6.7. Прежде чем перейти к следующему разделу, докажем одну несложную теорему, которая поможет нам яснее выявить алгебраическую структуру проблемы математической семантики. Теорема 9.6.1. Расширенный семантический процессор образует категорию. Доказательство. Введем объекты (в терминологии категорий) С, - и классы, возможно пустые, морфизмов
Очевидно, что
где 6.7.1. Рассмотрим конфигурацию
индексы представляют собой координаты образующих и связи Пусть она состоит из цепочки произвольной конечной длины Каждый элемент 6.7.2. Следовательно, потребность в памяти будет зависеть от того, насколько велики таблицы состав Лемма 9.6.1. Для
Доказательство немедленно следует из того факта, что связки могут только добавлять, но не могут удалять образующие. Соотношение (9.6.11) влечет за собой
Поведение размера таблицы
|
1 |
Оглавление
|