9.3. Свойства выводов в продукционных
СИСТЕМАХ
Выводы в системах Поста и множества выводимых слов обладают рядом интересных и важных свойств.
1. Существует алгоритм, который по
произвольным словам в основном и
вспомогательном алфавитах
1,
. . . ,
k,
k+1
и продукции
=
определяет выводимость слова
k+1
из слов
1,
... ,
k
с помощью продукции .
Возможен следующий алгоритм определения применимости произвольной продукции к заданным словам 1, ... , k.
1.1. Выделяются все различные символы переменных в образцах t1, . . . , tk+1.
1.2. Находится длина d самого короткого слова среди слов 1, ... , .
1.3. Для выделенного множества символов переменных строятся все подстановки, в которых эти переменные заменяются такими словами в основном и вспомогательном алфавитах, длина которых не превосходит d.
1.4. Для каждой подстановки проверяется условие:
i = 1,. . . , k+1 ( i = ti ) (1)
1.5. Если условие (1) имеет место хотя бы для одной подстановки, то k+1 выводится из 1, ... , k с помощью продукции .
1.6. Если для всех подстановок условие (1) не выполняется, то k+1 не выводится из 1, ... , k с помощью .
2. Существует алгоритм, который по произвольной последовательности 1, . . . , k слов в основном и вспомогательном алфавитах заданной системы Поста P определяет, является ли эта последовательность выводом в P или нет.
Пример соответствующего алгоритма может быть получен на основе схемы предыдущего алгоритма.
3.Множество различных слов, которые могут быть получены из слов 1, ... , k применением продукции = является конечным.
9.4. Решение задач в продукционных
СИСТЕМАХ
Задачи, которые можно решать получать с помощью систем Поста, естественно связаны с множествами слов, выводимых в этих системах.
Простейший вопрос, который можно отнести к системе это вопрос о принадлежности конкретного слова множеству слов , выводимых в . Такой вопрос записывается в виде:
″
″?
Ответом на него может быть только либо нет, либо да.
Естественный процесс поиска правильного ответа на этот вопрос состоит в нахождении вывода слова в системе .
При этом если существует такой вывод W, то он может быть найден последовательным перебором всех конечных выводов в системе .
Если же такой вывод отсутствует, а значит, слово является невыводимым, то переборный алгоритм не позволяет получить ответ "нет" и поиск отрицательного ответа должен осуществляться другими методами.
Обобщение рассмотренного типа задач, решаемых системами Поста, это задачи, связанные с вопросом о выводимости в системе слов, являющихся применениями заданного образца.
Для заданного образца t требуется получить ответ на вопрос о существовании такой подстановки , что t .
Поскольку может содержать несколько различных применений t, то возможны несколько вариантов уточнения данного типа вопроса:
1) найти любое применение t, выводимое в системе ;
2) перечислить все применения t, выводимые в системе ;
3) найти применения t, обладающие дополнительным свойством.
Ответы на перечисленные варианты вопроса естественно представлять в виде последовательностей таких подстановок, что применение подстановки к t дает один из элементов ответа на вопрос.
Если же ни одно применение t не выводимо в системе Поста , то ответом на поставленный вопрос является нет.
Как и в предыдущем случае, естественный алгоритм перебора всех конечных выводов в системе не позволяет получить отрицательный ответ.