Cтраница 3
Таким образом, определение выводимости в расширенном исчислении предикатов в точности совпадает с соответствующим определением для исчисления предикатов. Содержание этого определения, однако, несколько иное, так как правила подстановок в расширенном исчислении предикатов отличаются от соответствующих правил в исчислении предикатов. Формулировка теоремы дедукции для расширенного исчисления предикатов остается той же, что и раньше, а доказательство ее проводится аналогично. [31]
В приложениях к грамматике естественных языков терминальными символами следует считать обычные слова, тогда как символы из V - Т суть названия частей речи и других грамматических категорий. Правила порождения могут включать грамматические правила типа А предложение - подлежащееска-зуемое и правила подстановки типа подлежащее - - мальчик и сказуемое - - улыбается. Строки терминальных символов языка являются грамматически правильными предложениями. [32]
Явные определения из выводов нумерических равенств устраняются легко. Схема замены в формализме ( Z1), ввиду наличия в нем аксиомы ( J2), правила подстановки и схемы заключения, является производной схемой. Это делается следующим образом. [33]
Начальный символ представляет собой подмножество классов алфавита, отображаемых наиболее предпочтительными семант ] е-скими фрагментами, выбираемыми на основе процедур экспертного оценивания. Такой начальный символ может быть задан в виде семантического описания основных элементов АСУ определенного к асса. Правила подстановки в языковой системе включают выбор эталона целей на языке классов алфавита. [34]
В системе ФП находит применение фиксированное множество комбинационных форм, называемых функциональными формами. Они в сочетании с простыми описаниями являются единственными средствами построения новых функций из уже существующих. В них не используются переменные или, правила подстановок, и они становятся операциями соответствующей алгебры программ. Все функции системы ФП относятся к одному типу: они отображают объекты на объекты и всегда работают с одним аргументом. [35]
Используют два основных вида грамматического разбора: разбор сверху вниз и разбор снизу вверх. Процедура разбора сверху вниз состоит в последовательных попытках путем использования правил соответствующей грамматики получить заданное терминальное предложение исходя из начального символа. При использовании процедуры разбора снизу вверх необходимо восстанавливать дерево вывода, начиная с элементов основного словаря и применяя инвертированные правила подстановки. Эта процедура начинается с конкретного предложения и заканчивается при получении начального символа. Так как подстановки 1 - аА и А - Ъ действительно порождают предложение ab, то это предложение считается грамматически правильным; предложения же ас и ad отклоняются. [36]
Таким образом, системы проектирования, осуществляющие процесс порождения и распознавания вариантов, при массовой разработке проектов в целях уменьшения числа шагов, необходимых для разработки проекта с заданными свойствами, и обеспечения требуемой полноты рассматриваемых вариантов, целесообразно представлять в классе адаптивных систем управления проектированием с эталоном объекта проектирования. Использование для этого процедур ПГ в среднем по множеству проектов уменьшает время генерации вариантов. При этом библиотека системы проектирования играет роль алфавита ПГ, а эталон - начального символа ПГ; классы алфавита определяют зоны компетенции экспертов-проектировщиков, правила подстановки ПГ определяют инструктивную часть системы проектирования. [37]
Цель заключается в том, чтобы распознавать десятичные числа. Грамматика эквивалентна грамматике, приведенной в разд. Правила подстановки несколько отличаются, отчасти для иллюстрации того факта, что одни и те же предложения могут генерироваться различными правилами, но в основном по причинам, которые будут пояснены позднее в разд. [38]
Проиллюстрируем на примере, приведенном выше, порядок выполнения синтаксически ориентированного грамматического разбора. Пусть требуется установить, принадлежит ли некоторая конструкция к классу объектов, порождаемых данной грамматикой. В положительном случае разбор продолжается, в отрицательном - исследуемый объект отклоняется. Поскольку процедура разбора снизу вверх начинается с терминального предложения, на первом шаге рассматриваются только правила подстановки, приводящие исключительно к непроизводным элементам. На следующем шаге разбора необходимо получить объект О2, состоящий из объекта О, расположенного над непроизводным элементом а. При положительном результате образ считается допустимым, при отрицательном - отклоняется. На рис. 8.8, б представлены грамматически правильные объекты, на рис. 8.8, в - объекты, отклоненные на одном из шагов разбора. [39]
Мы должны ответить на два вопроса: во-первых, Является ли данная строка предложением языка, определяемого грамматикой, и, во-вторых, какова структура строки, если она является предложением. Процесс ответа на эти вопросы посредством использования грамматики в анализирующем режиме называется грамматическим разбором. Один из методов грамматического разбора строки, называемый разбором сверху вниз, основан на конструировании дерева всех возможных способов, посредством которых можно применять правила подстановок для построения стоящей на первом месте исходной строки. Если нельзя найти такую последовательность правил, строка не является предложением; если имеется единственная последовательность, то полный путь по дереву определяет структуру строки. Если имеется более чем одна последовательность правил, структура строки синтаксически неоднозначна. [40]
На рис. 8.9 [14] представлена схема вывода цепочечных грамматик. На выходе блока в результате процесса обучения воспроизводится грамматика Г, согласованная с заданными цепочками. Процедура, позволяющая решить указанную задачу в общем случае, до сих пор неизвестна; существует, однако, множество частных алгоритмов. Типичным подходом в этой области можно считать следующий. Сначала строятся правила подстановки, порождающие именно те цепочки, которые были заданы; затем посредством сращивания элементов основного словаря - более простая рекурсивная грамматика, обеспечивающая порождение бесконечного числа цепочек. Процедура состоит из трех этапов: 1) формирования правил подстановки; 2) преобразования правил подстановки в грамматику; 3) упрощения грамматики. [41]
Второй шаг процесса вывода состоит в следующем. Строится объединение грамматик, полученных на первом шаге для каждого из объектов. К каждой из этих грамматик применяется специальная процедура преобразования и из полученных модифицированных грамматик, согласно некоторому критерию, выбирается наилучшая. Предпочтение, естественно, отдается коротким грамматикам, поскольку такие, действительно, являются единой грамматикой для заданной обучающей выборки, а не просто набором частных случаев. Однако целесообразно, чтобы правила подстановки были как можно конкретнее в том, что касается возможных типов непроизводных элементов и отношений. Очевидно, что окончательный критерий выбора грамматики должен базироваться на какой-то комбинации двух этих эвристических приемов. [42]
Операции реляционной алгебры можно осуществлять с помощью правил подстановки, по аналогии с упрощением обычных алгебраических выражений, что вполне реализуется на Прологе. Однако при этом возникает дополнительная проблема, которую мы будем рассматривать в гл. Речь идет о конкретном представлении отношений в памяти ЭВМ. В зависимости от того, как именно это сделано, некоторые правила подстановки могут и не оптимизировать вычисления, в особенности те правила, которые относятся к перемещению проекций. [43]