Свойства множеств выводимых слов

ПОСТРОЕНИЕ ВЫВОДОВ В СИСТЕМАХ ПОСТА

Как уже отмечалось, понятие вывода для систем Поста является недетерминированным.

Это означает, что всякий конечный вывод может быть продолжен в новый вывод большей длины не единственным способом. При этом каждое из таких продолжений является допустимым.

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

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

Простой переборный алгоритм последовательного построения всех конечных вычислений в произвольной системе P = (A, B, V, P) можно представить следующей схемой:

1. Определим переменную d, начальное значение которой равно 1.

2. Образуем множество M, состоящее из всех слов в алфавите A È V, длина которых равна d.

3. Последовательно выписываем все возможные последовательности, состоящие из d слов множества M.

Для каждой такой последовательности W проверяется, является ли она вычислением. Если это так, то W и ее начальные фрагменты добавляется к формируемому списку всех конечных выводов в системе P.

4. Увеличим значение d на 1 и повторим действия 2 - 4.

Из приведенных ранее свойств понятия вывода в системах Поста следует, что каждое из приведенных действий - алгоритмическое и выполняется за конечное время. В результате работы алгоритма последовательно заполняется в общем случае бесконечный список, содержащий все конечные вычисления в P.

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

Из всех слов, выводимых в произвольной системе Поста, выделяются подмножества таких слов, которые могут считаться окончательными результатами вычислений.

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

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

В других случаях заключительные слова должны иметь специальную структуру.

Например, рассмотрим систему Поста, в которой выводятся все такие пары двоичных последовательностей (x, y), являющихся правильными записями неотрицательных целых чисел.

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

p₁ = N 0; p₂ = N 1; p₃ = N 11; p₄ = N 10;

p₅ = ; p₆ = .

Пары целых неотрицательных чисел (x, y) выводятся с помощью продукции:

p₇ = .

Приведенная система Поста имеет основной алфавит
A = { 0, 1, (,),, } и вспомогательный алфавит V = { N }.

Результатами в такой системе являются только такие выводимые слова, которые не содержат символа N.

Выводимые в системе вспомогательные слова имеют вид Nx.

Множество всех слов, выводимых в произвольной системе Поста с непустым вспомогательным алфавитом, разбивается на два класса: это класс слов, содержащих символы вспомогательного алфавита, и класс слов, состоящих только из символов основного алфавита.

Слова из первого класса называются нетерминальными словами системы Поста; из второго класса - терминальными, или заключительными.

В дальнейшем обозначение W_P будет применяться для множества слов в основном алфавите, которые выводятся в системе Поста P. Другие слова, выводимые в системе Поста P и содержащие вспомогательные символы рассматриваются как промежуточные в выводах, позволяющие организовать вывод заключительных слов.

Рассмотрим ещё один пример системы Поста, в которой выводятся все возможные пары слов вида (, ), где - это произвольная последовательность из нулей и единиц, а - двоичная запись числа, равного длине последовательности .

Выпишем множество продукций соответствующей системы Поста.

1. Вспомогательные продукции, позволяющие выводить правильные двоичные записи неотрицательных целых чисел:

p₁= N 1; p₂= N 0; p₃= N 11; p₄ = N 10; p₅: ; p₆: .

2. Вспомогательные продукции, позволяющие выводить слова вида S (x) = y, где x и y - это правильные двоичные записи неотрицательных целых чисел и у = x + 1:

p₇: S (0) = 1; p₈: ; p₉: .

3. Основные продукции, позволяющие выводить пары, слов (, ), которые являются заключительными:

p₁₀: (0, 1); p₁₁: (1, 1);

p₁₂: ; p₁₃: .

Здесь символы N и S образуют вспомогательный алфавит, а x, y, z - алфавит переменных. Остальные символы составляют основной алфавит.

Упражнение. Привести пример множества слов в алфавите { 0, 1 }, которое выводится только в таких системах Поста, которые имеют непустой вспомогательный алфавит.

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

Справедливость приведенного свойства вытекает из теоремы 9.2.

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