Определение. Слово n+1 в алфавите (a è v) выводится из слов 1,

Слово _{n+ 1} в алфавите (A È V) выводится из слов
₁,..., _n в этом же алфавите применением продукции
p = , если существует такая подстановка Q, содержащая все различные символы переменных, входящих в образцы t ₁,..., t _{n + 1}, что " i = 1,..., n + 1 (t _i Q = _i).

В пределах одной продукции одинаковые символы переменных понимаются одинаково и при всяком применении продукции заменяются одинаково. Процесс получения слова _{n+ 1­} из слов ₁,..., _n с помощью продукции p называется шагом вывода, а слово _{n+ 1­} называется применением продукции p.

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

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

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

Упражнение. Пусть основной и вспомогательный алфавиты состоят из символов 0 и 1, а алфавит переменных состоит из символов x, y. Привести пример продукции p = , где t _{n+ 1} содержит только такие символы переменных, которые входят в t ₁,..., t _n, и последовательности слов ₁,..., _n, из которых с помощью подстановок Q₁ и Q₂ выводятся разные слова.

Дата добавления: 2015-03-31