![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задача о полноте автоматного базиса
Набор структурных автоматов Усилия математиков для получения аналога теоремы Поста для автоматов не увенчались успехом. В 1964 г. М.И. Кратко доказал несуществование алгоритма для определения полноты системы Теорема. Система автоматов Доказательство. Рассмотрим произвольный автомат Схема состоит из двух частей.
…
Рис. 6.
Левая половина называется запоминающей частью. Она состоит из
то это означает, что автомат Правая половина называется комбинационной частью и представляет СФЭ. Входы этой схемы: 1) двоичное слово 2) двоичное слово Выходы: 1) двоичное слово 2) двоичное слово Покажем, что сигналы управления памятью являются булевыми функциями от тех же переменных, что и выход автомата, а, значит, они могут быть реализованы полной системой ФЭ. В каждый момент времени
Используемые в канонической схеме Итак,
Выразим
Теорема доказана.
|