Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

СВОЙСТВА МНОЖЕСТВ ВЫВОДИМЫХ СЛОВ





 

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

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

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

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

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

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

 

p1 = N 0; p2 = N 1; p3 = N 11; p4 = N 10;

p5 = ; p6 = .

 

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

 

p7 = .

 

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

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

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

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

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

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

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

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

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

p1= N 1; p2= N 0;p3= N 11; p4 = N 10; 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; просмотров: 332. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...


Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

Сравнительно-исторический метод в языкознании сравнительно-исторический метод в языкознании является одним из основных и представляет собой совокупность приёмов...

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

Конституционно-правовые нормы, их особенности и виды Характеристика отрасли права немыслима без уяснения особенностей составляющих ее норм...

ПУНКЦИЯ И КАТЕТЕРИЗАЦИЯ ПОДКЛЮЧИЧНОЙ ВЕНЫ   Пункцию и катетеризацию подключичной вены обычно производит хирург или анестезиолог, иногда — специально обученный терапевт...

Ситуация 26. ПРОВЕРЕНО МИНЗДРАВОМ   Станислав Свердлов закончил российско-американский факультет менеджмента Томского государственного университета...

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Studopedia.info - Студопедия - 2014-2025 год . (0.013 сек.) русская версия | украинская версия