9. Продукционные системы

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

9.1. Продукции и системы поста

Пусть А, B и V  три непересекающихся конечных алфавита, причем А  B  , которые называются соответственно основным алфавитом, вспомогательным алфавитом и алфавитом переменных.

В дальнейшем всегда будет предполагаться, что АB  2.

Всякое слово, составленное из символов алфавитов А, B и V, называется образцом.

Слово (A  B)* называется применением образца t, если существует подстановка  = , где x₁, . . . , x_k  все различные символы переменных, входящих в t, а ₁, . . . , _k  непустые слова в алфавите А B, что слово получается из t заменой каждого вхождения символов переменных x₁, . . . , x_k на соответствующие им слова в подстановке .

Применение подстановки  к образцу t обозначается как t.

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

Например, если A = {0, 1}, B = , V = {x}, то образец t = 1x0 представляет все правильные записи не менее чем трехразрядных четных двоичных чисел. Образец x1x представляет двоичные последовательности, составленные из двух одинаковых последовательностей разделенных 1.

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

ТЕОРЕМА 9.1

Множества применений образцов t₁ и t₂  Ut₁ и Ut₂ совпадают тогда и только тогда, когда t₁ и t₂ совпадают с точностью до переименования переменных.

Доказательство

Необходимость. () Покажем, что если Ut₁ = Ut₂, то образцы t₁ и t₂ совпадают с точностью до переименования переменных.

Пусть Ut₁ = Ut₂. Без ограничения общности можно считать, что множества символов переменных в образцах t₁ и t₂ не пересекаются.

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

Пусть t₁ = ₁, ... , _k и t₂ = ₁, ... , _k.

Произведем последовательное посимвольное сравнение t₁ и t₂ слева направо.

При этом возможны следующие случаи:

1. _i  (А B);

2. _i  V.

Рассмотрим первый из этих случаев и покажем, что справедливы соотношения _i  (А B) и _i = _i.

Для этого рассмотрим множества всех таких применений t₁ и t₂, которые получаются из t₁ и t₂ заменой символов переменных на слова длины 1.

Тогда, если _i _i, то рассматриваемые множества кратчайших по длине слов в Ut₁ и Ut₂ являются разными, так как i-й символ всех слов первого множества равен _i. Однако значения i-го символа слов второго множества могут быть отличными от _i.

Из проведенных рассуждений следует, что на одинаковых позициях образцов t₁ и t₂ могут располагаться либо символы переменных, либо равные символы из А B.

Рассмотрим второй случай. Покажем, что в этом случае _i также является символом переменной и _i = _j тогда и только тогда, когда _i = _j. Первое из приведенных свойств верно, поскольку если _i  А B, то в кратчайших применениях t₂ символ с порядковым номером i всегда равен _i, а в кратчайших применениях t₁ символ с тем же номером принимает значения всех символов из А B.

Проверим справедливость второго свойства. Пусть _i V и _j, j < i, обозначают одну и ту же переменную в t₁. Тогда все применения t₁, получаемые заменой переменных на слова длины 1 в алфавите А  B, имеют одинаковые j-й и i-й символы. Если же _i и _j  разные символы переменных в t₂, то среди кратчайших по длине применений образца t₁ имеются такие, в которых j-й и i-й символы  разные. Поэтому Ut₁ Ut₂. Последнее заключение противоречит предполагаемому равенству множеств Ut₁ и Ut₂.

Доказательство того, что если _i = _j, то _i = _j можно провести аналогичными рассуждениями.

Из доказательства свойств, имеющих место в случаях 1 и 2, следует, что t₁ и t₁ совпадают с точностью до переименования переменных.

Достаточность. () Пусть образцы t₁ и t₂ совпадают с точностью до переименования переменных. Тогда множества применений этих образцов совпадают.

Действительно, пусть подстановка ₁ = задает переименование переменных из t₁ в переменные из t₂, которое преобразует t₁ в t₂.

Тогда, если слово является применением t₁, получаемым с помощью подстановки , то является применением t₂ с помощью подстановки ₁, т.е. Ut₁  Ut_2. Обратное включение Ut₁  Ut₂ доказывается аналогично. Поэтому Ut₁ = Ut₂.

Следовательно, Ut₁ = Ut₂.

Доказательство окончено.

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

Семейство слов в основном алфавите { ₁, . . . , _r} называется согласованным применением образцов t₁, . . . , t_r, если найдется такая подстановка  для всех различных символов переменных в этих образцах, что  i = 1, . . . , r (t_i  = _i). То есть если все эти слова получаются из соответствующих им образцов с помощью одного и того же уточнения входящих в них одинаковых символов переменных.

ОПРЕДЕЛЕНИЕ

Продукцией называется запись вида  = , где t₁, . . . , t_n+1  некоторые образцы.

В продукции  образцы t₁, . . . , t_n образуют посылки, а t_n+1  заключение.

Продукция , множество посылок которой является пустым, называется аксиомой.

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

ОПРЕДЕЛЕНИЕ

Слово _n+1 в алфавите (A  V) выводится из слов ₁, . . . , _n в этом же алфавите применением продукции  = , если существует такая подстановка , содержащая все различные символы переменных, входящих в образцы t₁, ... , t_n+1, что  i = 1, ... , n+1 (t_i = _i).

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

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

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

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

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