СИСТЕМАХ

⇐ Предыдущая 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. Нарушение авторских прав; Мы поможем в написании вашей работы!

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

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

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

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

Гидравлический расчёт трубопроводов Пример 3.4. Вентиляционная труба d=0,1м (100 мм) имеет длину l=100 м. Определить давление, которое должен развивать вентилятор, если расход воздуха, подаваемый по трубе, . Давление на выходе . Местных сопротивлений по пути не имеется. Температура...

Огоньки» в основной период В основной период смены могут проводиться три вида «огоньков»: «огонек-анализ», тематический «огонек» и «конфликтный» огонек...

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

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

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

Случайной величины Плотностью распределения вероятностей непрерывной случайной величины Х называют функцию f(x) – первую производную от функции распределения F(x): Понятие плотность распределения вероятностей случайной величины Х для дискретной величины неприменима...

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