Cтраница 2
Говоря о правилах подстановки и переименования, мы всегда имеем в виду допустимые в каком-либо выводе подстановки и переименования. [16]
В общем случае правило подстановки утверждает следующее. [17]
Первая аккуратная формулировка правила подстановки приведена, невидимому, у Гильберта - Бернайса [ 1939, стр. [18]
Приведем другое определение правила подстановки, эквивалентное старому определению. Оно гораздо более громоздко, но из него будет прямо следовать, что получаемое в результате подстановки слово является формулой. Кроме того, это определение будет полезно в других рассуждениях. [19]
Из новой формулировки правила подстановки непосредственно вытекает, что результат подстановки в формулу 91 есть также формула. [20]
Если левая часть правила подстановки ограничена одним нетерминальным. [21]
Правила вывода являются правилами подстановки и отделения для принимаемых и отбрасываемых выражений. [22]
Распознаватель, описанный правилами подстановки, нетрудно переписать а виде набора синтаксических подпрограмм. Например, алгоритм распознавателя ( транслятора для перевода в обратную польскую запись), заданный таблицей 5.26, можно записать в виде пяти подпрограмм с именами ПО, ВО-МО-ТО, Ml, Т1 и В1, в которые включены соответствующие семантические подпрограммы ОШИБКА 1, СП1, СП2, СПЗ и ВЫХОД. [23]
Это правило называется правилом подстановки. [24]
Для исчисления с прямым правилом подстановки понятие доказуемости остается прежним ( это мы предоставляем доказать читателю), но отношение выводимости расширяется. [25]
Если во всех правилах подстановки длина строки х не более т, а длина строки у не более п, то распознаватель анализирует грамматику с ( т, п) ограниченным контекстом. С другой стороны, ничто не препятствует тому, чтобы строка хиу, являющаяся образцом, при необходимости совпадала со всем содержимым стека. [26]
Правила вывода следующие: правило подстановки R1 с одной посылкой и правило замены R2 с двумя посылками. [27]
Свойство симметричности в соединении с правилом подстановки гарантирует обратимость системы преобразований. [28]
Если Q выведена из Р по правилу подстановки 2.2, то очевидно, что h HQ может быть выведена из h ПР. [29]
Если F выводима из G в исчислении предикатов с постулированным правилом подстановки ( конец § 37), то F тождественна в каждой области, в которой тождественна G, а поэтому дедуктивно равные формулы тождественны в одних и тех же областях. [30]