СИСТЕМАХ

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒

Выводы в системах Поста и множества выводимых слов обладают рядом интересных и важных свойств.

1. Существует алгоритм, который по произвольным словам в основном и вспомогательном алфавитах ₁,..., _k, _k+ ₁ и продукции p = определяет выводимость слова _k+ ₁из слов ₁,..., _k с помощью продукции p.

Возможен следующий алгоритм определения применимости произвольной продукции p к заданным словам ₁,..., _k.

1.1. Выделяются все различные символы переменных в образцах t ₁,..., t _k+ _1.

1.2. Находится длина d самого короткого слова среди слов ₁,..., .

1.3. Для выделенного множества символов переменных строятся все подстановки, в которых эти переменные заменяются такими словами в основном и вспомогательном алфавитах, длина которых не превосходит d.

1.4. Для каждой подстановки Q проверяется условие:

" i = 1,..., k + 1 ( _i = t _i Q) (1)

1.5. Если условие (1) имеет место хотя бы для одной подстановки, то _k+ ₁выводится из ₁,..., _k с помощью продукции p.

1.6. Если для всех подстановок условие (1) не выполняется, то _k+ ₁ не выводится из ₁,..., _k с помощью p.

2. Существует алгоритм, который по произвольной последовательности ₁,..., _k - слов в основном и вспомогательном алфавитах заданной системы Поста P определяет, является ли эта последовательность выводом в P или нет.

Пример соответствующего алгоритма может быть получен на основе схемы предыдущего алгоритма.

3. Множество различных слов, которые могут быть получены из слов ₁,..., _k применением продукции p = является конечным.

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒

Дата добавления: 2015-09-18; просмотров: 338. Нарушение авторских прав; Мы поможем в написании вашей работы!

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

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

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

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

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

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

КОНСТРУКЦИЯ КОЛЕСНОЙ ПАРЫ ВАГОНА Тип колёсной пары определяется типом оси и диаметром колес. Согласно ГОСТ 4835-2006* устанавливаются типы колесных пар для грузовых вагонов с осями РУ1Ш и РВ2Ш и колесами диаметром по кругу катания 957 мм. Номинальный диаметр колеса – 950 мм...

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

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Основные разделы работы участкового врача-педиатра Ведущей фигурой в организации внебольничной помощи детям является участковый врач-педиатр детской городской поликлиники...

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