СВОЙСТВА МНОЖЕСТВ ВЫВОДИМЫХ СЛОВ
Из всех слов, выводимых в произвольной системе Поста, выделяются подмножества таких слов, которые могут считаться окончательными результатами вычислений.
В процессе вывода таких окончательных слов в системах Поста приходится использовать и другие слова, которые можно рассматривать как промежуточные или вспомогательные слова.
В простейшем случае заключительными считаются все слова, которые не содержат символов вспомогательного алфавита.
В других случаях заключительные слова должны иметь специальную структуру.
Например, рассмотрим систему Поста, в которой выводятся все такие пары двоичных последовательностей (x, y), являющихся правильными записями неотрицательных целых чисел.
В этой системе все выводимые слова, начинающиеся с буквы N, являются вспомогательными. Они представляют правильные записи целых неотрицательных чисел в двоичной системе, выводимых с помощью продукций:
p1 = N0; p2 = N1; p3 = N11; p4 = N10;
p5 = ; p6 = .
Пары целых неотрицательных чисел (x, y) выводятся с помощью продукции:
p7 = .
Приведенная система Поста имеет основной алфавит
A = {0, 1, (, ), ,} и вспомогательный алфавит V = {N}.
Результатами в такой системе являются только такие выводимые слова, которые не содержат символа N.
Выводимые в системе вспомогательные слова имеют вид Nx.
Множество всех слов, выводимых в произвольной системе Поста с непустым вспомогательным алфавитом, разбивается на два класса: это класс слов, содержащих символы вспомогательного алфавита, и класс слов, состоящих только из символов основного алфавита.
Слова из первого класса называются нетерминальными словами системы Поста; из второго класса - терминальными, или заключительными.
В дальнейшем обозначение WPбудет применяться для множества слов в основном алфавите, которые выводятся в системе Поста P. Другие слова, выводимые в системе Поста P и содержащие вспомогательные символы рассматриваются как промежуточные в выводах, позволяющие организовать вывод заключительных слов.
Рассмотрим ещё один пример системы Поста, в которой выводятся все возможные пары слов вида ( , ), где - это произвольная последовательность из нулей и единиц, а - двоичная запись числа, равного длине последовательности .
Выпишем множество продукций соответствующей системы Поста.
1. Вспомогательные продукции, позволяющие выводить правильные двоичные записи неотрицательных целых чисел:
p1= N1; p2= N0;p3= N11; p4 =N10; p5: ; p6: .
2. Вспомогательные продукции, позволяющие выводить слова вида S(x) = y, где x и y - это правильные двоичные записи неотрицательных целых чисел и у = x + 1:
p7: S( 0 ) = 1; p8: ; p9: .
3. Основные продукции, позволяющие выводить пары, слов ( , ), которые являются заключительными:
p10: (0 , 1); p11: (1, 1);
p12: ; p13: .
Здесь символы N и S образуют вспомогательный алфавит, а x, y, z - алфавит переменных. Остальные символы составляют основной алфавит.
Упражнение.Привести пример множества слов в алфавите {0, 1}, которое выводится только в таких системах Поста, которые имеют непустой вспомогательный алфавит.
Рассмотрим класс всех таких множеств слов, каждое из которых выводится в некоторой системе Поста. Покажем, что этот класс замкнут относительно операций объединения и пересечения множеств.
Справедливость приведенного свойства вытекает из теоремы 9.2.
Дата добавления: 2015-09-18; просмотров: 546;